Newer
Older
Nous allons analyser un réseau de collaboration scientifique en informatique. Le réseau est extrait de DBLP et disponible sur [SNAP](https://snap.stanford.edu/data/com-DBLP.html).
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://data.graphstream-project.org/api/gs-algo/current/org/graphstream/algorithm/Toolkit.html). Elles vous seront très utiles par la suite.
> **Note : les résultats affichés sont approximatifs, mais les calculs ont bien été réalisés avec les valeurs réelles calculées par GraphStream.**
1. Commencez par télécharger les données et les lire avec GraphStream. GraphStream sait lire ce format. Voir [`FileSourceEdge`](https://data.graphstream-project.org/api/gs-core/current/org/graphstream/stream/file/FileSourceEdge.html) et ce [tutoriel](http://graphstream-project.org/doc/Tutorials/Reading-files-using-FileSource/). Vous pouvez essayer de visualiser le graphe mais pour cette taille ça sera très lent et très peu parlant.
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 ?
| Donnée | Valeur approximative |
|-----------------------------------------|----------------------|
| Nombre de noeuds ($N$) | 317080 |
| Nombre de liens ($L$) | 1049866 |
| Degré moyen ($`\langle k \rangle`$) | 6.62208890914917 |
| Coefficient moyen de clustering ($C_i$) | 0.6324308280637396 |
Pour un réseau aléatoire, le coefficient moyen de clustering est $`C_i = p = \cfrac{\langle k \rangle}{N}`$, soit $`C_i \approx \cfrac{6.622}{317080} \approx \boxed {2.088e^{-5}}`$
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 ?
Le réseau est connexe.
Pour un réseau aléatoire, le régime connecté s'atteint lorsque $`\langle k \rangle > \ln N`$.
Ici, $`\langle k \rangle \approx 6.622`$ et $`\ln N \approx 12.667`$, donc le régime n'est pas atteint. Cela signifie qu'un réseau aléatoire de la même taille et de même degré moyen ne sera pas forcément connexe.
Le degré moyen à atteindre pour n'avoir que des réseaux connexes est donc $`\langle k \rangle \gtrapprox 12.667`$.
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.
La distribution de degrés $`p_k = \frac{N_k}{N}`$ est la probabilité qu'un nœud choisi au hasard ait degré $`k`$. 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 $`N_k`$ 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 :
On utilise ce [script](/gnuplot/plot_dd.gnu) pour tracer la distribution et estimer l'exposant de la loi de puissance.
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 à 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.
Avec la fonction `getAverageDistance`, je calcule la distance moyenne : $`\langle d \rangle \approx 6.75`$
$`\langle d \rangle > 6`$ donc l'hypothèse des six degrés de séparations n'est pas validée avec cette approximation.
Pour vérifier qu'il s'agit d'un petit monde, on doit vérifier que $`\langle d \rangle \approx \cfrac{\ln N}{\ln \langle k \rangle}`$ :
$`\cfrac{\ln N}{\ln \langle k \rangle} \approx \cfrac{\ln 317080}{\ln 6.62208890914917} = 6.70061181886`$
Avec une différence d'environ 0.05, $`\langle d \rangle \approx \cfrac{\ln N}{\ln \langle k \rangle}`$. J'estime donc que ce graphe représente un petit monde.
D'ailleurs, pour un réseau aléatoire, la distance moyenne correspond à cette valeur.
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 ?
| | Graphe aléatoire | Barabàsi-Albert |
|----------------------------------------|------------------|-----------------|
| Nombre de noeuds ($N$) | 102 | 102 |
| Nombre de liens ($L$) | 344 | 344 |
| Degré moyen ($L$) | 6.75 | 6.75 |
| Coefficient de clustering ($C_i$) | 0.000084 | 0.00001 |
| Distance moyenne ($\langle d \rangle$) | 2.63 | 2.5 |
| Est connexe ? | Non | Oui |
Distribution des degrés pour le graphe de Barabàsi-Albert :
Distribution des distances pour le graphe aléatoire :
Distribution des distances pour le graphe de Barabàsi-Albert :
- Le réseau de collaboration est très structuré : fort clustering, régime de petit monde et loi de puissance.
- Le modèle Barabási-Albert reproduit certaines propriétés (loi de puissance, petite distance moyenne) mais pas le clustering élevé.
- Le réseau aléatoire n'imite pas du tout ces caractéristiques.
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.
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
* Taux d'infection ($\beta$) : 1 mail/semaine = $\frac{1}{7} \approx 0.143$ interactions par jour.
* Taux de nettoyage ($\mu$) : 2 mises à jour/mois = 1 mise à jour/2 semaines = $\frac{1}{14} \approx 0.067$ nettoyages par jour.
Le taux de propagation est de $\lambda = \frac{\beta}{\mu} = \frac{\frac{1}{7}}{\frac{1}{14}} = 2$
Le seuil épidémique est défini par $\frac{\beta}{\mu} > \frac{1}{\langle k \rangle}$, où $\beta$ est le taux d'infection, $\mu$ le taux de guérison, et $\langle k \rangle$ le degré moyen.
Le seuil épidémique est $\lambda_c = \frac{\langle k \rangle}{\langle k \rangle²} = \frac{1}{\langle k \rangle} \approx 0.151 $ en se basant sur un degré moyen $\langle k \rangle \approx 6.62$ comme dans le TP1.
Pour un réseau aléatoire de même taille et même $\langle k \rangle$, le seuil est de $\frac{1}{\langle k \rangle + 1} = \lambda_c \approx 0.131$, ce qui est plus 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.
On utilise ces paramètres à partir de la question 1 :
* $\beta = 0.143$ (taux d'infection par jour).
* $\mu = 0.067$ (taux de nettoyage par jour).
* Durée de simulation : 90 jours.
* Nombre de simulations par scénario : 20.
Déroulé de la simulation :
* On génère un graphe et on lui attribue un état initial.
* Simulation 1 : 0% des nœuds sont immunisés.
* Simulation 2 : 50% des nœuds sont immunisés.
* Simulation 3 : 50% des nœuds sont immunisés et un de leurs voisins également.
* Chaque jour (sur 90), pour chaque noeud on fait la chose suivante :
* Si le noeud est infecté, parmis ses voisins non immunisés, on infecte avec une probabilité $\beta$.
* Si le noeud est infecté, on le guérit avec une probabilité $\mu$.
* Il y a donc également une chance pour que rien ne se passe, ou qu'un ou les deux évènements se produisent, en tout logique.
Déjà, on voit clairement que le scénario 3 est extrêmement efficace pour contenir l'épidémie. Aucun infecté n'est à déplorer après 90 jours.
Le scénario 2 est également efficace, mais moins que le scénario 3. On observe une propagation de l'épidémie, mais elle est contenue.
Le scénario 1 est le pire des trois. L'épidémie se propage très rapidement et atteint un pic d'infectés après 90 jours.
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 ?
| Scénario | Degré moyen des nœuds non immunisés | Degré moyen des nœuds immunisés |
|----------|-------------------------------------|---------------------------------|
| 2 | 6.62 | 6.63 |
| 3 | 3,76 | 10,68 |
__Scénario 2 (immunisation aléatoire) :__
Les degrés moyens des nœuds immunisés et non immunisés sont proches, car la sélection des nœuds immunisés est indépendante de leur connectivité.
__Scénario 3 (immunisation sélective) :__
Le degré moyen des nœuds immunisés est bien plus élevé, car la stratégie cible préférentiellement les voisins des nœuds choisis, augmentant ainsi la probabilité d'immuniser des hubs (nœuds à fort degré). Cela réduit drastiquement la connectivité des non immunisés, ralentissant 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.
Pour un réseau modifié, le seuil épidémique est défini par $\lambda_c = \frac{\langle k \rangle}{\langle k^2 \rangle}$.
| Réseau | $`\langle k \rangle`$ | $`\langle k^2 \rangle`$ | $`\lambda_c`$ |
|------------------------|-----------------------|-------------------------|---------------|
| Initial | 6.62 | 75.48 | 0.0877 |
| Immunisation aléatoire | 6.55 | 71.32 | 0.0918 |
| Immunisation sélective | 1.80 | 16.30 | 0.1104 |
**Analyse**
- **Réseau initial** : Faible seuil épidémique, propice à la propagation du virus.
- **Immunisation aléatoire** : Augmente légèrement $`\lambda_c`$ mais reste peu efficace.
- **Immunisation sélective** : Augmente fortement $`\lambda_c`$, car la suppression des hubs réduit la connectivité globale et la dispersion des degrés $`\langle k^2 \rangle`$. Cela limite significativement la propagation du virus.
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.
Je peux conclure certaines choses, d'après mes résultats :
- la propagation, peu importe le scénario est très similaire (dans sa forme) pour un réseau de Barabasi-Albert par rapport au réseau de base.
- pour un graphe aléatoire, le scénario 3 est moins efficace, car les hubs sont moins présents dans un réseau aléatoire. Il se rapproche du scénario 2.