## Mesures de réseaux d'interaction ### 2.Quelques mesures de base: | Mesure | Resultat| |-----------------|:-------------| | Le nombre de noeud (N) :| 317080 | | Le nombre de lien (L) : | 1049866 | | Le Degré moyen (K) :| 6.62208890914917 | | Le coefficient de clustering : | 0.6324308280637396 | Le coefficient de clustering pour un réseau aléatoire de la même taille et du même degré moyen est **![](https://latex.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cfn_jvn%20P%3D%5Cfrac%7BK%7D%7BN%7D%3D%5Cfrac%7B6.62208890914917%7D%7B317080%7D%3D0.00002088459)** ### 3.La connexité du reseau Oui, le reseau est connexe car il posséde une seule composante connexe (il suffit d'executer ce code) ```java if(isConnected(graph)) System.out.println("Le graphe est connexe"); else System.out.println("Le graphe est non connexe"); ``` Un réseau aléatoire de la même taille et degré moyen ne sera pas connexe car dans un régime connecté cette condition doit etre verifiée : **![](https://latex.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cfn_jvn%20k%20%3Eln%28n%29%3A%28p%20%3E%20%5Cfrac%7Bln%28N%29%7D%7BN%7D%29)** et là dans notre cas : **![](https://latex.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cfn_jvn%20k%20%3D%206.62208890914917%20%5Cngtr%20ln%28N%29%20%3D%2012.666909387)** Donc un réseau aléatoire avec cette taille sera connexe à partir d'un degré moyen **![](https://latex.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cfn_jvn%20k%3E12.666909387)** ### 4.La distribution de degrés En traçant la distribution de degrés avec [le fichier obtenu][dd-degres-distribution] en échelle log-log on observe une ligne droite pendant plusieurs ordres de grandeur. Cela nous indique une loi de puissance : **![](https://latex.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cfn_jvn%20P_k%3DCK%5E%5Cdelta)** Tracer la distribution et estimer l'exposant de la loi de puissance: | Tracer la distribution de degrés | | :--------------------------:|:-------------------------: ![](src/main/resources/distribution_degres/dd_dblp.png) | On a γ=2.7±0.04 La loi de puissance ici signifie que ce reseau n'a pas d'échelle, comme on a pu le remarquer lors du calcul de la distribution le degré typique des noeuds est k ± ∞. ### 5.La distance moyenne dans le réseau Voici le programme utilisé pour obtenir la distribution des distances: ```java public static HashMap getDistancesDistribution(Graph g, int nn) { List sample = Toolkit.randomNodeSet(g, nn); HashMap dist_distances = new HashMap<>(); int i = 0; for (Node n : sample) { BreadthFirstIterator iter = (BreadthFirstIterator) n.getBreadthFirstIterator(); while (iter.hasNext()) { int depth = iter.getDepthOf(iter.next()); Double depthSum = dist_distances.get(depth); if (depthSum == null) dist_distances.put(depth, 1.0); else dist_distances.put(depth, depthSum + 1); } i++; } Double measuresCount = dist_distances.values().stream().reduce(0.0, Double::sum); dist_distances.forEach((k, v) -> dist_distances.put(k, v / measuresCount)); return dist_distances; } ``` Puis j'ai mets les resultat dans ce [fichier][dd-distances-distribution] - La courbe obtenue en exécutant avec gnuplot est: ![](src/main/resources/distribution_distances/dist-distri.png) La courbe obtenue correspond à une **loi de poisson** de parametre γ=7±0.5, la cloche dans la courbe(**γ**) indique la valeur du plus grand nombre de noeuds partageant une distance avec un autre noeud. La distance moyenne obtenue avec un échantillon de 1000 est **6,76** par conséquant L'hypothèse des 6 degrés de séparation semble se confirmer. Vérifiant si les propriétés d'un réseau **petit monde** sont réunies : - Six degrés de séparation :heavy_check_mark: :heavy_check_mark: - **![](https://latex.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cfn_jvn%20%3Cd%20%3E%20%3Dd_%7B_max%7D)** Par un simple calcul **![](https://latex.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cfn_jvn%20d_%7Bmax%7D%3D%20%5Cfrac%7Bln%28N%29%7D%7Bln%28K%29%7D%3D%206.70064)**, vu que notre programme n'est pas très précis alors on peut les considérés comme égaux **![](https://latex.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cfn_jvn%20%3Cd%20%3E%20%5Capprox%20d_%7B_max%7D)** :heavy_check_mark: :heavy_check_mark: Les propriétés sont vérifiées donc c'est un réseau **petit monde** Un réseau aléatoire avec les mêmes caractéristiques aura la même distance moyenne, car d'après le cours, c'est la seule caractéristique en commun entre un réseau de terrain et réseau aléatoire. ### 6-Refaire les mesures de base En utilisant GraphStream, on génere un réseau aléatoire et un un réseau avec la méthode d'attachement préférentiel (Barabasi-Albert) (même taille et même degré), et on refait les mesures précédentes : 1)Un réseau avec la méthode d'attachement préférentiel (Barabasi-Albert) : | Mesure | Resultat| |-----------------|:-------------| | Le nombre de noeud (N) :| 100000 | | Le nombre de lien (L) : | 349539 | | Le Degré moyen (K) :| 6.990779876708984 | | Le coefficient de clustering : | 0.0012226869597521156 | Oui, ce graphe est connexe. | tracer la distribution des degres et estimer l'exposant de la loi de puissance | | :--------------------------:|:-------------------------: ![](src/main/resources/distribution_degres/deg-meth-att-ref.png) | | tracer la distribution des distances | | :--------------------------:|:-------------------------: ![](src/main/resources/distribution_distances/dist-distrib-mehode.png) | 2)Un réseau aléatoire : | Mesure | Resultat| |-----------------|:-------------| | Le nombre de noeud (N) :| 100000 | | Le nombre de lien (L) : | 348924 | | Le Degré moyen (K) :| 6.978549957275391 | | Le coefficient de clustering : | 6.77163144670172E-5 | Ce réseau n'est pas connecté. | tracer la distribution et estimer l'exposant de la loi de puissance | | :--------------------------:|:-------------------------: ![](src/main/resources/distribution_degres/deg-reseau-aleatoire.png) | | tracer la distribution des distances | | :--------------------------:|:-------------------------: ![](src/main/resources/distribution_distances/dist-distrib-aleat.png) | [dd-degres-distribution]: https://www-apps.univ-lehavre.fr/forge/ic194665/tp2-ri-chaourar_imine/-/blob/master/src/main/resources/distribution_degres/degreedistribution.txt [dd-distances-distribution]: https://www-apps.univ-lehavre.fr/forge/ic194665/tp2-ri-chaourar_imine/-/blob/master/src/main/resources/distribution_distances/distancedistribution