Newer
Older
## 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 ?
```java
//Affichage des données sur le réseau
System.out.println("Le nombre des noeuds du graphe "+g.getNodeCount());
System.out.println("Le nombre des liens du graphe "+g.getEdgeCount());
System.out.println("Le degré moyen est : "+averageDegree(g));
System.out.println("Le coefficient de clustering est : "+averageClusteringCoefficient(g));
```
- Coefficient de clustering dans un reseau aleatoire de même taille et degré moyen : 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 connexe
- Un réseau aléatoire de la même taille et degré moyen ne sera pas connexe.
- Pour 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 qui est supérieur au degré qui égale à 6,62
## 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.
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−γ
On a γ=2.7±0.04\gamma = 2.7 \pm 0.04γ=2.7±0.04
- La distribution des degrés en echelle linéaire :
- La distribution des degrés en echelle log :
- Nous remarquons une ligne droite dans le graphe pour plusieurs ordres de grandeur.
On déduit donc que la distribution des degrés soit une loi de puissance.</br>
- La ditribution des degrés, loi de poisson et la loi de puissance :
En utilisant la commande fit, nous avons obtenu les coefficients de **f(x) = lc - gamma * x** :
**lc = 2.34298** et **gamma = 2.70556**
## 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.
Le code suivant permet de trouver l'estimation de la distance moyenne sur un échantillon de 1000 sommets
```java
double sommeDistances = 0;
int nbr=0;
//parcours en largeur
for(int i = 0 ; i < 1000 ; i++){
Node depart = randomNode(g);
BreadthFirstIterator it = new BreadthFirstIterator(depart);
while(it.hasNext()){
Node next = it.next();
sommeDistances += it.getDepthOf(next);
nbr++;
}
}
System.out.println("la distance moyenne est :"+(sommeDistances/nbr));
```
- 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**
D'après le graphe de distribution des distances, on déduit que cette dernère suit une <strong>loi binomiale</strong>
## 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 ?
Les mesures sont faites sur deux graphes : un généré aléatoirement et l'autre avec la méthode d'attachement préférentiel (Barabasi-Albert)
.png)
Comme nous pouvons le remarquer sur les résultats , le coefficient de clustering du graphe Barabasi est plus petit que de celui du graphe généré aléatoirement :
- Prédictions théoriques :
# TP Propagation dans des réseaux
## 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.
### Question 1 :
- Le taux de propagation : λ = β / μ
- β probabilité de transmission dans une unité de temps.
- μ est la probabilité que les individus infectieux guérissent pour redevenir susceptibles.
- Un individu envoie en moyenne un mail par semaine à chacun de ses collaborateurs, donc β = 1/7
- Un individu met à jour son anti-virus en moyenne deux fois par mois, donc μ = 1/14
- Alors λ = β / μ = (1/7) / (1/14) = 2
### Question 2 :
- Le seuil épidémique λc = < k > / < k2 >
- Le degré moyen < k > = 6.62208890914917
- < k2 > = 144.00627601867035 ( calculé en utilisant la méthode distributionDegres)
- λc = < k > / < k2 > = 0,0459847243671519
### Comparaison avec le seuil théorique d'un réseau aléatoire :
- Comparaison avec un réseau aléatoire de meme degré. **λc = 1 / < k > + 1**
- La valeur du seuil theorique :λc = 0,1312
- Le seuil théorique du réseau aléatoire est supérieur à celui de notre réseau.
## 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.
- **Scénario 1** : On fait une simulation de propagation du virus dans le réseau pendant une durée de 3 mois équivalente à 84 jours. La méthode **scénario1** faut une simulation de notre premier scénario,
qui consiste à ne rien faire pour empecher la propagation du virus. Pour cela, on prends un noeud patient 0 aléatoirement et on le rend infecté. Ensuite pendant 3 mois on simule une probabilité de 1/7 pour qu'un individu infecté passe le virus à un voisin (collaborateur) en lui envoyant un mail.
Hajar RAHMOUNI
a validé
Après, on simule une probabilité de 1/14 qu'un individu infecté met à jour son antivirus et soit guérit mais il restera toujours susceptible d'attraper encore une fois le virus.<br>
Hajar RAHMOUNI
a validé
- On constate que si on ne fait rien pour empêcher l'épidémie, le virus se propage tres rapidement dans notre réseau.<br>
- **Scénario 2** : On fait une simulation de propagation du virus dans le cas ou on immunise 50% de notre réseau. La méthode scénario2 fait une simulation du 2éme scénario, on prend au hasard 50% des noeuds du réseau et on les immunise, on choisit aléatoirement un patient 0 et on l'infecte avec le virus.
Hajar RAHMOUNI
a validé
Ensuite, pour une probabilité de 1/7, un individu non immunisé et infecté passe le virus à ses voisins(la moitié du réseau est immunisée -> ils ne peuvent pas etre infectés), de meme un individu infecté (non immunisé) peut guérir avec une probabilité de 1/14. <br>
Hajar RAHMOUNI
a validé
- On constate que si on immunise la moitié de notre réseau de collaboration, le virus se propage un peu moins qu'en premier cas.<br>
- **Scénario 3** : On fait une simulation de propagation du virus dans le cas ou on arrive à convaincre un de leurs contacts de mettre à jour en permanence son anti-virus (immunisation sélective.
La méthode **scenario3** fait la simulation de ce scénario. Pour cela, on prend aléatoirement pour chaque individu un voisin de celui ci et on l'immunise.
Hajar RAHMOUNI
a validé
Ensuite, pour une probabilité de 1/7, un individu non immunisé et infecté passe le virus à ses voisins, de meme un individu infecté (non immunisé) peut guérir avec une probabilité de 1/14.<br>
Hajar RAHMOUNI
a validé
- On déduit qu'avec ce type d'immunisation, le virus se propage très lentement. Donc l'immunisation sélective est plus efficace que la précedente.<br>
## 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 ?
- Le degré moyen du groupe 0 = 6.61
- Le degré moyen du grouep 1 = 18.40
- Réseau aléatoire :
- Le degré moyen du groupe 0 = 6.63
- Le degré moyen du grouep 1 = 7.62
- Réseau Barabasi :
Hajar RAHMOUNI
a validé
- Le degré moyen du groupe 0 : 7.00
- Le degré moyen du groupe 1 : 41.71
- On remarque que le degré moyen du groupe 1 est plus grand que celui du groupe 0. le voisin d'un noeud choisit au hasard a plus de chance d'etre un hub, en immunisant la moitié du réseau, on a plus de chance d'immuniser des hubs qui vont à leurs tours immuniser une fraction de voisins, d'ou le degré moyen elevé.
- Donc Le groupe 1 a une probabilité élevé d'avoir été immunisés grâce à un de leurs voisins
## 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.
Hajar RAHMOUNI
a validé
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
- le seuil épidémique du réseau modifié pour la méthode d'immunisation du scenario 02 (immunisation aléatoire) est de valeur k/k2 : **0.04**
- le seuil épidémique du réseau modifié pour la méthode d'immunisation du scenario 03 (immunisation séléctive) est de valeur k/k2 : **0.09**
- On remarque bien que le seuil épidémique du scenario 03 est supérieur au seuil épidémique du reseau initial et du scenario 2.
- On peut déduire que l'immunisation sélective est la plus efficace, car plus le seuil est grand plus c'est plus efficace.
## 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.
- Comparaison entre les 3 réseaux pour la simulation 1 :<br>
- Comparaison entre les 3 réseaux pour la simulation 2 :<br>
- Comparaison entre les 3 réseaux pour la simulation 3 :<br>
- Graphe Aléatoire :
- seuil épidémique à l'immunisation aléatoire : 0.13
- seuil épidémique à l'immunisation sélective : 0.14
- Graphe Barabasi :
- seuil épidémique à l'immunisation aléatoire : 0.02
- seuil épidémique à l'immunisation sélective : 0.14
- Par conclusion : on constate que l'immunisation aléatoire est très moins efficace dans le graphe Barabasi.
au contraire du graphe Aléatoire.
- L'immunisation sélective reste favorisée dans tous les cas (graphe aléatoire ou généré avec la méthode d'attachement préférentiel).