Newer
Older
# 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 :
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 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 .
# Qst 4 - Distribution des degrés
## Méthode :
Pour obtenir la distribution des degrés, on utilise la fonction Toolkit.degreeDistribution(graph) de GraphStream, qui renvoie pour chaque degré k le nombre de noeuds Nk ayant ce degré.
La probabilité qu'un noeud ait un degré k est alors :
pk = Nk / N .
On a généré le fichier degreeDist_dblp.dat pour Gnuplot afin de tracer la distribution.
## Résultat :
1. Distribution linéaire : on observe que la majorité des noeuds ont un faible degré et très peu de noeuds ont un degré éleve.
2. Distribution log-log : en échelle log-log, on obtient approximativement une ligne droite sur plusieurs ordres de grandeur, indiquant que le réseau suit une loi de puissance : pk ∼ Ck−γ
En utilisant la commande fit de Gnuplot, on obtient un exposant :
γ ≈ 2.7±0.04
3. Comparaison avec Poisson : la distribution de Poisson de même moyenne (<k> ≈6.6) est beaucoup plus concentrée autour du degré moyen et décroît très rapidement pour les degrés élevés, ce qui confirme que DBLP n’est pas un réseau aléatoire de type Erdős–Rényi.
# Q5 - Distance moyenne et distribution des distances
## Méthode :
Le calcul exact des plus courts chemins entre toutes les paires de nœuds étant trop coûteux, nous avons estimé la distance moyenne en procédant ainsi :
1. Tirer 1000 sommets au hasard dans le graphe.
2. Effectuer un parcours en largeur (BFS) à partir de chacun de ces sommets.
3. Calculer la distance moyenne et la distribution des distances.
## Résultats :
1. Distance moyenne estimée :
⟨d⟩≈6,8125.
2. Distance moyenne d’un réseau aléatoire de même n et \<k> : \<d>ER 6,7006.
3. Distribution des distances : la plupart des paires de nœuds sont séparées par 5 à 9 arêtes. La distribution est très concentrée autour de la moyenne, avec une décroissance rapide pour les grandes distances.
## Interprétation :
1. L’hypothèse des six degrés de séparation se vérifie approximativement.
2. Le réseau DBLP est un réseau petit monde car :
distances moyennes faibles et coefficient de clustering élevé.
3. Les réseaux ER comparables ont des distances plus longues et un clustering très faible.
# Q6 - Comparaison avec modèles génératifs
## Méthode :
Nous avons généré deux réseaux artificiels avec GraphStream, ayant le même nombre de nœuds et le degré moyen du DBLP :
1. Réseau aléatoire (Erdős–Rényi) : RandomGenerator(kER).
2. Réseau avec attachement préférentiel (Barabási–Albert) : BarabasiAlbertGenerator(mBA).
Nous avons ensuite refait les mesures des questions précédentes :
1. Nombre de noeuds et arêtes.
2. Degré moyen et distribution.
3. Coefficient de clustering.
## Résultats :
### Comparaison des trois réseaux
| Réseau | n | m | \<k> | Clustering C | Distance moyenne |
| :----: | :-----: | :---------: |:---:| :-----------: | :--------------: |
| DBLP | 317 080 | 1 049 866 | 6.62 | 0.6324 | 6.7948 |
| ER | 317 087 | 1 048 902 | 6,61 | 0,000024 | 9.1 |
| BA | 317 082 | 634110 | 3,99 | 0,000184 | 7.8 |
## Analyse :
1. ER :
Clustering quasi nul, distance moyenne plus élevée et ne reproduit pas les caractéristiques de DBLP.
2. BA :
Distance moyenne proche de DBLP → petit monde, et Clustering beaucoup plus faible que DBLP → les hubs n’augmentent pas suffisamment le clustering.
3. Distribution des degrés :
. ER suit une loi de Poisson.
. BA suit une loi de puissance (γ≈3), reproduisant la queue lourde de DBLP mais avec moins de clustering.
## Conclusion :
1. DBLP est un réseau petit monde avec loi de puissance et clustering élevé.
2. BA capture la loi de puissance et les distances moyennes, mais pas le clustering.
3. ER capture seulement les distances moyennes (si n grand), mais pas la loi de puissance ni le clustering.
4. Les modèles génératifs permettent d'approximer certaines caractéristiques, mais aucun modèle simple ne reproduit parfaitement toutes les propriétés du réseau réel.