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.
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 ?
| Mesure | Résultat | Methode |
|:-------------------------------|:---------|:---------------------------------------|
| nombre de nœuds | 317080 |g.getNodeCount() |
| nombre de liens | 1049866 |g.getEdgeCount() |
| degré moyen | 6.62 |Toolkit.averageDegree(g) |
| coefficient de clustering moyen| 0.63 |Toolkit.averageClusteringCoefficient(g) |
#### Coefficient de clustering pour un réseau aléatoire de la même taille et du même degré moyen:
`Toolkit.averageDegree(g)/g.getNodeCount()`: 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 ?
Réseau connexe : oui (méthode: `Toolkit.isConnected(graphe)`);\
Un réseau aléatoire de la même taille et degré moyen sera-t-il connexe :\
non (méthode: `(Toolkit.averageDegree(graphe) > Math.log(graphe.getNodeCount())`);\
À partir de quel degré moyen un réseau aléatoire avec cette taille devient connexe :\
12.67 (méthode:`Math.log(graphe.getNodeCount()`)
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.
Distribution des degrés s'obtient avec la méthode : `Toolkit.degreeDistribution(graphe)`\
Puis on normalise les résultats obtenue entre [0,1].
```java
public static double[] normaliser(Graph g)
{
int[] dd = Toolkit.degreeDistribution(g);
double[] degree = new double[dd.length];
for (int k = 0; k < dd.length; k++)
if (dd[k] != 0)
degree[k]=(double)dd[k]/g.getNodeCount();
return degree;
}
```
#### Est-ce qu'on observe une ligne droite en log-log ? Que cela nous indique ?
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/poisson/GrapheFichier.gnuplot) pour tracer la distribution et estimer l'exposant de la loi de puissance.
On a $`\gamma = 2.7 \pm 0.04`$
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.
On récupere 1000 noeuds aléatoire grâce à cette méthode : `Toolkit.randomNodeSet(graphe,1000);`
```
L'hypothèse des six degrés de séparation se confirme-t-elle ?
```
Tout dépend des 1000 noeuds choisis. Mais dans la plupart des cas la distance moyenne est inférieure
ou égale à 6.
pour la suite des questions on prendra 6.509 comme distance moyenne.
```
Est-ce qu'il s'agit d'un réseau petit monde ?
```
Il faut que $`d_{max}`$ soit égale à la distance moyenne obtenue précédemment.
$`\frac{\ln 317080}{\ln 6,622088} = 6.7006`$
Comme les résultats obtenus ne sont pas d'une grande précision, on peut en conclure 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 ?
```
``Formulez une hypothèse sur la loi de cette distribution``
Hypothèse:
La courbe suit une loi de poisson
```math
```
on prend k = 10
```math
e^{-6.62208890914917}\cdot\frac{6.62208890914917^{10}}{10!} = 0.05946348641
```
Le résultat théorique ne correspond pas au résultat que nous avons mesuré:
Résultat théorique:
```math
p_k = 0.059
```
Résultat mesuré
```math
alors l'hypothèse est fausse.
Mon hypothèse finale serait que la courbe suit une loi binomiale.
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 BarabasiAlbert
| Mesure | Résultat |
|:--------------------------|:---------|
| nombre de nœuds | 317082 |
#### Coefficient de clustering pour un réseau aléatoire de la même taille et du même degré moyen:
Graphe Aléatoire
| Mesure | Résultat |
|:--------------------------|:---------|
| nombre de nœuds | 317087 |
| nombre de liens | 985807 |
| degré moyen | 6.22 |
| coefficient de clustering | 0.000021 |
#### Coefficient de clustering pour un réseau aléatoire de la même taille et du même degré moyen:
Pour un réseau aléatoire, le coefficient de clustering (meme taille et meme degré moyen)
doit être égale à 2.0884599814397534E-5.
- Le résultat que nous avons lors de nos mesure sur le réseau aléatoire:
- Les deux résultats sont très proches.
Toujours pour un réseau aléatoire qui reprend la même taille ainsi que le même degré moyen n'est pas connexe. Vérifions:
- d'après la méthode ``Toolkit.isConnected`(Graph g)` le réseau aléatoire n'est pas connexe
Ce qui correspond à nos attente
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
# Propagation dans des réseaux
Les consignes sont les mêmes que pour le premier TP. On travaille sur les mêmes données et la problématique est proche. Utilisez donc le même dépôt sur la forge.
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. Taux de propagation du virus:
$`\beta = \frac{1}{7}`$ pour la probabilité de contaminer un collaborateur
$`\mu = \frac{1}{14}`$ pour la probabilité de mettre à jour son anti-virus.
le taux de propagation $`\lambda = \frac{\beta}{\mu} = 2`$
Seuil épidémique du réseau:
$`\lambda = \frac{<k>} {<k²>}`$
où $`<k>`$ = 6.62 et $`<k²>`$ = 144.6
$`\lambda = \frac{6.62} {144.63} = 0.046`$
Comparez avec le seuil théorique d'un réseau aléatoire du même degré moyen:
6.62 * (6.62+1) = 50.44
Le calcul : $`\lambda = \frac{6.62} {50.4} = 0.131 > 0.046`$
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.
Dans le premier cas : la propagation du virus ne fait qu'augmenter.
Dans le deuxième cas (immunisation aléatoire): la propagation subit un ralentissement.
Dans le troisième cas (immunisation sélective): elle permet de réduire la propagation du virus malgré que le nombre de noeud immunisé soit inférieur ou égale au deuxième cas.
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 ?
groupe 0 : $`<k>`$ = 9.12
groupe 1 : $`<k>`$ = 28.73
Le groupe 1 a une probabilité élevé d'avoir été immunisés grâce à un de leurs voisins.
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.
seuil épidémique réseau initial : 0.046
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
seuil épidémique (selective) : 0.141
plus le seuil est grand plus le type d'immunisation est efficace.
Donc l'immunisation sélective est la 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.
## Graphe Barabasi-Albert
### Scénario 1
### Scénario 2
### Scénario 3
## Graphe Aleatoire
### Scénario 1
### Scénario 2
### Scénario 3
Graphe Aleatoire
seuil épidémique (sélective) : 0.152
Graphe Barabasi-Albert
seuil épidémique (sélective) : 0.166
Donc on peut remarquer que l'immunisation aléatoire est plus efficace dans le graphe Aléatoire.
Alors que l'immunisation sélective est plus efficace dans le graphe Barabasi-Albert.