# IWOCS_TP_MOLINIER # Mesures de réseaux d'interaction Les 2 TP sont dans le même projet. --- # TP 1 ## 1. Objectif du TP L'objectif de ce projet est d'analyser un réseau de collaboration scientifique en informatique extrait de **DBLP** (disponible sur [SNAP](https://snap.stanford.edu/data/com-DBLP.html)). Nous allons calculer certaines mesures de base pour comprendre la structure du réseau et comparer ses caractéristiques à celles d'un graphe aléatoire équivalent. 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://graphstream-project.org/gs-algo/org/graphstream/algorithm/Toolkit.html). Elles vous seront très utiles par la suite. On cherche à savoir si le graphe importer soit un réseau aléatoire et si non les différences entre un réseau aléatoire 1. Commencez par télécharger les données et les lire avec GraphStream. GraphStream sait lire ce format. Voir FileSourceEdge et ce tutoriel. Vous pouvez essayer de visualiser le graphe mais pour cette taille ça sera très lent et très peu parlant. #### Résultat Le fichier est un txt contenant les valeurs d'un graphe, pour l'ouvrir on utilise la fonction [getTheFileEdge(path)](src/main/java/org/example/GraphManipulation.java), qui lit chaque arête du fichier, crée automatiquement les nœuds correspondants si nécessaire et construit un objet Graph complet dans GraphStream. Limite : l'affichage du graphe est lent, pause problème car les nodes sont pas instannément crée mais nous sera pas utile dans notre cas. Le [fichier](src/main/resources/com-dblp.ungraph.txt) qu'on utilise contient l'ensemble des arretes . - Chaque ligne représente une connexion entre deux nœuds - Format : `FromNodeId ToNodeId` - Les nœuds sont créés automatiquement si nécessaire --- 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 ? #### Résultat Nous avons pris les mesures suivantes : - Nombre de nœuds - Nombre d'arêtes - Degré moyen - Coefficient de clustering Pour trouver le coefficient de clustering attendu pour un graphe aléatoire, on utilise la formule pour un graphe Erdős–Rényi : (Degré moyen) / (Nombre de nœuds - 1) #### Mesure | Mesure | Valeur | | -------------------------------------------- | ---------------------------------- | | Nombre de nœuds | 317 080 | | Nombre d'arêtes | 1 049 866 | | Degré moyen | 6.62208890914917 | | Coefficient de clustering réel | 0.6324308280637396 | | Coefficient attendu pour un graphe aléatoire | 2.088466568000142E-5 =0.0000208847 | --- #### Interprétation - Le graph est non orienté : car dans le fichier.txt, il y a Undirected graph. Qu'on a en plus vérifié avec une méthode isOrientedGraph(Graph g). - Le **degré moyen** indique qu’un chercheur collabore en moyenne avec ~6 à 7 autres chercheurs. - Le **coefficient de clustering réel** est très élevé environ = 0,632, ce qui montre que les collaborateurs d’un chercheur sont eux-mêmes souvent connectés, formant des communautés. - Le **coefficient attendu pour un graphe aléatoire** est très faible, ce qui confirme que la structure réelle du réseau est loin d’être aléatoire et présente des communautés bien définies. --- 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ésultat Pour notre réseau, il est **connexe**. Nous avons vérifié cela avec la fonction [isConnexe](src/main/java/org/example/GraphManipulation.java), qui parcourt toutes les arêtes, ajoute les nœuds atteignables dans un ensemble (`Set`) et compare la taille de cet ensemble au nombre total de nœuds du graphe. Pour qu’un **réseau aléatoire** soit connexe, il faut que le **degré moyen** soit supérieur à ln(Nombre de nœuds). - Nombre de nœuds : 317080 - Degré moyen du réseau étudié : 6.62208890914917 - ln(317080) = 12.66691 On trouve donc: 6.62208890914917 < 12.66691 . Le degré moyen actuel n’est pas suffisant pour garantir la connexité d’un graphe aléatoire de la même taille. #### Commentaire - Notre graphe réel est connexe, mais il **n’est pas un graphe aléatoire**. - Pour qu’un graphe aléatoire de cette taille soit connexe, le degré moyen devrait être supérieur à **12.66691** (soit ln(Nombre de nœuds). --- 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. #### Rappel - Tracé linéaire : distribution décroissante avec beaucoup de nœuds de petit degré. - Tracé log-log : distribution approximativement linéaire, indiquant une loi de puissance. - loi puissance : la probabilité qu’un nœud ait un degré k. - fit Gnuplot pour estimer l’exposant 𝛾 de cette loi de puissance. - 𝛾 = il caractérise la décroissance de la distribution des degrés et permet de mesurer l’hétérogénéité du réseau. #### Résultat La distribution de degrés pk=Nk/N est la probabilité qu'un nœud choisi au hasard ait degré kkk. On peut utiliser [Toolkit.degreeDistribution()]("https://data.graphstream-project.org/api/gs-algo/current/org/graphstream/algorithm/Toolkit.html#degreeDistribution(org.graphstream.graph.Graph)">) pour obtenir Nk et normaliser par la suite : ```java int[] dd = Toolkit.degreeDistribution(graph); for (int k = 0; k < dd.length; k++) { if (dd[k] != 0) { System.out.printf(Locale.US, "%6d%20.8f%n", k, (double)dd[k] / graph.getNodeCount()); } } ``` 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 : pk=Ck^−γ On utilise ce [script](src/main/gnuplot/plot_dd.gnu) pour tracer la distribution et estimer l'exposant de la loi de puissance. ![image_Résultat](src/main/gnuplot/dd_dblp.png) On a gamma = 2.7 ±0.04 #### Commentaire 1. Courbe DBLP (données réelles) - En log-log, la distribution est presque une droite sur plusieurs ordres de grandeur. - En échelle linéaire, la distribution décroît rapidement, montrant que la plupart des nœuds ont peu de liens. 2. Courbe Poisson (réseau aléatoire) - Elle est étroite et symétrique, avec peu de nœuds ayant un degré très élevé. - Distribution qui ne reproduit pas les hubs observés dans le réseau réel. 3. Courbe Power law (ajustement) - En log-log, elle suit presque parfaitement la droite des données réelles. Le fit est satisfaisant, et l’exposant γ≈2.7 peut être utilisé pour caractériser la loi de puissance du réseau DBLP. Cela confirme que le réseau est hétérogène et possède des hubs. --- 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](https://graphstream-project.org/gs-core/org/graphstream/graph/BreadthFirstIterator.html) à 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. #### Application Pour estimer la distance moyenne dans le réseau, le calcul exact des plus courts chemins entre toutes les paires de nœuds aurait été trop coûteux en temps de calcul pour un réseau de cette taille. Nous avons donc procédé à une estimation par échantillonnage : un parcours en largeur (Breadth-First Search) a été réalisé à partir de 1000 nœuds choisis aléatoirement. Et fait la [probabilité pour chaque distance](src/main/gnuplot/averageDistanceOf1000Node.dat) (en excluant 0). Cela est représenté par les fonctions [getDistanceProbabilities & getAverageDistanceOfNNode](src/main/java/org/example/GraphManipulation.java) qui permettent d'obtenir un dictionnaire d'occurence de la distance et la distance moyenne sur une selection de N points choisis aléatoirement. #### Résultat Le résultat obtenu est le suivant : - Distance moyenne=6.7996460629685345 ≈6,80 Répartion probabilité : ![image_Résultat](src/main/gnuplot/averageDistance.png) Cette valeur est proche de l’hypothèse des six degrés de séparation, selon laquelle la distance moyenne entre deux individus dans un réseau social est d’environ six. Cette observation suggère que le réseau étudié possède des caractéristiques typiques d’un réseau petit monde( distances moyennes relativement faibles malgré un grand nombre de nœuds) Pour **un réseau aléatoire** ayant le même nombre de nœuds N=317080 et un degré moyen ⟨k⟩=6,62208890914917, la distance moyenne attendue serait de : - Lrand = ln(N) / ln(k) - Lrand = ln (317080) / ln(6,62208890914917) - 6.70 ≈ 12,66691 / 1,890 #### Interprétation Pour notre réseau ou un réseau aléatoire, la distribution des distances est centrée autour de la distance moyenne ~6,8 et ~6.7 et décroît rapidement pour les distances plus grandes. Cela suggère que la plupart des nœuds sont proches les uns des autres, ce qui est typique d’un réseau petit monde. On peut donc hypothétiser que cette distribution suit une loi exponentielle décroissante. --- 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 ? #### Application On utilise donc les générateurs de GraphStream pour générer [un réseau aléatoire](https://graphstream-project.org/doc/Generators/Random-graph-generator/) et [un réseau avec la méthode d'attachement préférentiel](https://graphstream-project.org/doc/Generators/Barabasi-Albert-Preferential-Attachment-generator/) (Barabasi-Albert) Avec [ces méthodes](src/main/java/org/example/GraphGenerator.java) on renseigne le nombre de noeud et le degré moyen. Une particularité pour l'algorithme de Barabasi-Albert est qu'il ne prend pas degré moyen maisle nombre de liens par nouveau nœud (linksPerNewNode). Pour que le graphe ait un degré moyen approximatif k, il faut donc définir :linksPerNewNode ≈ degréMoyen / 2 car chaque arête contribue au degré de deux nœuds. #### Mesures obtenues | Graphe | Arêtes | Degré moyen | Clustering | Distance moyenne | | --------------- | --------- | ----------- | ---------- | ---------------- | | DBLP (réel) | 1 049 866 | 6.62 | 0.632 | 6.80 | | Random | 1 051 093 | 6.63 | 1.33e-5 | 6.91 | | Barabasi-Albert | 634 760 | 4.00 | 2.26e-4 | 6.19 | ![image_Résultat](src/main/gnuplot/averageDistanceOfThree.png) Obtenue avec ce script: [Script Gnuplot](src/main/gnuplot/averageDistanceProbaTree.gnu) (en excluant 0). ### En Conclusion L’analyse des réseaux montre que les résultats expérimentaux confirment en grande partie les prédictions théoriques. Le réseau aléatoire présente des distances conformes à ln(N)/ln(k) mais un clustering quasi nul, ce qui le rend très différent du réseau réel. Le modèle Barabasi-Albert montre des hubs et des distances moyennes plus faibles mais conserve un clustering faible. Comparé au réseau réel DBLP, ce dernier combine un fort clustering et des hubs, typique d’un réseau social de collaboration scientifique. Aucun des modèles simples ne reproduit parfaitement toutes les caractéristiques observées Le réseau DBLP n’est pas aléatoire et le modèle Barabasi-Albert capture certains aspects comme les hubs et les petites distances mais pas le clustering élevé. ### Limite Le générateurs de GraphStream pour l'algorithme de Barabasi-Albert ne permet pas d'imposer un degré moyen et ne prend que un entier en paramètre. Pour la représentation j'ai essayé ay mieu d'avoir une distance moyenne similaire. --- # TP 2 Nos collaborateurs scientifiques communiquent souvent par mail. Malheureusement pour eux, les pièces jointes de ces mails contiennent parfois des virus informatiques. On va étudier la propagation d'un virus avec les hypothèses suivantes : Un individu envoie en moyenne un mail par semaine à chacun de ses collaborateurs. Un individu met à jour son anti-virus en moyenne deux fois par mois. Cela nettoie son système mais ne le protège pas de nouvelles infections car le virus mute. L'épidémie commence avec un individu infecté (patient zéro). 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. ### Application Si on reprend les données des mesures faites sur le réseau DBLP dans le TP 1 qui représentait un réseau de collaboration scientifique en informatique. Alors on avait un degré moyen du réseau d'environ : 6.622 Le modèle d’infection qui correspond à notre situation est un modèle SIS, car les individus peuvent être infectés, guéris par leur anti-virus et redevenir susceptibles d’être infectés à nouveau, sans immunité permanente. La formule du seuil épidémique dans ce modèle est - !["Image des Formules de propagation"](static/image/formuleSiS.png) Donc le taux de propagation est = degre moyen × frequence quotidienne - soit 6,622 * (1/7) ≈ 0,94 Le seuil épidémique pour le réseau réel DBLP est donc très faible. --- 2. Simulez la propagation du virus jour par jour pendant trois mois avec les scénarios suivants : - On ne fait rien pour empêcher l'épidémie - On réussit à convaincre 50 % des individus de mettre à jour en permanence leur anti-virus (immunisation aléatoire) - On réussit à convaincre 50 % des individus de convaincre un de leurs contacts de mettre à jour en permanence son anti-virus (immunisation sélective). Pour chacun des trois scénarios, tracez l'évolution de la fraction d'infectés de la population non immunisée. Que peut-on conclure ? Attention : La réalisation d'un scénario autour des valeurs critiques est sensible aux conditions initiales. Simulez plusieurs fois chaque scénario afin d'identifier le déroulement typique. ### Application Dans [script Java réalisant les scénarios](src/main/java/org/example/Main_TP2.java) ### Résultat ![Image Des 3 scénarios](src/main/gnuplot/TP2/SIS_Scenarios.png) Obtenue avec ce script: [Script Gnuplot](src/main/gnuplot/TP2/scenarioImmunisation.gnu). ### Analyse on peut voir que chaqu'un des 3 scénario tent vers une valeurs: - Le scénario 1 ( sans Immunisation ) : l’infection devient endémique en étant proche de 1 car Dans un SIS, lorsque 𝛽 (taux de propagation) > seuil épidémique , aucune fraction d’infection ne s’éteint naturellement et le virus persiste indéfiniment. - Le scénario 2 ( Immunisation Aléatoire): l'infection peut etre proche de 0.5 en théorie. En pratique,la fraction observée est autour 0.3 - 0.35 car le réseau est hétérogène et fortement clusterisée. Les nœuds immunisés créent des barrières. - Scénario 3 (immunisation sélective 50%) : en ciblant les voisins des nœuds choisis, on supprime préférentiellement les chemins critiques de propagation. ### En Conclusion Le nombre de nœuds immunisés ne suffit pas à réduire une épidémie. La position des nœuds immunisés dans le réseau est tout aussi critique. Cela montre que la topologie du réseau et la stratégie d’immunisation sont des facteurs déterminants pour contrôler efficacement la propagation d’un virus. Cela permet de mieux comprendre pourquoi, lors de la pandémie de COVID‑19, la vaccination ciblée des populations les plus exposées et les mesures de confinement dans les zones à forte transmission ont été plus efficaces qu’une stratégie uniforme. --- 3. Pour justifier l'efficacité de l'immunisation sélective, calculez le degré moyen des groupes 0 et 1. Comment expliquez-vous la différence ? ### Application Dans le cadre des scénarios, on rajoute à la simulation le calcul quotidien du degré moyen pour chaque groupe: immunisés et non immunisés. Qu'on calcule chaque jour Pour le scénario 2 et 3 . Le scénario 1 (sans immunisation) n’est pas pris en compte pour ce calcul, car l’ensemble des nœuds appartient à un seul groupe. Le degré moyen est alors identique au degré moyen global du graphe. ### Résultat ![Image Des 3 scénarios](src/main/gnuplot/TP2/averageDegreeByImmunity_histogram.png) Obtenue avec ce script: [Script Gnuplot](src/main/gnuplot/TP2/plot_averageDegreeByImmunity.gnu). ### Conclusion Dans le cas de l’immunisation aléatoire, les nœuds immunisés et non immunisés présentent un degré moyen identique, proche de celui du graphe global (environ 6). Cela est attendu, car la sélection des individus immunisés est uniforme et indépendante de leur position dans le réseau. L’immunisation aléatoire ne cible donc pas spécifiquement les nœuds les plus connectés, et la structure du réseau reste globalement inchangée du point de vue des connexions. En revanche, dans le scénario d’immunisation sélective, une forte différence apparaît entre les deux groupes. Les nœuds immunisés ont un degré moyen élevé (environ 11,5), tandis que les nœuds non immunisés ont un degré moyen nettement plus faible (environ 4). Cette différence s’explique par le fait que la stratégie sélective tend à immuniser des nœuds fortement connectés (les hubs du réseau), qui jouent un rôle central dans la propagation du virus. --- 4. Du point de vue du virus l'immunisation d'un nœud est équivalente à sa suppression du réseau. Calculez le seuil épidémique du réseau modifié pour chacune des deux stratégies d'immunisation et comparez avec le seuil épidémique du réseau initial. 5. Simulez l'épidémie avec les mêmes hypothèses et les mêmes scénarios dans un réseau aléatoire et un réseau généré avec la méthode d'attachement préférentiel de la même taille et le même degré moyen. Comparez et commentez les résultats. ## Add your files ``` cd existing_repo git remote add origin https://www-apps.univ-lehavre.fr/forge/mh252189/iwocs_tp_molinier.git git branch -M main git push -uf origin main ``` ## Project status TP 1 , TP 2 (3/5)