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 |graph.getNodeCount() |
| nombre de liens | 1049866 |graph.getEdgeCount() |
| degré moyen | 6.62 |Toolkit.averageDegree(graph) |
| coefficient de clustering moyen| 0.63 |Toolkit.averageClusteringCoefficient(graph) |
#### 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