# Réseaux d'intéraction - Rapport des TP de réseaux complexes

## Mesures d'intéraction (TP1)

Nous analysons un réseau de collaboration scientifique en informatique (DBLP, extrait de SNAP).  
L’objectif est de mesurer des propriétés du réseau réel, puis de comparer avec deux modèles générés avec GraphStream :
- un réseau aléatoire (RandomGenerator) ;
- un réseau à attachement préférentiel (Barabási–Albert).

La plupart des mesures sont obtenues via `org.graphstream.algorithm.Toolkit`.

---

### 1) Lecture des données (DBLP) et exécution

Le fichier `com-dblp.ungraph.txt` est lu avec GraphStream via `FileSourceEdge`.  

Le projet fonctionne avec Java / Maven. Il faut exécuter la classe `MesureInteraction` (dans Eclipse par exemple) pour effectuer les calculs.

Les scripts gnuplot sont dans le même dossier que la classe `MesureInteraction`.
Il faut exécuter les scripts gnuplot depuis la racine du projet (important pour les chemins) :
- `gnuplot src/main/java/.../degrees_reel_lineaire.gnuplot`
- `gnuplot src/main/java/.../degrees_reel_loglog_fit.gnuplot`
- `gnuplot src/main/java/.../degrees_compare_loglog.gnuplot`
- `gnuplot src/main/java/.../distances_compare.gnuplot`

Le dossier `target` se trouve à la racine du projet, au même niveau que le README.

Les fichiers .dat sont générés dans le dossier `target/dat`.

Les images des courbes `.png` sont créées dans le dossier `target/courbes`.

---

### 2) Mesures de base : nombre de nœuds, liens, degré moyen, clustering

Mesures (réseau DBLP, sortie console) :
- Nombre de nœuds : **N = 317080** ;
- Nombre d’arêtes : **L = 1049866** ;
- Degré moyen : **k_moy = 6.62208890914917** ;
- Degré maximum : **k_max = 343** ;
- Coefficient de clustering moyen : **C = 0.6324308280637396**.

#### Clustering attendu pour un réseau aléatoire de même taille et même degré moyen :  
Dans un réseau aléatoire, on approxime la probabilité de lien par **p = k_moy / (N − 1)**.  
Le clustering attendu est de l’ordre de **p**.

Ici, on a **p ≈ 2.088466568000142E-5**.

Comparaison :
- DBLP : **C ≈ 0.632** ;
- Réseau aléatoire comparable : **C attendu ≈ 2.1e-5**.

Le réseau DBLP est donc beaucoup plus clusterisé qu’un réseau aléatoire.

---

### 3) Connexité : DBLP, réseau aléatoire comparable, seuil de connexité

DBLP est-il connexe ?
`Toolkit.isConnected(g)` renvoie **true**, donc le graphe est connexe.

Un réseau aléatoire de même taille et même degré moyen serait-il connexe ?  
Dans le cours, une règle indique qu'un réseau aléatoire devient connexe quand **k_moy > ln(N)**.

Ici, nous avons :
- ln(N) = ln(317080) ≈ **12.6669** ;
- k_moy(DBLP) ≈ **6.62**, donc **k_moy < ln(N)**.

En conclusion, un réseau aléatoire de même taille et même degré moyen a de fortes chances de **ne pas être connexe**. C’est cohérent avec le fait qu'on a `Toolkit.isConnected(g1)` qui renvoie **false** sur le réseau aléatoire généré.

À partir de quel degré moyen un réseau aléatoire avec cette taille devient connexe ?

Un réseau aléatoire avec cette taille devient connexe à partir du seuil **k_moy ≈ ln(N) ≈ 12.67**.

---

### 4) Distribution des degrés + tracés (linéaire puis log-log) + Poisson + fit loi de puissance

On calcule la distribution des degrés avec `Toolkit.degreeDistribution(g)`, puis on normalise **p(k) = Nk / N**.

#### 4.1) Échelle linéaire (DBLP)
Dans le graphe ci-dessous, on peut voir que la distribution est très concentrée sur les petits degrés, et la traîne est difficile à lire en linéaire.

**Graphe de la distribution des degrés en linéaire :**
![Distribution des degrés (linéaire)](target/courbes/degree_reel_lineaire.png)

#### 4.2) Échelle log-log (DBLP) et ajustement

En échelle log-log, on observe une traîne et une zone approximativement “linéaire” sur une plage de degrés, ce qui suggère un comportement compatible avec une loi de puissance sur cette plage : p(k) ≈ C · k^(-gamma)

Le script gnuplot utilise fit pour estimer les paramètres. Valeur obtenue (sortie gnuplot) : gamma ≈ 2.23.

**Graphe de la distribution des degrés en log-log + fit :**
![Distribution des degrés (log-log + fit)](target/courbes/degree_reel_loglog_fit.png)

---

### 5) Distance moyenne : estimation par échantillonnage (BFS) + distribution des distances

Le calcul exact “toutes paires” est trop long.  
On estime la distance moyenne par échantillonnage :
- 1000 sommets sources au hasard (`Toolkit.randomNodeSet(g, 1000)`) ;
- BFS (`BreadthFirstIterator`) ;
- moyenne des distances observées + distribution p(d).

On applique exactement la même estimation BFS au réseau DBLP, au réseau aléatoire généré et au réseau BA.

DBLP (sortie console) :
- distance moyenne par formule indicative : **ln(N) / ln(k_moy) ≈ 6.70** ;
- distance moyenne estimée par BFS : **≈ 6.8**.

On peut conclure que malgré la grande taille, la distance moyenne reste faible, l’idée des “six degrés” est globalement compatible. Aussi, combiné au fort clustering, on peut remarquer que DBLP a un comportement de réseau petit monde.

Pour la distribution des distances, la distribution p(d) est centrée autour d’une valeur (forme en cloche), avec très peu de grandes distances. On peut observer dans le graphe ci-dessous la courbe de distribution des distances pour le DBLP.

**Graphe des distributions des distances (DBLP / aléatoire / BA) :**
![Comparaison des distances](target/courbes/distances_compare.png)

---

### 6) Génération des deux réseaux (même taille et degré moyen) + comparaison

Ici, l'objectif est de générer deux graphes ayant la même taille N que DBLP et un degré moyen proche, puis refaire les mesures.

#### 6.1) Réseau aléatoire (modèle ER)

On génère un réseau aléatoire avec N identique et un paramètre choisi pour obtenir un degré moyen proche de celui de DBLP. Dans les graphes et dans le code, je note parfois ce réseau ‘ER’ (pour Erdős–Rényi), c’est le modèle de réseau aléatoire classique. Ici, il est généré avec RandomGenerator.

Résultats observés :
- degré moyen proche de DBLP (en pratique autour de 7) ;
- clustering très faible (comme attendu pour un réseau aléatoire) ;
- graphe souvent non connexe (false) car le degré moyen reste inférieur à ln(N) ;
- distance moyenne du même ordre que DBLP (~6.7).

Cela montre qu’un réseau aléatoire de même taille et degré moyen ne reproduit pas le fort clustering observé dans DBLP.

#### 6.2) Réseau Barabási–Albert (attachement préférentiel)

On génère ensuite un réseau par attachement préférentiel avec N identique et un paramètre réglé pour viser le même degré moyen. Dans ce modèle, chaque nouveau nœud ajoute m liens, ce qui donne en moyenne un degré proche de **2m**.

On prend donc m ≈ k_moy_DBLP / 2, ici on arrondit m = 3 car le générateur demande un int en paramètre pour le degré moyen.

Dans le code, j'utilise **setExactlyMaxLinksPerStep(true)** pour garantir exactement m liens à chaque nouveau nœud (et donc stabiliser le degré moyen).

Résultats observés :
- k_moy ≈ 6.0 (cohérent avec **2m**) ;
- degré max très élevé (hubs) ;
- clustering faible (~10^-4), plus grand qu’aléatoire mais très loin de DBLP ;
- graphe connexe (`true`) ;
- distance moyenne plus faible (environ 5.3 ou 5.4).

Le graphe suivant compare les distributions des degrés en log-log pour DBLP, le réseau aléatoire et Barabási–Albert.

**Graphe de comparaison des distributions des degrés (log-log) :**
![Comparaison des degrés (log-log)](target/courbes/degree_compare_loglog.png)

On observe que :
- le réseau aléatoire décroît rapidement (peu de très grands degrés) ;
- Barabási–Albert produit une traîne plus lourde (présence de hubs) ;
- DBLP présente aussi une traîne lourde, mais avec en plus un clustering beaucoup plus fort.

### Conclusion
Les deux réseaux générés ont une taille identique à DBLP et un degré moyen proche (les petits écarts viennent de l’arrondi et du fonctionnement des générateurs).

Le réseau aléatoire ne ressemble pas à DBLP, il a un clustering très faible et il n’est pas forcément connexe.

Le réseau Barabási–Albert produit des “hubs” et des distances plus courtes, ce qui se rapproche mieux de DBLP sur la distribution des degrés, mais son clustering reste très faible comparé au réseau réel.

Au final, le réseau DBLP combine à la fois un clustering élevé et des distances courtes, aucun des deux modèles simples (Réseau aléatoire et Barabási–Albert) ne reproduit complètement ces propriétés.

---

## Propagation dans des réseaux (TP2)

On étudie la propagation d’un virus informatique qui se transmet par mail sur un réseau de collaborations.
Le réseau principal est un réseau réel (DBLP), on doit le comparer, en gardant la même taille et un degré moyen proche, avec :
- un réseau aléatoire (Erdős–Rényi) ;
- un réseau à attachement préférentiel (Barabási–Albert).

Il faut exécuter la classe `PropagationReseau` (dans Eclipse par exemple) pour effectuer les calculs.

Les scripts gnuplot sont dans le même dossier que la classe `PropagationReseau`.
Il faut exécuter les scripts gnuplot depuis la racine du projet (important pour les chemins) :
- `gnuplot src/main/java/.../propagation_dblp.gnuplot`
- `gnuplot src/main/java/.../propagation_aleatoire.gnuplot`
- `gnuplot src/main/java/.../propagation_ba.gnuplot`
- `gnuplot src/main/java/.../propagation_comparaison_reseaux_3scenarios.gnuplot`

Le dossier `target` se trouve à la racine du projet, au même niveau que le README.

Les fichiers .dat sont générés dans le dossier `target/dat`.

Les images des courbes `.png` sont créées dans le dossier `target/courbes`.

---

### 1) Hypothèses et paramètres du modèle

Consignes du sujet :

- Un individu envoie en moyenne 1 mail par semaine à chacun de ses voisins ;
- Un individu met à jour son anti-virus en moyenne 2 fois par mois ; 
- La mise à jour guérit, mais ne protège pas contre une nouvelle infection (virus mutant) ;
- L’épidémie commence avec un patient zéro infecté.

On simule un modèle SIS (Susceptible → Infecté → Susceptible) jour par jour pendant 3 mois :

- durée : 90 jours ;
- probabilité de transmission (par voisin et par jour) : **beta = 1/7 ≈ 0.142857** ;
- probabilité de guérison (par jour) : **mu = 2/30 ≈ 0.0666667**.

Le taux de propagation est **lambda = beta / mu ≈ 2.142857**.

Le sujet précise que le résultat peut être sensible aux conditions initiales, donc on répète chaque scénario plusieurs fois.
Ici on prend **NB_RUNS = 20** et on trace la **courbe moyenne**.
À chaque run, le patient zéro est choisi aléatoirement parmi les nœuds non immunisés.

---

### 2) Seuil épidémique et comparaison avec un réseau aléatoire

Le seuil épidémique utilisé (comme dans le cours) est **lambda_c = \<k> / <k^2>**.

On compare aussi avec le seuil théorique d’un réseau aléatoire de même degré moyen (formule donnée dans le cours) : **lambda_c_ER = 1 / (\<k> + 1)**.

Sortie console (DBLP) :
- \<k> ≈ **6.6221** ;
- <k^2> ≈ **144.0063** ;
- lambda ≈ **2.1429** ;
- lambda_c (réseau) ≈ **0.0460** ;
- lambda_c_ER (théorique) ≈ **0.1312**.

On a **lambda > lambda_c**, donc une épidémie est attendue.
Le seuil du réseau réel est plus bas que le seuil théorique ER car DBLP est hétérogène, **<k^2>** est grand, ce qui diminue **\<k>/<k^2>**.

---

### 3) Scénarios simulés

On simule jour par jour l’évolution de la fraction d’infectés **parmi les non immunisés** dans trois scénarios :

- Scénario 1 : Rien (pas d’action) ;
- Scénario 2 : Immunisation aléatoire 50% (50% des nœuds immunisés au hasard) ;
- Scénario 3 : Immunisation sélective (50% des nœuds “convainqueurs” tirés au hasard, chacun convainc un voisin).

Remarque importante pour l’immunisation sélective :

Le nombre final d’immunisés n’est pas forcément exactement égal à 50%, on tire 50% de convainqueurs (non immunisés), puis chaque convainqueur tente d’immuniser un voisin. Cela peut échouer si un nœud est isolé.

De plus, si plusieurs convainqueurs choisissent le même voisin, on obtient des doublons. Dans le code, je limite ce problème en réessayant pour trouver un voisin non déjà immunisé.

---

### 4) Courbes sur DBLP

**Graphe de propagation pour un réseau réel (DBLP) :**
![Propagation DBLP](target/courbes/propagation_dblp.png)

Dans le graphe, on observe :

- Sans immunisation : la fraction d’infectés augmente puis se stabilise à une valeur élevée ;
- Immunisation aléatoire 50% : la propagation diminue nettement mais reste présente ;
- Immunisation sélective : la propagation devient très faible (ordre de grandeur très petit).

Dans le cas de l'immunisation sélective, la courbe sélective peut être difficile à lire sur une échelle [0;1], c'est la raison pour laquelle j'ai établi un set yrange [0:0.001] dans le gnuplot afin qu'on puisse voir les variations.

Conclusion sur DBLP :
- l’immunisation sélective est la plus efficace des trois stratégies.

---

### 5) Courbes sur réseau aléatoire

**Graphe de propagation pour un réseau Aléatoire :**
![Propagation Aleatoire](target/courbes/propagation_aleatoire.png)

Ici, on observe :

- Sans immunisation : propagation rapide, plateau élevé ;
- Immunisation aléatoire 50% : baisse, mais l’épidémie reste importante ;
- Immunisation sélective : baisse supplémentaire, mais moins importante que sur DBLP.

En regardant les résultats, on peut remarquer que dans un réseau aléatoire, les degrés sont assez homogènes, donc “choisir un voisin” ne cible pas particulièrement des nœuds très connectés.

---

### 6) Courbes sur Barabási–Albert

**Graphe de propagation pour un réseau Barabási–Albert :**
![Propagation BA](target/courbes/propagation_ba.png)

On observe :

- Sans immunisation : propagation rapide et forte ;
- Immunisation aléatoire 50% : réduction, mais une épidémie peut encore se maintenir ;
- Immunisation sélective : réduction beaucoup plus forte.

Ici, on peut remarquer que le réseau BA contient des hubs (très grands degrés). Une immunisation sélective a plus de chances d’atteindre ces hubs (directement ou indirectement), donc elle est très efficace.

---

### 7) Comparaison des trois réseaux, scénario par scénario

**Graphe de comparaison de propagation des 3 réseaux pour chaque scénario :**
![Comparaison reseaux](target/courbes/propagation_compare_reseaux_3scenarios.png)

Cette image contient trois sous-graphes (un graphe par scénario) possédant chacun trois courbes représentant les différents types de réseaux :

- Scénario Rien : les trois réseaux développent une épidémie, mais avec des vitesses et des plateaux différents ;
- Scénario Immunisation aléatoire 50% : réduction visible partout, mais effet variable selon le réseau ;
- Scénario Immunisation sélective : effet très fort sur DBLP et BA (réseaux hétérogènes), moins marqué sur le réseau aléatoire.

Pour le scénario sélectif, l’axe Y est zoomé pour rendre visibles les faibles valeurs.

---

### 8) Justification de l’efficacité de l’immunisation sélective (groupes 0 et 1)

Le sujet demande de calculer le degré moyen des groupes 0 et 1, pour rappel :

- Groupe 0 : les convainqueurs (50% tirés au hasard) ;
- Groupe 1 : les voisins convaincus (immunisés).

Sortie console (DBLP) :

- degré moyen groupe 0 ≈ **6.60** ;
- degré moyen groupe 1 ≈ **10.50**.

Le groupe 1 a un degré moyen plus élevé, car choisir “un voisin” favorise naturellement les nœuds de grand degré.

---

### 9) Seuil épidémique après immunisation (réseau modifié)

Le sujet précise qu’immuniser un nœud revient à le supprimer du réseau du point de vue du virus.
On recalcule donc le seuil sur le réseau modifié (en ne comptant que les liens entre non immunisés).

Sortie console (DBLP) :

- seuil initial ≈ **0.0460** ;
- après immunisation aléatoire ≈ **0.0868** ;
- après immunisation sélective ≈ **0.2540**.

Les deux stratégies d'immunisation augmentent le seuil, mais la sélective l’augmente bien plus, ce qui correspond aux courbes.

---

### Conclusion

 Le taux de propagation issu des hypothèses (conditions) du sujet vaut lambda ≈ **2.1429**.
 Sur DBLP, le seuil épidémique est faible (≈ **0.046**) et plus petit que le seuil théorique d’un réseau aléatoire de même degré moyen.
 Les simulations sur 90 jours montrent que :
  - sans action, l’épidémie se maintient à un niveau élevé ;
  - l’immunisation aléatoire réduit la propagation mais ne suffit pas toujours ;
  - l’immunisation sélective est la stratégie la plus efficace sur les réseaux hétérogènes (DBLP et BA).
 La différence entre groupe 0 et groupe 1 (degré moyen plus élevé pour les voisins) explique pourquoi la stratégie sélective fonctionne mieux.
 Les comparaisons entre DBLP, aléatoire et BA montrent que la structure du réseau (présence de hubs, hétérogénéité) influence fortement la propagation.

