Newer
Older
L'objectif de ce projet est d'analyser un réseau de collaboration scientifique en informatique extrait de **DBLP** (disponible sur [SNAP](https://snap.stanford.edu/data/com-DBLP.html)).
Nous allons calculer certaines mesures de base pour comprendre la structure du réseau et comparer ses caractéristiques à celles d'un graphe aléatoire équivalent.
GraphStream permet de mesurer de nombreuses caractéristiques d'un réseau. La plupart de ces mesures sont implantées comme des méthodes statiques dans la classe [TOOLKIT](https://graphstream-project.org/gs-algo/org/graphstream/algorithm/Toolkit.html). Elles vous seront très utiles par la suite.
On cherche à savoir si le graphe importer soit un réseau aléatoire et si non les différences entre un réseau aléatoire
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
1. Commencez par télécharger les données et les lire avec GraphStream. GraphStream sait lire ce format. Voir FileSourceEdge et ce tutoriel. Vous pouvez essayer de visualiser le graphe mais pour cette taille ça sera très lent et très peu parlant.
#### Résultat
Le fichier est un txt contenant les valeurs d'un graphe, pour l'ouvrir on utilise la fonction [getTheFileEdge(path)](src/main/java/org/example/GraphManipulation.java), qui lit chaque arête du fichier, crée automatiquement les nœuds correspondants si nécessaire et construit un objet Graph complet dans GraphStream.
Limite : l'affichage du graphe est lent, pause problème car les nodes sont pas instannément crée mais nous sera pas utile dans notre cas.
Le [fichier](src/main/resources/com-dblp.ungraph.txt) qu'on utilise contient l'ensemble des arretes .
- Chaque ligne représente une connexion entre deux nœuds
- Format : `FromNodeId ToNodeId`
- Les nœuds sont créés automatiquement si nécessaire
---
2. Prenez quelques mesures de base: nombre de nœuds et de liens, degré moyen, coefficient de clustering. Quel sera le coefficient de clustering pour un réseau aléatoire de la même taille et du même degré moyen ?
#### Résultat
Nous avons pris les mesures suivantes :
- Nombre de nœuds
- Nombre d'arêtes
- Degré moyen
- Coefficient de clustering
Pour trouver le coefficient de clustering attendu pour un graphe aléatoire, on utilise la formule pour un graphe Erdős–Rényi :
(Degré moyen) / (Nombre de nœuds - 1)
#### Mesure
| Mesure | Valeur |
| -------------------------------------------- | ---------------------------------- |
| Nombre de nœuds | 317 080 |
| Nombre d'arêtes | 1 049 866 |
| Degré moyen | 6.62208890914917 |
| Coefficient de clustering réel | 0.6324308280637396 |
| Coefficient attendu pour un graphe aléatoire | 2.088466568000142E-5 =0.0000208847 |
---
- Le graph est non orienté : car dans le fichier.txt, il y a Undirected graph. Qu'on a en plus vérifié avec une méthode isOrientedGraph(Graph g).
- Le **degré moyen** indique qu’un chercheur collabore en moyenne avec ~6 à 7 autres chercheurs.
- Le **coefficient de clustering réel** est très élevé environ = 0,632, ce qui montre que les collaborateurs d’un chercheur sont eux-mêmes souvent connectés, formant des communautés.
- Le **coefficient attendu pour un graphe aléatoire** est très faible, ce qui confirme que la structure réelle du réseau est loin d’être aléatoire et présente des communautés bien définies.
---
3. Le réseau est-il connexe ? Un réseau aléatoire de la même taille et degré moyen sera-t-il connexe ? À partir de quel degré moyen un réseau aléatoire avec cette taille devient connexe ?
#### Résultat
Pour notre réseau, il est **connexe**.
Nous avons vérifié cela avec la fonction [isConnexe](src/main/java/org/example/GraphManipulation.java), qui parcourt toutes les arêtes, ajoute les nœuds atteignables dans un ensemble (`Set`) et compare la taille de cet ensemble au nombre total de nœuds du graphe.
Pour qu’un **réseau aléatoire** soit connexe, il faut que le **degré moyen** soit supérieur à ln(Nombre de nœuds).
- Nombre de nœuds : 317080
- Degré moyen du réseau étudié : 6.62208890914917
- ln(317080) = 12.66691
On trouve donc:
6.62208890914917 < 12.66691 .
Le degré moyen actuel n’est pas suffisant pour garantir la connexité d’un graphe aléatoire de la même taille.
#### Commentaire
- Notre graphe réel est connexe, mais il **n’est pas un graphe aléatoire**.
- Pour qu’un graphe aléatoire de cette taille soit connexe, le degré moyen devrait être supérieur à **12.66691** (soit ln(Nombre de nœuds).
---
4. Calculez la distribution des degrés et tracez-la avec gnuplot (ou avec votre outil préféré) d'abord en échelle linéaire, ensuite en échelle log-log. Est-ce qu'on observe une ligne droite en log-log ? Que cela nous indique ? Tracez la distribution de Poisson avec la même moyenne pour comparaison. Utilisez la commande fit de gnuplot pour trouver les coefficients de la loi de puissance et tracez-la.
#### Rappel
- Tracé linéaire : distribution décroissante avec beaucoup de nœuds de petit degré.
- Tracé log-log : distribution approximativement linéaire, indiquant une loi de puissance.
- loi puissance : la probabilité qu’un nœud ait un degré k.
- fit Gnuplot pour estimer l’exposant 𝛾 de cette loi de puissance.
- 𝛾 = il caractérise la décroissance de la distribution des degrés et permet de mesurer l’hétérogénéité du réseau.
#### Résultat
La distribution de degrés pk=Nk/N est la probabilité qu'un nœud choisi au hasard ait degré kkk. On peut utiliser [Toolkit.degreeDistribution()](<"https://data.graphstream-project.org/api/gs-algo/current/org/graphstream/algorithm/Toolkit.html#degreeDistribution(org.graphstream.graph.Graph)">) pour obtenir Nk et normaliser par la suite :
```java
int[] dd = Toolkit.degreeDistribution(graph);
for (int k = 0; k < dd.length; k++) {
if (dd[k] != 0) {
System.out.printf(Locale.US, "%6d%20.8f%n", k, (double)dd[k] / graph.getNodeCount());
}
}
```
En traçant la distribution de degrés en échelle log-log on observe une ligne droite pendant plusieurs ordres de grandeur. Cela nous indique une loi de puissance :
pk=Ck^−γ
On utilise ce [script](src/main/gnuplot/plot_dd.gnu) pour tracer la distribution et estimer l'exposant de la loi de puissance.
On a gamma = 2.7 ±0.04
#### Commentaire
1. Courbe DBLP (données réelles)
- En log-log, la distribution est presque une droite sur plusieurs ordres de grandeur.
- En échelle linéaire, la distribution décroît rapidement, montrant que la plupart des nœuds ont peu de liens.
2. Courbe Poisson (réseau aléatoire)
- Elle est étroite et symétrique, avec peu de nœuds ayant un degré très élevé.
- Distribution qui ne reproduit pas les hubs observés dans le réseau réel.
3. Courbe Power law (ajustement)
- En log-log, elle suit presque parfaitement la droite des données réelles.
Le fit est satisfaisant, et l’exposant γ≈2.7 peut être utilisé pour caractériser la loi de puissance du réseau DBLP. Cela confirme que le réseau est hétérogène et possède des hubs.
---
5. Maintenant on va calculer la distance moyenne dans le réseau. Le calcul des plus courts chemins entre toutes les paires de nœuds prendra plusieurs heures pour cette taille de réseau. C'est pourquoi on va estimer la distance moyenne par échantillonnage en faisant un [parcours en largeur](https://graphstream-project.org/gs-core/org/graphstream/graph/BreadthFirstIterator.html) à partir de 1000 sommets choisis au hasard. L'hypothèse des six degrés de séparation se confirme-t-elle ? Est-ce qu'il s'agit d'un réseau petit monde ? Quelle sera la distance moyenne dans un réseau aléatoire avec les mêmes caractéristiques ? Tracez également la distribution des distances. Formulez une hypothèse sur la loi de cette distribution.
#### Application
Pour estimer la distance moyenne dans le réseau, le calcul exact des plus courts chemins entre toutes les paires de nœuds aurait été trop coûteux en temps de calcul pour un réseau de cette taille. Nous avons donc procédé à une estimation par échantillonnage : un parcours en largeur (Breadth-First Search) a été réalisé à partir de 1000 nœuds choisis aléatoirement.
Et fait la [probabilité pour chaque distance](src/main/gnuplot/averageDistanceOf1000Node.dat) (en excluant 0).
Cela est représenté par les fonctions [getDistanceProbabilities & getAverageDistanceOfNNode](src/main/java/org/example/GraphManipulation.java) qui permettent d'obtenir un dictionnaire d'occurence de la distance et la distance moyenne sur une selection de N points choisis aléatoirement.
#### Résultat
Le résultat obtenu est le suivant :
- Distance moyenne=6.7996460629685345 ≈6,80
Répartion probabilité :
Cette valeur est proche de l’hypothèse des six degrés de séparation, selon laquelle la distance moyenne entre deux individus dans un réseau social est d’environ six. Cette observation suggère que le réseau étudié possède des caractéristiques typiques d’un réseau petit monde( distances moyennes relativement faibles malgré un grand nombre de nœuds)
N=317080 et un degré moyen ⟨k⟩=6,62208890914917, la distance moyenne attendue serait de :
- Lrand = ln(N) / ln(k)
- Lrand = ln (317080) / ln(6,62208890914917)
- 6.70 ≈ 12,66691 / 1,890
Pour notre réseau ou un réseau aléatoire, la distribution des distances est centrée autour de la distance moyenne ~6,8 et ~6.7 et décroît rapidement pour les distances plus grandes. Cela suggère que la plupart des nœuds sont proches les uns des autres, ce qui est typique d’un réseau petit monde. On peut donc hypothétiser que cette distribution suit une loi exponentielle décroissante.
6. Utilisez les générateurs de GraphStream pour générer un réseau aléatoire et un réseau avec la méthode d'attachement préférentiel (Barabasi-Albert) qui ont la même taille et le même degré moyen. Refaites les mesures des questions précédentes pour ces deux réseaux. Les résultats expérimentaux correspondent-ils aux prédictions théoriques ? Comparez avec le réseau de collaboration. Que peut-on conclure ?
---
- 7 (Question bonus) S'il y a une caractéristique du réseau de collaboration que le modèle de Barabasi-Albert n'arrive pas à reproduire c'est le coefficient de clustering. Est-ce qu'on peut espérer faire mieux avec une variante de la méthode de copie :
- Le nouveau nœud choisit au hasard un nœud v.
- Ensuite il parcourt tous les voisins de v et se connecte à eux avec probabilité p.
- À la fin il se connecte à v
Essayez d'implanter un tel générateur et voir les résultats qu'il donne.
```
cd existing_repo
git remote add origin https://www-apps.univ-lehavre.fr/forge/mh252189/iwocs_tp_molinier.git
git branch -M main
git push -uf origin main
```
## Description
## Project status
En Cours