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
# Q1 - Téléchargement & lecture avec GraphStream en utilisant (FileSourceEdge)
## But :
télécharger les données SNAP et lire le graphe com-dblp.ungraph.txt en utilisant FileSourceEdge (GraphStream).
## Commandes (téléchargement) :
https://snap.stanford.edu/data/bigdata/communities/com-dblp.ungraph.txt.gz
Le code suivant lit le fichier d’arêtes et affiche quelques informations de base. Il utilise FileSourceEdge comme demandé.
## Remarques :
Le graphe contient plusieurs centaines de milliers de nœuds → il faut suffisamment de RAM (plusieurs Go).
graph.display() fonctionne mais la visualisation n’est pas informative pour cette taille (très lente).
# Q2 - Mesures de base : nœuds, arêtes, degré moyen, clustering ; comparaison ER
## Mesures (valeurs observées / calculées) :
Valeurs numériques observées / connues pour ce jeu de données (com-DBLP) :
Nombre de nœuds : n ≈ 317 080
Nombre d’arêtes : m ≈ 1 049 866
Degré moyen : <k> = 2m / n ≈ (2×1049866) / 317080 ≈ 6.622089
Coefficient de clustering observé (moyenne locale) : C ≈ 0.6324 (selon le calcul fais dans le code avec Toolkit)
## Coefficient de clustering attendu pour un graphe aléatoire G(n,p)
Pour un graphe Erdős–Rényi G(n,p) on a approximativement :
p ≈ <k> / n-1
et le coefficient de clustering moyen vaut environ Crand≈p
Calcul numérique :
p ≈ 6.622089 / 317079 ≈ 0,0000208847
# Q3 - Connexité
## Définitions :
Un graphe est connexe si tous les nœuds sont reliés entre eux par des chemins (une seule composante connexe contenant tous les nœuds).
Pour G(n,p), la connectivité (avec haute probabilité) apparaît autour du seuil p ≈ (ln n)/n ce qui correspond à un degré moyen ⟨k⟩ ≈ ln n.
## Mesures / valeurs pour DBLP :
n≈317000 → ln n ≈ ln(317000) ≈ 12.66.
Seuil en degré moyen pour connectivité ER : ⟨k⟩conn ≈ ln n ≈ 12.66 ≈ 13.
Degré moyen observé dans DBLP : ⟨k⟩ ≈ 6.6 < 13
## Observation (DBLP réel) :
DBLP n’est pas strictement connexe : il existe quelques petites composantes isolées (quelques nœuds ou petites communautés non reliées).
Cependant DBLP contient une très grande composante connexe (GCC) qui regroupe la très grande majorité des nœuds.
## Comparaison avec un G(n,p) de même n et <k> :
Un G(n,p) avec le même degré moyen <k> ≈ 6.6 aura p = <k> /(n−1) ≈ 0,0000208847.
Puisque <k> < (ln n) un ER comparable ne sera pas (avec haute probabilité) entièrement connexe. On s’attend à :
une composante géante (si <k>>1).
plusieurs petites composantes isolées.
l’absence de “tous les nœuds connectés” tant que <k> n’atteint pas (ln n).
## Conclusion :
DBLP connexe ? => Non (mais contient une très grande composante connexe).
Réseau aléatoire même n et degré moyen (6.6) ? => Non — un G(n,p) comparable aura plusieurs composantes ; il ne sera pas complètement connexe.
Degré moyen minimum pour connexité d’un G(n,p) => <k> >= (ln n) ≈ 12.66 ≈ 13 .