Newer
Older
- On a commencé par telecharger et lire les données par readAll du classe FileSourceEdge() de GraphStream.
- Nombre de nœuds : 317080
- Nombre de liens : 1049866
- Le degré moyen : 6.62208890914917
- Coefficient de clustering : 0.6324308280637396
- le coefficient de clustering pour un réseau aléatoire de la même taille est : < K >/N = 6.62/317080 = 2.08780118582E-5
- Est ce que le graphe est connexe : true
- Un réseau aléatoire de la même taille et degré moyen n'est pas connexe
- Dans 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 donc le degré moyen doit etre superieur a 12.66 pour que le réseau aléatoire devient connexe.
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 pk=NkNp_k = \frac{N_k}{N}pk=NNk est la probabilité qu'un nœud choisi au hasard ait degré k.
pour calculer la distribution des degres, on a crée une méthode distributionDegre() qui permet de calculer la probabilité qu’un noeud choisi au hasard ait degré k, en utilisant la fontion
Toolkit.degreeDistribution(graph) et qui renvoie un tableau où les indices représentent les degrés, et les valeurs de representent le nombre de noeud de ce degré.
On a crées apres un fichier texte ou chaque ligne représente la probabilité qu'un noeud choisi au hasard ait degré k.
- On a γ=2.7±0.04
- Distribution des degrés en echelle linéaire :
- Distribution des degrés en echelle log :
- 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−γ
- Distribution de poisson, de puissance :
5. Distribution des distances :
- 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**
6. Reseau aleatoire et réseau Barabasi
- Les mesures faites sur un réseau aléatoire et un graphe généré avec la méthode d'attachement préférentiel (Barabasi-Albert)
- pour le reseaux aleatoir Les résultats expérimentaux correspondent aux prédictions théoriques calculées ci_dessus dans les questions précedentes.
- la coefficient de clustering du reseau de barbasie et la distance moyenne sont plus petites que celles du reseau aleatoire