Newer
Older
- On a commencé par telecharger et lire les données par readAll du classe FileSourceEdge() de GraphStream.
- Nombre de nœuds : 317080
- Nombre de liens : 1049866
- Le degré moyen : 6.62208890914917
- Coefficient de clustering : 0.6324308280637396
- le coefficient de clustering pour un réseau aléatoire de la même taille est : < K >/N = 6.62/317080 = 2.08780118582E-5
- Est ce que le graphe est connexe : true
- Un réseau aléatoire de la même taille et degré moyen n'est pas connexe
- Dans un régime connecté le degré < k > doit etre supérieur à ln(N) avec N le nombre de noeuds du graphe.
Dans notre cas : ln(N) = ln(317080) = 12.66 donc le degré moyen doit etre superieur a 12.66 pour que le réseau aléatoire devient connexe.
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 pk=NkNp_k = \frac{N_k}{N}pk=NNk est la probabilité qu'un nœud choisi au hasard ait degré k.
pour calculer la distribution des degres, on a crée une méthode distributionDegre() qui permet de calculer la probabilité qu’un noeud choisi au hasard ait degré k, en utilisant la fontion
Toolkit.degreeDistribution(graph) et qui renvoie un tableau où les indices représentent les degrés, et les valeurs de representent le nombre de noeud de ce degré.
On a crées apres un fichier texte ou chaque ligne représente la probabilité qu'un noeud choisi au hasard ait degré k.
- On a γ=2.7±0.04
- Distribution des degrés en echelle linéaire :
- Distribution des degrés en echelle log :
- 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 :
Cela nous indique une loi de puisance de : pk=Ck−γ
- Distribution de poisson, de puissance :
5. Distribution des distances :
- La valeur de la distance moyenne obtenue est : 6.760441774946385
L'hypothèse des six degrés de séparation se confirme et la distance entre deux noeuds choisis au hasard est courte car,
la distance moyenne est égale à ln(N)/ln(k) = ln(317080)/ln(6.6220889) = **6.700611819**
Par déduction, le réseau s'agit bien d'un petit monde
Un réseau généré aléatoirerment avec les memes caracteristiques a un peu près la meme distance moyenne : **6.903640794874903**
6. Reseau aleatoire et réseau Barabasi
- Les mesures faites sur un réseau aléatoire et un graphe généré avec la méthode d'attachement préférentiel (Barabasi-Albert)
- pour le reseaux aleatoir Les résultats expérimentaux correspondent aux prédictions théoriques calculées ci_dessus dans les questions précedentes.
- la coefficient de clustering du reseau de barbasie et la distance moyenne sont plus petites que celles du reseau aleatoire
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
# Rapport du TP de propagation dans des reseaux
1. Le taux de propagation, Le seuil épidémique du réseau, le seuil théorique d'un réseau aléatoire:
- Le taux de propagation du virus λ = β/υ avec β est probabilité de transmission dans une unité de temps
- Un individu envoie en moyenne un mail par semaine à chacun de ses collaborateurs alor β = 1/7
- Un individu met à jour son anti-virus en moyenne deux fois par mois alors υ = 1/14
- Lamda = B/U = 14/7 =2
- Le seuil épidémique du réseau λc = 〈k〉/〈k²〉 avec 〈k〉le moyen et 〈k²〉la dispersion des degrés:
- λc = 6.62208890914917 / 144.00627601867038 = 0.04598472436222584
- Le seuil théorique d'un réseau aléatoire du même degré moyen λc = 1 /〈k〉+ 1 = 0.13119762993051035
- Le seuil epidemique de notre reseau est plus petit que le seuil epidemique du reseau aleatoire
2. Simulations des scenarios du virus:
- Scenario 1 on ne fait rien pour empêcher l'épidémie on obtient un graph de de la fraction d'infectés de la population non immunisée comme suit:
- 
- On ramarque que le virus se propage de maniere importante dans les 20 premiers jours et apres devient presque constant a une valeur de 266000 infections
- Scenario 2 On réussit à convaincre 50 % des individus de mettre à jour en permanence leur anti-virus on obtient un graph de de la fraction d'infectés de la population non immunisée comme suit:
- 
- Sn ramarque que le virus se propage dans les 20 premiers jours jusqu'a atteindre la valeur 80000 infections apres devient presque constant
- Scenario 3 On réussit à convaincre 50 % des individus de convaincre un de leurs contacts de mettre à jour en permanence son anti-virus on obtient un graph de de la fraction d'infectés de la population non immunisée comme suit:
- 
- On ramarque que le virus se propage dans les 60 premiers jours jusqu'a atteindre la valeur 30000 infections apres devient presque constant
3. Le degré moyen des groupes 0 et 1:
- Le degre moyen du groupe 0(le noeud choisi au hasard) est : 6.593056167054532
- Le degre moyen du groupe 1(les voisins du noeud choisi au hasard) est : 18.5238757154538
- La difference entre le degré moyen des groupes 0 et 1 s'explique car quand on choisie un noeuds au hasard, il a peu de chance d'etre un "hub", mais quand on immunise au hasard un de ses voisins, son voisin a plus grande chance d'être un "hub".
4. Le seuil épidémique du réseau modifié:
- le seuil épidémique du réseau modifié (scenario 2: immunisation aléatoire) = 〈k〉/〈k²〉= 6.62135683774146 / 142.87975831957763 = 0.04634216151829947
- le seuil épidémique du réseau modifié (scenario 3: immunisation sélective) = 〈k〉/〈k²〉= 5.949799564407689/ 63.284732173858146 = 0.0940163505482204
- On comparant ces seuil avec le seuil du reseau initiale on remarque que le seuil epidemique du reseau modifie avec immunisation aléatoire est presque le meme du reseau initiale mais le seuil epidemique du reseau modifie avec immunisation sélective est plus grand que le seuil epidemique initiale.
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:
- Scenario 1:
- 
- On remarque que les trois reseau ont presque les mêmes résultats (260000 d'infections)
- Scenario 2 :
- 
- On remarque que le reseau initial a moins de contaminé que les 2 autres reseaux.
Le réseau initial et preferentiel deviennent assez rapidement constant tandis que le réseau aléatoire met un peu plus
de temps à se propager mais infecte beaucoup plus de personnes.
- 
- On remarque que le réseau initial est le réseau le moins infecté. Tandis que Le réseau aléatoire et le réseau initial sont très efficaces et contamine beaucoup le réseaux.