Newer
Older
# Mesures de réseaux d'interaction
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.
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.
**DONE**
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 ?
Coefficient de clustering: 0.6324308280637396
Nombre de nœuds: 317080
Nombre de liens: 1049866
Pour un réseau aléatoire de la même taille et du même degré moyen, le coefficient de clustering est de degré moyen / nombre de nœuds soit environ 1.04E-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 ?
D’après la méthode isConnected de Toolkit, on sait que le réseau est connexe. En revanche, le réseau aléatoire ne l’est pas. Pour être sûr que le réseau aléatoire soit connexe il doit être complet donc le degré moyen doit être du nombre de nœuds -1.
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 :
```math
p_k = C k^{-\gamma}
```
On utilise ce [script](/gnuplot/plot_dd.gnu) pour tracer la distribution et estimer l'exposant de la loi de puissance.
On a $`\gamma = 2.7 \pm 0.04`$
Oui, nous pouvons observer une ligne droite dans le graph en mode log-log. La probabilité qu’un sommet possède peu de voisins est beaucoup plus élevée que la probabilité qu’un sommet possède beaucoup de voisins. La loi de poisson est presque identique à la ligne tracée grâce à la distribution de degré. On peut donc dire que la distribution de degré suit une loi de poisson.
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.
**TODO**
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 ?
**TODO**
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.
**DONE**
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 :
* 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.
Nous sommes dans un modèle SIS, le taux de propagation du virus est donc calculé par beta / mu. Dans notre cas, une personne envoie en moyenne 1 mail par semaine donc 1/7 et un individu met à jour son antivirus 2 fois par mois donc 1/14. On a donc (1/7)/(1/14) = 2. Dans notre réseau, grâce au TP précédemment nous avons trouvé que le degré moyen du réseau est d’environ k = 3.31. Le seuil épidémique du réseau est donc égale à environ : 6.62 / 1.39E7 = 4.76E-7. Le seuil théorique d’un réseau aléatoire est égal à 1/(<k>+1), dans notre cas cela nous donne environ, 1/(6.62+1) = 0,13. Dans les deux cas, le taux de propagation est supérieur aux deux seuils épidémiques. Donc la maladie persiste dans un réseau aléatoire comme dans le réseau actuel.
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).
3. 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.
La simulation de l’immunité sélective est beaucoup plus efficace que le reste des simulations. On peut tout de même voir que la courbe est la même pour chaque simulation, la différence est dans le nombre de cas.
4. Pour justifier l'efficacité de l'immunisation sélective, calculez le degré moyen des groupes 0 et 1. Comment expliquez-vous la différence ?
Groupe 0 : 6.595488446406356
Groupe 1 : 9.357999151283684
La différence vient du fait que le groupe 1 possède un degré moyen plus élevé que le groupe 0, ce qui rend l’immunisation plus efficace. Ils ont plus de chance de pouvoir ralentir la propagation du virus.
5. 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.
Il y a une grosse différence entre le seuil initial qui est de environ 4.76E-7 et le seuil épidémique de la simulation 2 et 3 qui est environ 0.085. On peut voir qu’avec ces simulations on se rapproche grandement du taux de propagation du virus. Ce qui montre une réelle évolution dans la propagation du virus à travers le réseau. Cela indique bien que le nombre d'infection dans ces simulations est bien inférieur au aux nombres d’infection dans le réseau initial.
6. 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.
On peut voir lors des différentes simulation avec un réseau aléatoire et un réseau Barabàsi-Albert que schéma reste le même que pour le réseau scientifique. La première simulation dans les 3 cas possède le même schéma, la propagation du virus est très rapide et beaucoup d’individus sont infectés. Dans la deuxième simulation, on immunise le groupe 0, la propagation du virus diminue par rapport à la première simulation. Enfin pour la troisième simulation, on immunise le groupe 1 et la propagation du virus diminue par rapport à la deuxième simulation. L’immunisation sélective dans ces 3 réseaux est plus efficace que les deux autres immunités. Le degré moyen est plus élevé lorsqu’on immunise le groupe 1. Ce qui permet de ralentir la propagation considérablement la propagation du virus.
**On peut voir les différents graphes dans le fichier gnu/SimulationPropagation.**