README.md

# 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**.