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 ?
Quelques mestures faites sur le graphe :
| Mesures | Résultats | Functions |
| :------------------ | :---------------: | -------------: |
| $`N`$ | 317080 | [`graph.getNodeCount()`](https://data.graphstream-project.org/api/gs-core/current/org/graphstream/graph/Structure.html#getNodeCount()) |
| $`L`$ | 1049866 | [`graph.getEdgeCount()`](https://data.graphstream-project.org/api/gs-core/current/org/graphstream/graph/Structure.html#getEdgeCount()) |
| $`\langle k \rangle`$ | 6,6220889 | [`Toolkit.averageDegree(graph)`](https://data.graphstream-project.org/api/gs-algo/current/org/graphstream/algorithm/Toolkit.html#averageDegree(org.graphstream.graph.Graph)) |
| $`\langle C \rangle`$ | 0.6324308 | [`Toolkit.averageClusteringCoefficient(graph)`](https://data.graphstream-project.org/api/gs-algo/current/org/graphstream/algorithm/Toolkit.html#averageClusteringCoefficient(org.graphstream.graph.Graph)) |
Le coefficient de clustering $`Ci`$ mesure la probabilité $`p`$ qu'un noeud $`i`$ soit relié à un autre noeud du réseau. Dans le cas d'un réseau aléatoire $`G(N,p)`$, la probabilité est la même pour tous les noeuds. Ce qui veut dire que $`C_i=p`$.
Avec $`p=\frac{\langle k \rangle}{N}`$, le coefficient de clustering moyen d'un graphe aléatoire est égal à $`\frac{6,622088}{317080}=2.088 \times 10^{-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 ?
GraphStream permet de vérifier si un graphe est connexe avec [`Toolkit.isConnected()`](https://data.graphstream-project.org/api/gs-algo/current/org/graphstream/algorithm/Toolkit.html#isConnected(org.graphstream.graph.Graph)). Dans notre cas le réseau est connexe car l'algorithme parcours bien chaque noeud une seule fois en passant par leurs voisins.
Sans parcourir un réseau aléatoire, on peut déduire qu'il est connexe à partir du moment où $`\frac{\langle k \rangle}{\log{N}} \gt 1`$.
Pour un réseau aléatoire de même taille et de même degré moyen, cela donnerait $`\langle k \rangle = \frac{6,622088}{\ln 317080} = 0.52786`$, $`\langle k \rangle \lt 1`$ donc le réseau aléatoire n'est pas connexe.
Pour que le réseau aléatoire soit connexe, il faudrait que $`\langle k \rangle \gt \ln N`$.
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 :
On utilise ce [script](/script/gen_degree.gnu) 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.
La distribution de distances $`p_d = \frac{N_d}{N}`$ est la probabilité que deux noeuds pris au hasard aient distance $`d`$.
On peut utiliser [Metric.distanceDistribution()](https://www-apps.univ-lehavre.fr/forge/ey143326/ri-metrics/blob/master/src/main/java/metric/Metric.java) du programme pour obtenir $`N_d`$ et normaliser par la suite.
```java
int[] dd = new int[50];
Toolkit.randomNodeSet(graph, sample).forEach(node -> {
BreadthFirstIterator<Node> bfi = (BreadthFirstIterator<Node>) node.getBreadthFirstIterator();
while (bfi.hasNext())
dd[bfi.getDepthOf(bfi.next())]++;
});
return dd;
```
On traçant la courbe de distribution, on observe une cloche. Son sommet indique la valeur du plus grand nombre de noeuds partageant une distance avec un autre noeud.
On utilise ce [script](/script/gen_distance.gnu) pour tracer la distribution.
Pour savoir s'il s'agit d'un réseau "petit monde", il suffit de vérifier que $`\langle d \rangle = d_{max}`$ où $`d_{max} = \frac{\ln N}{\ln \langle k \rangle}`$.
Pour $`\langle d \rangle`$, on utilise la distribution des distances et avec un simple calcul de moyenne comme montré ci-dessous, on obtient $`\langle d \rangle = 6.787289`$ pour notre graphe de collaboration.
```java
int[] dd = distanceDistribution(graph, sample);
int sum = Arrays.stream(dd).reduce(0, Integer::sum);
double v = 0;
for (int i = 0; i < dd.length; i++)
v += i * dd[i];
return v / (double) sum;
```
Etant donné le temps d'execution qu'il faudrait pour obtenir $`d_{max}`$, on part du même calcul que dans un réseau aléatoire ayant le même nombre de noeuds et le même degré moyen, ce qui nous donne $`d_{max} = \frac{\ln 317080}{\ln 6,622088} = 6.700645`$
$`\langle d \rangle`$ et $`d_{max}`$ ne sont pas égaux mais notre algorithme ne permet pas d'avoir un résultat d'une immense précision, on pourra en conclure que le réseau de collaboration est un petit monde.
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 aléatoire :
| Mesures | Résultats |
| :------------------ | :---------------: |
| $`N`$ | 317088 |
| $`L`$ | 1110910 |
| $`\langle k \rangle`$ | 7.0069508 |
| $`\langle C \rangle`$ | 2.1839707 |
- Graphe préférentiel :
| Mesures | Résultats |
| :------------------ | :---------------: |
| $`N`$ | 317082 |
| $`L`$ | 1267243 |
| $`\langle k \rangle`$ | 7.9931564 |
| $`\langle C \rangle`$ | 4.8840521 |
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
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
179
180
181
182
# 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. ([SNAP](https://snap.stanford.edu/data/com-DBLP.html))
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 ?
On a $`\beta = \frac{1}{7}`$ pour la probabilité de contaminer un collaborateur et $`\mu = \frac{1}{14}`$ pour la probabilité de mettre à jour son anti-virus.
De ce fait, le taux de propagation $`\lambda = \frac{\beta}{\mu} = 2`$
2. Quel est le seuil épidémique du réseau ?
On peut avoir le seuil avec $`\lambda c = \frac{\langle k \rangle}{\langle k^2 \rangle}`$
où $`\langle k \rangle = 6.622`$ et $`\langle k^2 \rangle = 144,631`$
qui vaut $`\lambda c \approx 0.046`$.
3. Comparez avec le seuil théorique d'un réseau aléatoire du même degré moyen.
Le seuil épidémique d'un réseau aléatoire au même degré moyen
serait $`\lambda c = \frac{1}{\langle k \rangle + 1} \approx 0.131`$.
Cette différence entre les seuils épidémique est dûe à la divergence du degré de clustering.
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).
4. 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 ?
Pour le cas de l'immunisation aléatoire, dans des conditions normales de simulation, on observe au mieux un ralentissement de la propagation du virus.
Au contraire, la sélective permet d'entraver la propagation malgrès le fait que le nombre de noeuds immunisés soit inférieur ou égal à celui des immunisés aléatoirement.
5. Pour justifier l'efficacité de l'immunisation sélective, calculez le degré moyen des groupes 0 et 1.
$`\langle k \rangle (0) = 6.620`$
$`\langle k \rangle (1) = 11.370`$
6. Comment expliquez-vous la différence ?
Le groupe 1 manifeste une présence supérieur de hubs car ils ont une probabilité élevé d'être immunisés par un de leurs voisins.
7. 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.
$`\lambda c(aléatoire) \approx 0.046`$\
$`\lambda c(sélective) \approx 0.093`$
Pour le réseau aléatoire, le seuil épidémique est approximativement égal à celui du réseau initial car la taille du réseau n'a pas d'influence sur son seuil épidémique.
Alors que le réseau sélectif a un seuil épidémique environ deux fois plus grand que les autres. On peut justifier cela par le fait qu'un grand nombre de hub soient retirés du réseau et donc limite la propagation.
1. 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.