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 > = 921.74
- λc = < k > / < k2 > = 0,007184335
## Comparaison avec le seuil théorique d'un réseau aléatoire :
- λ = 1, 〈 k 〉 = 3.26, 〈 k2 〉 = 1 271
- λc = 0,00256491
- Le seuil théorique du réseau aléatoire est un peu plus supérieur que de celui de notre réseau.