# Q1 - Téléchargement & lecture avec GraphStream en utilisant (FileSourceEdge)

## But : 
télécharger les données SNAP et lire le graphe com-dblp.ungraph.txt en utilisant FileSourceEdge (GraphStream).

## Commandes (téléchargement) :
https://snap.stanford.edu/data/bigdata/communities/com-dblp.ungraph.txt.gz

Le code suivant lit le fichier d’arêtes et affiche quelques informations de base. Il utilise FileSourceEdge comme demandé.

## Remarques :
Le graphe contient plusieurs centaines de milliers de nœuds → il faut suffisamment de RAM (plusieurs Go).

graph.display() fonctionne mais la visualisation n’est pas informative pour cette taille (très lente).

# Q2 - Mesures de base : nœuds, arêtes, degré moyen, clustering ; comparaison ER 

## Mesures (valeurs observées / calculées) : 
Valeurs numériques observées / connues pour ce jeu de données (com-DBLP) :

Nombre de nœuds : n ≈ 317 080
Nombre d’arêtes : m ≈ 1 049 866
Degré moyen : \<k> = 2m / n ≈ (2×1049866) / 317080 ≈ 6.622089
Coefficient de clustering observé (moyenne locale) : C ≈ 0.6324 (selon le calcul fais dans le code avec Toolkit)

## Coefficient de clustering attendu pour un graphe aléatoire G(n,p)
Pour un graphe Erdős–Rényi G(n,p) on a approximativement :

p ≈ \<k> / n-1

et le coefficient de clustering moyen vaut environ Crand≈p

Calcul numérique :
p ≈ 6.622089 / 317079 ≈ 0,0000208847

# Q3 - Connexité

## Définitions : 
Un graphe est connexe si tous les nœuds sont reliés entre eux par des chemins (une seule composante connexe contenant tous les nœuds).

Pour G(n,p), la connectivité (avec haute probabilité) apparaît autour du seuil  p ≈ (ln⁡ n)/n ce qui correspond à un degré moyen \⟨k⟩ ≈ ln n.

## Mesures / valeurs pour DBLP :
n≈317000 → ln ⁡n ≈ ln⁡(317000) ≈ 12.66.
Seuil en degré moyen pour connectivité ER : \⟨k⟩conn ≈ ln ⁡n ≈ 12.66 ≈ 13.
Degré moyen observé dans DBLP : \⟨k⟩ ≈ 6.6 < 13

## Observation (DBLP réel) :
DBLP n’est pas strictement connexe : il existe quelques petites composantes isolées (quelques nœuds ou petites communautés non reliées).
Cependant DBLP contient une très grande composante connexe qui regroupe la très grande majorité des nœuds.

## Comparaison avec un G(n,p) de même n et \<k> :
Un G(n,p) avec le même degré moyen \<k> ≈ 6.6 aura p = \<k> /(n−1) ≈ 0,0000208847.
Puisque \<k> < (ln ⁡n) un ER comparable ne sera pas (avec haute probabilité) entièrement connexe. On s’attend à :
une composante géante (si \<k>>1).
plusieurs petites composantes isolées.
l’absence de “tous les nœuds connectés” tant que \<k> n’atteint pas (ln n).

## Conclusion :
DBLP connexe ? => Non (mais contient une très grande composante connexe).
Réseau aléatoire même n et degré moyen (6.6) ? => Non — un G(n,p) comparable aura plusieurs composantes ; il ne sera pas complètement connexe.
Degré moyen minimum pour connexité d’un G(n,p) => \<k> >= (ln n) ≈ 12.66 ≈ 13 .

# Qst 4 - Distribution des degrés 

## Méthode : 
Pour obtenir la distribution des degrés, on utilise la fonction Toolkit.degreeDistribution(graph) de GraphStream, qui renvoie pour chaque degré k le nombre de noeuds Nk ayant ce degré.

La probabilité qu'un noeud ait un degré k est alors : 
pk = Nk / N .

On a généré le fichier degreeDist_dblp.dat pour Gnuplot afin de tracer la distribution.

## Résultat :
 1. Distribution linéaire : on observe que la majorité des noeuds ont un faible degré et très peu de noeuds ont un degré éleve.
![Distribution linéaire](dd_dblp_lin.png)
 2. Distribution log-log : en échelle log-log, on obtient approximativement une ligne droite sur plusieurs ordres de grandeur, indiquant que le réseau suit une loi de puissance : pk ∼ Ck−γ

![Degree distribution](dd_dblp.png)

 En utilisant la commande fit de Gnuplot, on obtient un exposant :
 γ ≈ 2.7±0.04

 3. Comparaison avec Poisson : la distribution de Poisson de même moyenne (\<k> ≈6.6) est beaucoup plus concentrée autour du degré moyen et décroît très rapidement pour les degrés élevés, ce qui confirme que DBLP n’est pas un réseau aléatoire de type Erdős–Rényi.

 # Q5 - Distance moyenne et distribution des distances

 ## Méthode : 
 Le calcul exact des plus courts chemins entre toutes les paires de nœuds étant trop coûteux, nous avons estimé la distance moyenne en procédant ainsi :
 1. Tirer 1000 sommets au hasard dans le graphe.
 2. Effectuer un parcours en largeur (BFS) à partir de chacun de ces sommets.
 3. Calculer la distance moyenne et la distribution des distances.

 ## Résultats : 
1. Distance moyenne estimée : 
⟨d⟩≈6,8125.
2. Distance moyenne d’un réseau aléatoire de même n et \<k> : \<d>ER 6,7006.
3. Distribution des distances : la plupart des paires de nœuds sont séparées par 5 à 9 arêtes. La distribution est très concentrée autour de la moyenne, avec une décroissance rapide pour les grandes distances.

![Distribution des distances](distanceDistribution.png)

## Interprétation : 
1. L’hypothèse des six degrés de séparation se vérifie approximativement.
2. Le réseau DBLP est un réseau petit monde car : 
distances moyennes faibles et coefficient de clustering élevé.
3. Les réseaux ER comparables ont des distances plus longues et un clustering très faible.

# Q6 - Comparaison avec modèles génératifs

## Méthode : 
Nous avons généré deux réseaux artificiels avec GraphStream, ayant le même nombre de nœuds et le degré moyen du DBLP :

1. Réseau aléatoire (Erdős–Rényi) : RandomGenerator(kER).
2. Réseau avec attachement préférentiel (Barabási–Albert) : BarabasiAlbertGenerator(mBA).

Nous avons ensuite refait les mesures des questions précédentes :

1. Nombre de noeuds et arêtes.
2. Degré moyen et distribution.
3. Coefficient de clustering.

## Résultats :
### Comparaison des trois réseaux
| Réseau |    n    |     m      | \<k> | Clustering C | Distance moyenne |
| :----: | :-----: | :---------: |:---:| :-----------: | :--------------: |
| DBLP   | 317 080 | 1 049 866   | 6.62 |   0.6324     |       6.7948       |
| ER     | 317 087 | 1 048 902   | 6,61 |   0,000024   |       9.1        |
| BA     | 317 082 | 634110     | 3,99  |   0,000184   |       7.8        |

## Analyse : 
1. ER :
Clustering quasi nul, distance moyenne plus élevée et ne reproduit pas les caractéristiques de DBLP.
2. BA : 
Distance moyenne proche de DBLP → petit monde, et Clustering beaucoup plus faible que DBLP → les hubs n’augmentent pas suffisamment le clustering.
3. Distribution des degrés : 
. ER suit une loi de Poisson.
. BA suit une loi de puissance (γ≈3), reproduisant la queue lourde de DBLP mais avec moins de clustering.

## Conclusion : 
1. DBLP est un réseau petit monde avec loi de puissance et clustering élevé.
2. BA capture la loi de puissance et les distances moyennes, mais pas le clustering.
3. ER capture seulement les distances moyennes (si n grand), mais pas la loi de puissance ni le clustering.
4. Les modèles génératifs permettent d'approximer certaines caractéristiques, mais aucun modèle simple ne reproduit parfaitement toutes les propriétés du réseau réel.

# --- TP2 : Propagation dans des réseaux ---

## 1. Propagation d’un virus sur le réseau DBLP

### Modèle de propagation

Nous utilisons un modèle de type **SIS (Susceptible – Infecté – Susceptible)** :

- **S (Susceptible)** : individu sain mais pouvant être infecté  
- **I (Infecté)** : individu infecté pouvant transmettre le virus  

La mise à jour de l’anti-virus permet de guérir un individu, mais ne l’immunise pas.
Le virus pouvant muter, un individu peut donc être infecté plusieurs fois au cours
du temps.

---

### 1.1 Taux de propagation du virus

#### Taux de transmission (β)

On suppose qu’un individu envoie en moyenne **un mail par semaine** à chacun de ses
collaborateurs et qu’un mail infecté transmet le virus.

Le pas de temps de la simulation étant le **jour**, on a :

- 1 semaine = 7 jours  
- 1 contact infectieux par semaine et par lien  

Ainsi, le taux de transmission est :

**β = 1 / 7 ≈ 0,143 par jour**

#### Taux de guérison (μ)

On suppose que les individus mettent à jour leur anti-virus **environ deux fois par
mois**. Chaque mise à jour permet de guérir complètement l’individu.

En considérant qu’un mois dure environ 30 jours, on obtient :

**μ = 2 / 30  = 1 / 15 ≈ 0,067 par jour**

#### Taux de propagation effectif

Dans le modèle SIS, le taux de propagation du virus est défini par :

**λ = β / μ**

Dans notre cas :

**λ ≈ 0,143 / 0,067 ≈ 2,1**

Le **taux de propagation du virus est donc λ ≈ 2,1**.

---

### 1.2 Seuil épidémique du réseau DBLP

À partir de l’analyse du réseau DBLP, nous calculons le **degré moyen ⟨k⟩** ainsi que
le **moment d’ordre deux ⟨k²⟩**. Le réseau DBLP présente une distribution des degrés
hétérogène, de type **loi de puissance**, caractéristique des réseaux **sans échelle**.

Dans ce type de réseau, le seuil épidémique est donné par :

**λc = ⟨k⟩ / ⟨k²⟩**

Or, dans le réseau DBLP, la valeur de ⟨k²⟩ est très élevée, ce qui rend le seuil
épidémique **extrêmement faible**, proche de zéro.

On peut donc considérer que :

**le seuil épidémique du réseau DBLP est quasiment nul (λc ≈ 0)**.

Cela signifie que même un virus faiblement contagieux peut se maintenir dans le
temps. Les nœuds fortement connectés (appelés *hubs*) jouent un rôle important en
facilitant la propagation de l’infection.

---

### 1.3 Comparaison avec un réseau aléatoire

Pour un réseau aléatoire de type **Erdős–Rényi** ayant le même degré moyen ⟨k⟩,
le seuil épidémique est donné par :

**λc(ER) = 1 / ⟨k⟩**

Avec ⟨k⟩ ≈ 6,6, on obtient :

**λc(ER) ≈ 0,15**

| Réseau               | Seuil épidémique |
|----------------------|------------------|
| **DBLP (réel)**      | ≈ 0              |
| **Réseau aléatoire** | ≈ 0,15           |
| **Virus (λ)**        | ≈ 2,1            |

Le seuil du réseau DBLP est donc **beaucoup plus faible** que celui d’un réseau
aléatoire de même degré moyen. Le virus se propage facilement dans le réseau DBLP,
même pour de faibles valeurs de λ, ce qui montre la **vulnérabilité des réseaux
sans échelle aux épidémies**.

## 2. Simulation de la propagation du virus

Nous simulons la propagation du virus **jour par jour pendant trois mois (90 jours)** sur le réseau DBLP,
selon un modèle SIS.  
Afin de limiter l’influence des conditions initiales (choix du patient zéro, tirages aléatoires),
chaque scénario est simulé **10 fois**, et les résultats présentés correspondent à la **moyenne**
des simulations.

La grandeur observée est la **fraction d’individus infectés parmi la population non immunisée**.

voici la courbe obtenue après simulation de la propagation du virus avec les 3 scénarios :
![Simulation de la propagation du virus](comparaison_propagation.png)

---

### 2.1 Scénario 1 : aucune immunisation

Dans ce premier scénario, aucun individu ne met à jour son anti-virus de façon permanente.

On observe sur la courbe que :
- la fraction d’infectés augmente très rapidement,
- l’épidémie atteint un plateau après environ 25 jours,
- plus de **60 % de la population non immunisée** reste infectée à long terme.

Le virus devient donc **endémique** dans le réseau.  
Cela est cohérent avec le seuil épidémique quasi nul du réseau DBLP mis en évidence à la question 1.

---

### 2.2 Scénario 2 : immunisation aléatoire (50 %)

Dans ce scénario, **50 % des individus sont immunisés aléatoirement** dès le début de la simulation.

On constate que :
- la propagation du virus est nettement ralentie,
- la fraction maximale d’infectés est fortement réduite,
- le plateau se situe autour de **30 %** de la population non immunisée.

L’immunisation aléatoire permet donc de **réduire l’impact de l’épidémie**, mais ne suffit pas
à l’éliminer complètement. Le virus continue à circuler dans le réseau.

---

### 2.3 Scénario 3 : immunisation sélective (50 %)

Dans ce dernier scénario, **50 % des individus sont choisis au hasard**, mais ce sont **leurs voisins**
qui sont immunisés. Cette stratégie cible donc indirectement les nœuds les plus connectés.

Les résultats montrent que :
- la propagation est très fortement freinée,
- la fraction d’infectés reste toujours **inférieure à 5 %**,
- aucun véritable régime endémique ne s’installe.

L’épidémie est presque totalement contrôlée, malgré le même pourcentage d’individus immunisés
que dans le scénario précédent.

---

### 2.4 Conclusion

Ces simulations montrent que :
- sans intervention, le virus se propage rapidement et persiste dans le réseau,
- l’immunisation aléatoire est efficace mais reste limitée,
- l’immunisation sélective est **de loin la stratégie la plus efficace**.

Cette différence s’explique par la structure du réseau DBLP : les individus les plus connectés
(hubs) jouent un rôle central dans la diffusion du virus. Les cibler indirectement permet
de casser les principales chaînes de transmission.

Ces résultats confirment que, dans les réseaux sans échelle, **une stratégie d’immunisation
sélective est bien plus efficace qu’une immunisation aléatoire**, à coût égal.

## 3. Justification de l'efficacité de l'immunisation sélective

Pour justifier mathématiquement pourquoi l'immunisation sélective (Scénario 3) écrase la courbe de l'épidémie par rapport à l'immunisation aléatoire (Scénario 2), nous avons comparé les caractéristiques structurelles des deux groupes.

### 3.1 Résultats des mesures

En analysant un échantillon représentatif de 10 000 nœuds, nous avons obtenu les résultats suivants :

| Groupe | Méthode de sélection | Degré moyen ( contacts ) |
| :--- | :--- | :--- |
| **Groupe 0** | Individus choisis au hasard | **6,71** |
| **Groupe 1** | Amis des individus du Groupe 0 | **18,34** |

**Observation :** Le degré moyen du Groupe 1 est **2,73 fois supérieur** à celui du Groupe 0.

### 3.2 Explication théorique

Dans un réseau hétérogène comme DBLP :
1. Les individus avec un haut degré (les **hubs**) ont, par définition, beaucoup d'amis. 
2. Par conséquent, ils apparaissent beaucoup plus souvent comme "voisin de quelqu'un" que les individus peu connectés.
3. En choisissant une personne au hasard (Groupe 0), on a peu de chances de tomber sur un hub. Mais en choisissant **un ami** d'une personne au hasard (Groupe 1), on a une probabilité très élevée d'atteindre un hub.



### 3.3 Lien avec l'efficacité vaccinale

L'immunisation sélective est bien plus efficace car elle ne "gaspille" pas de vaccins sur des nœuds isolés. En ciblant les voisins, on cible indirectement les **nœuds stratégiques** qui servent de ponts pour le virus. 

Puisque le Groupe 1 a un degré moyen de **18,34** (contre 6,71 pour le reste), chaque vaccin distribué dans ce groupe neutralise un individu capable de contaminer presque trois fois plus de personnes qu'un individu moyen. Cela augmente artificiellement le **seuil épidémique** du réseau jusqu'à stopper la propagation.

## 4. Modification du seuil épidémique

L’immunisation d’un individu est, du point de vue du virus, équivalente à sa **suppression définitive** du réseau (puisqu’il ne peut plus être infecté ni transmettre le virus). Pour justifier l'efficacité des stratégies, nous avons recalculé le seuil épidémique du réseau après avoir physiquement supprimé les nœuds immunisés.

### 4.1 Formules mathématiques utilisées

Le seuil critique $\lambda_c$ d'un réseau, en dessous duquel une épidémie finit par s'éteindre, est calculé à l'aide des moments de la distribution des degrés :

* **Degré moyen ($\langle k \rangle$)** : $\langle k \rangle = \frac{1}{N} \sum k_i$
* **Moment d'ordre deux ($\langle k^2 \rangle$)** : $\langle k^2 \rangle = \frac{1}{N} \sum k_i^2$
* **Seuil épidémique ($\lambda_c$)** : 
    $$\lambda_c = \frac{\langle k \rangle}{\langle k^2 \rangle}$$



### 4.2 Comparaison des seuils recalculés

Après simulation de la suppression de 50% des nœuds selon les deux stratégies, nous obtenons les résultats suivants :

| État du réseau | Seuil épidémique ($\lambda_c$) |
| :--- | :--- |
| **Initial (réseau complet)** | **0,0460** |
| **Après immunisation aléatoire** | **0,0846** |
| **Après immunisation sélective** | **0,1810** |

### 4.3 Analyse des résultats

* **Réseau Initial** : Le seuil est extrêmement bas, ce qui explique pourquoi le virus se propage très vite dans le scénario sans contrôle.
* **Immunisation Aléatoire** : Le seuil augmente légèrement mais reste faible. Supprimer des nœuds au hasard ne garantit pas la suppression des **hubs**. Le réseau conserve donc une variance des degrés élevée ($\langle k^2 \rangle$ important), ce qui maintient le seuil à une valeur basse.
* **Immunisation Sélective** : On observe une augmentation majeure du seuil (plus de **3,9 fois supérieur** au seuil initial). En immunisant les voisins, on cible prioritairement les hubs. La suppression de ces nœuds très connectés fait baisser énormément la valeur de $\langle k^2 \rangle$.

### 4.4 Conclusion

L'immunisation sélective est la stratégie la plus efficace car elle augmente le seuil critique du réseau. En supprimant les hubs (les nœuds les plus connectés), on rend le réseau plus "homogène", ce qui crée une barrière mathématique plus forte contre le virus. L'épidémie finit par s'éteindre car le virus ne parvient plus à se transmettre assez vite pour compenser le nouveau seuil de tolérance du réseau ainsi modifié.

## 5. Comparaison : Réseau aléatoire vs Attachement préférentiel

Pour conclure notre étude, nous avons cherché à savoir si l'efficacité des stratégies d'immunisation dépendait de la structure du réseau. Nous avons donc généré deux réseaux artificiels ayant la même taille (N≈317000) et le même degré moyen (⟨k⟩≈6,6) que DBLP, mais avec des modes de construction différents :

![Comparaison : Réseau aléatoire vs Attachement préférentiel](comparaison_globale_tp.png)

- **Réseau aléatoire (Modèle Erdős–Rényi):** Les liens sont créés au hasard de façon uniforme.

- **Réseau à attachement préférentiel (Modèle Barabási–Albert) :** Les nouveaux nœuds se connectent prioritairement aux nœuds déjà très connectés (création de hubs).

### 5.1. Comparaison des simulations

Nous avons lancé la simulation SIS avec les trois mêmes scénarios sur ces deux réseaux. Les résultats obtenus sont présentés sur le graphique ci-dessous :

### 5.2. Analyse du réseau aléatoire (ER)

Sur le graphique (courbes oranges), on observe un comportement très différent de DBLP :

- **Absence de différence stratégique :** Les courbes d'immunisation aléatoire (tirets) et sélective (pointillés) sont quasiment confondues.

- **Explication :** Dans un réseau aléatoire, les degrés sont homogènes (tout le monde a environ le même nombre de contacts). Comme il n'y a pas de hubs, le "paradoxe de l'amitié" ne fonctionne pas : l'ami d'un individu n'est pas plus connecté qu'un autre. La stratégie sélective perd donc tout son intérêt.

### 5.3. Analyse du réseau à attachement préférentiel (BA)

Sur le graphique (courbes violettes), on observe un comportement similaire à DBLP :

- **Efficacité de la sélection :** L'immunisation sélective écrase la courbe de l'infection par rapport à l'immunisation aléatoire.

- **Explication :** Ce modèle reproduit la présence de hubs. En ciblant les voisins, on neutralise les nœuds centraux du réseau, ce qui stoppe l'épidémie.

### 5.4. Conclusion de la comparaison

Cette expérience prouve que :

- L'efficacité de l'immunisation sélective **dépend entièrement de la structure du réseau**.

- Le réseau **DBLP se comporte comme un réseau à attachement préférentiel**. La réussite de la stratégie sélective sur DBLP confirme mathématiquement que ce réseau réel est organisé autour de hubs très connectés.


| Type de réseau        | Stratégie gagnante | Structure identifiée                |
|----------------------|--------------------|-------------------------------------|
| Aléatoire (ER)       | Aucune (résultats similaires) | Homogène (sans hubs)                |
| Préférentiel (BA)    | Sélective          | Hétérogène (avec hubs)               |
| DBLP (réel)          | Sélective          | Hétérogène (scale-free)              |


En conclusion, le réseau DBLP est vulnérable à cause de ses hubs, mais c'est précisément cette vulnérabilité qui nous permet de le protéger efficacement en utilisant une stratégie d'immunisation ciblée.