# Projet RI Nous allons analyser un réseau de collaboration scientifique en informatique. Le réseau est extrait de DBLP et disponible sur SNAP. 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. Elles vous seront très utiles par la suite. ## 1- Tout d'abord : j'ai commencé par télécharger les données et les lire avec GraphStream. ## 2- Quelques mesures de base : J'ai calculé quelques mesures de base : comme le nombre de nœuds et d'arêtes, le degré moyen ainsi que le coefficient de clustring. - Nombre de noeuds : N = 317080 ```java int nodeCount = graph.getNodeCount(); ``` - Nombre de liens : E = 1049866 ```java int edgeCount = graph.getEdgeCount(); ``` - Degré moyen : ⟨k⟩ = 6.62208890914917 ```java double averageDegree = Toolkit.averageDegree(graph); ``` - Coefficient de clustering (réel) : 0.6324308280637396 ```java double clusteringCoefficient = Toolkit.averageClusteringCoefficient(graph); ``` - Coefficient de clustering (aléatoire) : ⟨k⟩/N = 2.0884599814397534E-5 ## 3- Autres mesures Voyons maintenant si le graphe est connexe : - Le réseau est-il connexe ? : Oui ```java boolean isConnected = Toolkit.isConnected(graph); ``` - Degré moyen minimal pour qu'un graphe aléatoire soit connexe : 12.666909386951092 ```java double minAverageDegreeForConnectivity = Math.log(nodeCount); ``` ## 4- Distribution des Degrés Exportation des données : Les degrés des nœuds sont exportés dans le fichier degree_distribution.txt. #### Analyse graphique : - Échelle linéaire : Tout d'abord, nous pouvons tracer la distribution des degrés en échelle linéaire. Cette courbe nous montrera comment la probabilité p(k) varie avec le degré k. Dans un graphique en échelle linéaire, la relation entre k et p(k) peut ne pas être évidente et pourrait ne pas révéler de structure particulière. ![Distribution des degrés](distribution_degres.png) - Échelle log-log : Lorsque nous traçons la même distribution en échelle log-log, c'est-à-dire avec les axes log(k) et log(p(k)), cela permet de mieux observer les tendances à grande échelle. nous observons une ligne droite ce qui nous dit que la distribution suit une loi de puissance. ![Distribution des degrés](distribution_degres_loglog.png) une ligne droite est observée, cela indique une loi de puissance. - Comparaison avec la distribution de Poisson : Superposer la distribution de Poisson avec ⟨k⟩. ![Dblp](dd_dblp.png) ## 5- Distance moyenne et distribution des distances Distance moyenne de notre réseau: 6.700611818856679 ```java double degreeAverage = Toolkit.averageDegree(graph); double NetworkDistance = Math.log(graph.getNodeCount()) / Math.log(degreeAverage); System.out.println("Distance moyenne dans notre réseau : " + NetworkDistance); ``` - L'hypothèse des six degrés de séparation se confirme-t-elle ? Oui, l'hypothèse des six degrés de séparation est confirmée : la distance moyenne entre les nœuds est proche de 6. - Est-ce qu'il s'agit d'un réseau petit monde ? Le réseau montre des propriétés caractéristiques des réseaux "petit monde" : une distance moyenne faible et un clustering élevé. - Quelle sera la distance moyenne dans un réseau aléatoire avec les mêmes caractéristiques ? J'ai calculé la distance moyenne d'un réseau aléatoire de même taille et de même degré moyen que j'ai généré avec randomGenerator de graphstream et ça nous donne à peu prés la même chose Distance moyenne du réseau Aléatoire : 6.70193902051403 ```java double degreeAverage = Toolkit.averageDegree(randomGraph); double NetworkDistance = Math.log(randomGraph.getNodeCount()) / Math.log(degreeAverage); System.out.println("Distance moyenne du réseau Aléatoire : " + NetworkDistance); ``` Tracer les distributions des distances : ![Distribution des distances](distance_distribution.png) - Analyse de la courbe des distances moyennes : Forme en cloche avec une décroissance symétrique de chaque côté. La courbe montre un pic central autour de 6. Cela suggère que la distance moyenne entre les paires de nœuds est proche de cette valeur. Cela soutient l'hypothèse des six degrés de séparation, car la majorité des distances sont à 6 ou moins. Décroissance rapide : Les distances très petites et très grandes sont rares, tandis que les distances proches de la moyenne sont les plus fréquentes. - Formulez une hypothèse sur la loi de cette distribution. On conclut donc que la forme de la distribution est proche d'une loi normale, ce qui est souvent observé dans les réseaux petits mondes. ## 6- Générer deux graphes de même taille et de même degré : 1 - le graphe aléatoire: Cette méthode génère un graphe aléatoire basé sur les propriétés d'un graphe d'entrée initialGraph, à l'aide d'un générateur de graphes aléatoires de GraphStream. Le graphe généré a un nombre total de nœuds fixé (N = 317080) et un degré moyen similaire à celui de initialGraph. ```java public static Graph createRandomGraph(Graph initialGraph) { double averageDegree = Toolkit.averageDegree(initialGraph); Generator generator = new RandomGenerator(averageDegree, false); Graph graphAlea = new SingleGraph("graphe aléatoire"); int N = 317080; // graphe aléatoire générer de taille N generator.addSink(graphAlea); generator.begin(); while (graphAlea.getNodeCount() < N) { generator.nextEvents(); } generator.end(); if (graphAlea.getNodeCount() == N) { System.out.println("Graph aléatoire générer !"); } return graphAlea; } ``` Les caractéristiques de ce graphe sont : Réseau aléatoire : - Nombre de nœuds : 317080 - Nombre de liens : 1049473 - Degré moyen : 6.61961030960083 - Coefficient de clustering : 4.364833098823207E-5 j'ai aussi calculé les degrés de distribution à l'échelle linéaire et à l'échelle log-log - Linéaire : ![Distribution des degrés](degree_distribution_random.png) - Log-log : ![Distribution des degrés](degree_distribution_loglog_random.png) 2 - Le graphe Barabàsi-Albert: Cette méthode génère un graphe Barabási-Albert en utilisant le graphe d'entrée initialGraph comme référence. Le modèle Barabási-Albert est un modèle de croissance qui suit le principe de l'attachement préférentiel : les nouveaux nœuds ont une probabilité plus élevée de se connecter aux nœuds déjà fortement connectés (hubs). Ce modèle permet de générer des graphes sans échelle, où la distribution des degrés suit une loi de puissance. ```java public static Graph generateBarabasiAlbertGraph(Graph initialGraph) { int nodeCount = initialGraph.getNodeCount(); double averageDegree = Toolkit.averageDegree(initialGraph); Graph barabasiGraph = new SingleGraph("Barabasi-Albert Network"); BarabasiAlbertGenerator generator = new BarabasiAlbertGenerator((int) averageDegree); generator.addSink(barabasiGraph); generator.begin(); while (barabasiGraph.getNodeCount() < nodeCount) { generator.nextEvents(); } generator.end(); return barabasiGraph; } ``` Les caractéristiques de ce graphe sont : Nombre de nœuds : 317080 Nombre de liens : 1108680 Degré moyen : 6.993061542510986 Coefficient de clustering : 4.235788849759945E-4 j'ai aussi calculé les degrés de distribution à l'échelle linéaire et à l'échelle log-log - Linéaire : ![Distribution des degrés](degree_distribution_ba.png) - Log-log : ![Distribution des degrés](degree_distribution_loglog_BA.png) Scenario 1: No Control Scenario 2: Random Immunization Scenario 3: Selective Immunization Les résultats ont été sauvegardés dans les fichiers pour Gnuplot. Degré moyen (Groupe 0 - Nœuds sélectionnés aléatoirement) : 0,000000000 Degré moyen (Groupe 1 - Voisins immunisés) : 0,000000000 Taux de propagation (τ) : 2.0 Seuil épidémique réel (c_réel) : 0.04598472436222584 Seuil épidémique théorique (c_théorique) : 0.13119762993051035 La maladie persiste dans le réseau réel (τ > c_réel). Le réseau réel est plus vulnérable que le réseau aléatoire (c_réel < c_théorique). Analyse après immunisation aléatoire : Taux de propagation (τ) : 2.0 Seuil épidémique réel (c_réel) : 0.08901721301662724 Seuil épidémique théorique (c_théorique) : 0.23306206408564414 La maladie persiste dans le réseau réel (τ > c_réel). Le réseau réel est plus vulnérable que le réseau aléatoire (c_réel < c_théorique). Analyse après immunisation sélective : Taux de propagation (τ) : 2.0 Seuil épidémique réel (c_réel) : 0.5542146555509032 Seuil épidémique théorique (c_théorique) : 0.8352912559058712 La maladie persiste dans le réseau réel (τ > c_réel). Le réseau réel est plus vulnérable que le réseau aléatoire (c_réel < c_théorique).