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.
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 ?
• Le coefficient de clustering de ce graphe est :0.6324308280637396
• Le coefficient de clustering pour ce réseau aléatoire de la même taille et de même degré moyen est :2.0884599814397534E-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-il connexe ? Oui
• Un réseau aléatoire de la même taille et degré moyen sera-t-il connexe ?
=>Non,puisque <d>=6.62208890914917<ln(317080)=12.666909387, càd le degré moyen <ln(le nb des nœuds).
• À partir de quel degré moyen un réseau aléatoire avec cette taille devient connexe ?
=>Le degré moyen à partir de ln(317080)=12.666909387
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 :
On a calculé la distribution des degrés et la stockée dans le fichier ‘dd_dblp.dat’.
Cela nous indique que la distribution de dégrés en calculant par pk=Ck−γ .Et les points violets correspondent beaucoup plus à cette ligne droite qui suit la loi de puissance qu'à la courbe "Poisson law" qui suit la loi de poisson .Càd notre reseaux suit la loi de puissance et ne suit pas la 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.
• L'hypothèse des six degrés de séparation se confirme-t-elle ?
=>Non,puisqu’on obtient la distance moyenne avec 1000 sommets choisis au hasard est égale à 6.764623877254952 un peu près > 6.
=>Non,on va comparer les valeurs <d>(6.700611818856679), lnN/ln<k>(6.764623877254952) si les deux valeurs sont presque,càd 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 ?
=>on la calcule avec la formule (lnN)/(ln<k>)=6.700611818856679
• La distribution des distances:
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.
Le taux de propagation du virus(λ) = probabilité de transmission dans une unité de temps(β)/le taux pour redevenir susceptibles(µ) = (1./7)/(1./15) = 2.142857142857143,puisque un individu envoie en moyenne un mail par semaine à chacun de ses collaborateurs,donc β = 1./7,et 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.
Le seuil épidémique $`λ_c = \frac{\langle k \rangle}{\langle k^{2} \rangle}`$ = 0.045984724362225844
• Le seuil théorique d'un réseau aléatoire du même degré moyen ?
Le seuil d'un réseau aléatoire du même degré moyen $`λ_c = \frac{1}{k+1}`$ = 0.13119762993051035
• Si on ne fait rien pour empêcher l'épidémie,cet épidémie va propager vite.
• Pour l'immunisation aléatoire,le nombre d'infectation est environ 1/3 des nombres total pendant 3 mois.
• Pour l'immunisation sélective,je l'ai simulez plusieurs fois,la pluspart du temp est plus efficace que l'immunisation alétoire