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
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
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 ?
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#### Application
On utilise donc les générateurs de GraphStream pour générer [un réseau aléatoire](https://graphstream-project.org/doc/Generators/Random-graph-generator/) et [un réseau avec la méthode d'attachement préférentiel](https://graphstream-project.org/doc/Generators/Barabasi-Albert-Preferential-Attachment-generator/) (Barabasi-Albert)
Avec [ces méthodes](src/main/java/org/example/GraphGenerator.java) on renseigne le nombre de noeud et le degré moyen.
Une particularité pour l'algorithme de Barabasi-Albert est qu'il ne prend pas degré moyen maisle nombre de liens par nouveau nœud (linksPerNewNode). Pour que le graphe ait un degré moyen approximatif k, il faut donc définir :linksPerNewNode ≈ degréMoyen / 2
car chaque arête contribue au degré de deux nœuds.
#### Mesures obtenues
| Graphe | Arêtes | Degré moyen | Clustering | Distance moyenne |
| --------------- | --------- | ----------- | ---------- | ---------------- |
| DBLP (réel) | 1 049 866 | 6.62 | 0.632 | 6.80 |
| Random | 1 051 093 | 6.63 | 1.33e-5 | 6.91 |
| Barabasi-Albert | 634 760 | 4.00 | 2.26e-4 | 6.19 |
Obtenue avec ce script:
[Script Gnuplot](src/main/gnuplot/averageDistanceProbaTree.gnu) (en excluant 0).
### En Conclusion
L’analyse des réseaux montre que les résultats expérimentaux confirment en grande partie les prédictions théoriques. Le réseau aléatoire présente des distances conformes à ln(N)/ln(k) mais un clustering quasi nul, ce qui le rend très différent du réseau réel. Le modèle Barabasi-Albert montre des hubs et des distances moyennes plus faibles mais conserve un clustering faible.
Comparé au réseau réel DBLP, ce dernier combine un fort clustering et des hubs, typique d’un réseau social de collaboration scientifique. Aucun des modèles simples ne reproduit parfaitement toutes les caractéristiques observées
Le réseau DBLP n’est pas aléatoire et le modèle Barabasi-Albert capture certains aspects comme les hubs et les petites distances mais pas le clustering élevé.
### Limite
Le générateurs de GraphStream pour l'algorithme de Barabasi-Albert ne permet pas d'imposer un degré moyen et ne prend que un entier en paramètre. Pour la représentation j'ai essayé ay mieu d'avoir une distance moyenne similaire.
Nos collaborateurs scientifiques communiquent souvent par mail. Malheureusement pour eux, les pièces jointes de ces mails contiennent parfois des virus informatiques. On va étudier la propagation d'un virus avec les hypothèses suivantes :
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
Un individu envoie en moyenne un mail par semaine à chacun de ses collaborateurs.
Un individu met à jour son anti-virus en moyenne deux fois par mois. Cela nettoie son système mais ne le protège pas de nouvelles infections car le virus mute.
L'épidémie commence avec un individu infecté (patient zéro).
1. Quel est le taux de propagation du virus ? Quel est le seuil épidémique du réseau ? Comparez avec le seuil théorique d'un réseau aléatoire du même degré moyen.
### Application
Si on reprend les données des mesures faites sur le réseau DBLP dans le TP 1 qui représentait un réseau de collaboration scientifique en informatique.
Alors on avait un degré moyen du réseau d'environ : 6.622
Le modèle d’infection qui correspond à notre situation est un modèle SIS, car les individus peuvent être infectés, guéris par leur anti-virus et redevenir susceptibles d’être infectés à nouveau, sans immunité permanente.
La formule du seuil épidémique dans ce modèle est
- 
Donc le taux de propagation est = degre moyen × frequence quotidienne
- soit 6,622 * (1/7) ≈ 0,94
Le seuil épidémique pour le réseau réel DBLP est donc très faible.
---
2. Simulez la propagation du virus jour par jour pendant trois mois avec les scénarios suivants :
- On ne fait rien pour empêcher l'épidémie
- On réussit à convaincre 50 % des individus de mettre à jour en permanence leur anti-virus (immunisation aléatoire)
- On réussit à convaincre 50 % des individus de convaincre un de leurs contacts de mettre à jour en permanence son anti-virus (immunisation sélective).
Pour chacun des trois scénarios, tracez l'évolution de la fraction d'infectés de la population non immunisée. Que peut-on conclure ?
Attention : La réalisation d'un scénario autour des valeurs critiques est sensible aux conditions initiales. Simulez plusieurs fois chaque scénario afin d'identifier le déroulement typique.
### Application
Dans [script Java réalisant les scénarios](src/main/java/org/example/Main_TP2.java)
### Résultat
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
Obtenue avec ce script:
[Script Gnuplot](src/main/gnuplot/TP2/scenarioImmunisation.gnu).
### Analyse
on peut voir que chaqu'un des 3 scénario tent vers une valeurs:
- Le scénario 1 ( sans Immunisation ) : l’infection devient endémique en étant proche de 1 car Dans un SIS, lorsque
𝛽 (taux de propagation) > seuil épidémique , aucune fraction d’infection ne s’éteint naturellement et le virus persiste indéfiniment.
- Le scénario 2 ( Immunisation Aléatoire): l'infection peut etre proche de 0.5 en théorie. En pratique,la fraction observée est autour 0.3 - 0.35 car le réseau est hétérogène et fortement clusterisée. Les nœuds immunisés créent des barrières.
- Scénario 3 (immunisation sélective 50%) : en ciblant les voisins des nœuds choisis, on supprime préférentiellement les chemins critiques de propagation.
### En Conclusion
Le nombre de nœuds immunisés ne suffit pas à réduire une épidémie. La position des nœuds immunisés dans le réseau est tout aussi critique.
Cela montre que la topologie du réseau et la stratégie d’immunisation sont des facteurs déterminants pour contrôler efficacement la propagation d’un virus.
Cela permet de mieux comprendre pourquoi, lors de la pandémie de COVID‑19, la vaccination ciblée des populations les plus exposées et les mesures de confinement dans les zones à forte transmission ont été plus efficaces qu’une stratégie uniforme.
---
3. Pour justifier l'efficacité de l'immunisation sélective, calculez le degré moyen des groupes 0 et 1. Comment expliquez-vous la différence ?
### Application
Dans le cadre des scénarios, on rajoute à la simulation le calcul quotidien du degré moyen pour chaque groupe: immunisés et non immunisés. Qu'on calcule chaque jour Pour le scénario 2 et 3 . Le scénario 1 (sans immunisation) n’est pas pris en compte pour ce calcul, car l’ensemble des nœuds appartient à un seul groupe.
Le degré moyen est alors identique au degré moyen global du graphe.
### Résultat
Obtenue avec ce script:
[Script Gnuplot](src/main/gnuplot/TP2/plot_averageDegreeByImmunity.gnu).
### Conclusion
Dans le cas de l’immunisation aléatoire, les nœuds immunisés et non immunisés présentent un degré moyen identique, proche de celui du graphe global (environ 6). Cela est attendu, car la sélection des individus immunisés est uniforme et indépendante de leur position dans le réseau. L’immunisation aléatoire ne cible donc pas spécifiquement les nœuds les plus connectés, et la structure du réseau reste globalement inchangée du point de vue des connexions.
En revanche, dans le scénario d’immunisation sélective, une forte différence apparaît entre les deux groupes. Les nœuds immunisés ont un degré moyen élevé (environ 11,5), tandis que les nœuds non immunisés ont un degré moyen nettement plus faible (environ 4). Cette différence s’explique par le fait que la stratégie sélective tend à immuniser des nœuds fortement connectés (les hubs du réseau), qui jouent un rôle central dans la propagation du virus.
---
4. Du point de vue du virus l'immunisation d'un nœud est équivalente à sa suppression du réseau. Calculez le seuil épidémique du réseau modifié pour chacune des deux stratégies d'immunisation et comparez avec le seuil épidémique du réseau initial.
### Application
| Réseau | ⟨k⟩ | ⟨k²⟩ | Seuil λc |
| --------- |-------|------------------------| ---------- |
| Initial | ≈ 6.6 | Très grand | ≈ 0 |
| Random | ≈ 6.6 | Grand(20.04) | **0.3306** |
| Selective | ≈ 6.8 | Fortement réduit(47.8) | **0.1422** |
Du point de vue du virus, l’immunisation équivaut à la suppression de nœuds du réseau. L’immunisation aléatoire conserve la structure hétérogène du réseau et n’affecte que modérément le seuil épidémique. En revanche, l’immunisation sélective supprime préférentiellement les nœuds les plus connectés, réduisant fortement la connectivité effective et fragmentant le réseau. Même si le seuil théorique reste non nul, la disparition des hubs rend la propagation du virus beaucoup moins efficace, ce qui explique l’extinction observée en simulation.
---
5. Simulez l'épidémie avec les mêmes hypothèses et les mêmes scénarios dans un réseau aléatoire et un réseau généré avec la méthode d'attachement préférentiel de la même taille et le même degré moyen. Comparez et commentez les résultats.
- DBLP : 
- Random : 
- BarabasiAlbert : 
Degré Moyen (Immunisé / Non Immunisé)
### Conclusion
Les simulations montrent que la propagation de l’épidémie dépend fortement de la structure du réseau. Dans un réseau aléatoire, l’immunisation aléatoire est efficace car les nœuds ont des degrés similaires. En revanche, dans les réseaux hétérogènes (DBLP ou Barabási–Albert), l’immunisation aléatoire est peu efficace car elle ne cible pas les hubs. L’immunisation sélective permet au contraire de neutraliser préférentiellement les nœuds de fort degré, ce qui réduit fortement la propagation, voire provoque l’extinction de l’épidémie.
Avec l'observation des degré moyen on peut voir
- Sur DBLP/BA : Il y a un fossé énorme. Les immunisés ont un degré gigantesque (ce sont les hubs). Le reste du réseau (non-immunisés) s'effondre à un degré très bas.
- Sur Random : L'écart existe mais est beaucoup plus faible, car il n'y a pas de nœuds "ultra-connectés" dans un réseau aléatoire classique.