Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# MesureRI
TP de mesures de réseaux d'interactions
Mesures :
```txt
Noeuds: 317080
Arcs: 1049866
Degré moyen: 6,622
Coefficient de clustering: 0,632
```
## Question 2 : Pour un réseau aléatoire de même taille et même degré moyen, quel coefficient de clustering ?
Le coefficient de clustering C d'un graphe aléatoire est défini par la formule suivante :
C = p = {k}/N
Pour les mêmes données, on a :
C = 6.622 / 317080 = 0.208e-5
## Question 3 : Pour un réseau aléatoire de même taille et même degré moyen, sera t-il connexe ?
Etant donné que le degré moyen est supérieur à 4.5, on considère que le graphe est connexe.
## Question 4 : Tracer la distribution des degrés du graphe, etc
## Question 5 : On cherche maintenant à calculer la distance moyenne + distribution des distances moyennes
(Me retrouvant forcer à exécuter le programme sur ma machine personnelle, bien moins puissante, le travail s'en est retrouvé atteint)
J'ai obtenu sur un premier échantillon de 1000 noeuds une disance moyenne de 6,766.
L'hypothèse des 6 degrés de séparation semble donc s'infirmer, impliquant que notre graphe n'est pas un réseau petit monde.
La distance moyenne d'un réseau aléatoire G(N, p) de même caractéristiques serait d'environ
{d} = ln N / ln {k} = ln 317080 / ln 6.622 ~= 6.701
La distribution de cette dernière semble suivre une loi normale centrée sur la distance moyenne du réseau.
## Question 6 : On refait les même mesures pour un graphe aléatoire et un graphe généré par la méthode d'attachement préférentiel de Barabasi-Albert
### Graphe aléatoire
Voici les mesures prises pour le graphe généré aléatoirement :
```txt
Noeuds: 317087
Arcs: 1049982
Degré moyen: 6,623
Coefficient de clustering: 0,000
Distance moyenne échantillonnée: 6,879
```
*Distribution des degrés moyens pour un graphe aléatoire, très similaire au graphe de collaboration*
*Distribution des distances moyennes pour un graphe aléatoire, elle aussi très similaire au graphe de collaboration*
Les mesures sont très proches de celles effectuées sur le graphe de collaboration, mis à part le coefficient de clustering qui en est très loin.
### Graphe BA
Voici les mesures prises pour le graphe généré via la méthode de Barabasi-Albezrt (avec un nombre max d'attachements de 7) :
```txt
Noeuds: 317087
Arcs: 1049982
Degré moyen: 6,623
Coefficient de clustering: 0,000
Distance moyenne échantillonnée: 6,879
```
*Distribution des degrés moyens pour un graphe de Barabasi-Albert, très similaire au graphe de collaboration*
*Distribution des distances moyennes pour un graphe de Barabasi-Albert, elle aussi très similaire au graphe de collaboration*