README.md

# Mesures de réseaux d'interaction

**TP: Analyse du réseau de collaboration scientifique DBLP**

---

## Introduction

Nous analysons un réseau de collaboration scientifique en informatique extrait de la base de données DBLP (Digital Bibliography & Library Project). Ce réseau représente les collaborations entre chercheurs, où chaque nœud est un auteur et chaque arête indique une co-publication.

**Source des données**: [SNAP - DBLP Collaboration Network](https://snap.stanford.edu/data/com-DBLP.html)

**Outils utilisés**:
- Java 11 avec Maven
- [GraphStream](https://graphstream-project.org/) pour l'analyse de réseau
- gnuplot pour les visualisations

---

## Question 1: Chargement des données

### Méthode
Nous utilisons [`FileSourceEdge`](https://graphstream-project.org/gs-core/org/graphstream/stream/file/FileSourceEdge.html) de GraphStream pour charger le fichier de données au format liste d'arêtes.

```java
Graph graph = new SingleGraph("DBLP");
FileSourceEdge fs = new FileSourceEdge();
fs.addSink(graph);
fs.readAll("src/main/resources/snap/com-dblp.ungraph.txt");
```

### Statistiques du graphe chargé
- **Nombre de nœuds**: 317,080 auteurs
- **Nombre d'arêtes**: ~1,049,866 collaborations
- **Type**: Graphe non dirigé

### Note sur la visualisation
La visualisation directe du graphe complet n'est pas recommandée en raison de sa taille (317k nœuds). Elle serait extrêmement lente et peu informative visuellement.

---

## Question 2: Mesures de base

### Résultats pour le réseau DBLP

| Métrique | Valeur |
|----------|--------|
| Nombre de nœuds | 317,080 |
| Nombre d'arêtes | 1,049,866 |
| Degré moyen | 6.62 |
| Coefficient de clustering | **0.632** |

### Comparaison avec un réseau aléatoire théorique

Pour un réseau aléatoire de même taille (N = 317,080) et même degré moyen (<k> = 6.62), le coefficient de clustering théorique serait:

**C_aléatoire = <k> / N = 6.62 / 317,080 ≈ 0.0000209**

### Analyse

Le coefficient de clustering du réseau DBLP (0.632) est environ **30,000 fois plus élevé** qu'un réseau aléatoire équivalent!

**Interprétation**: Ce clustering extrêmement élevé indique que le réseau DBLP présente une forte structure en communautés. Si deux chercheurs A et B collaborent tous deux avec un chercheur C, ils ont une forte probabilité de collaborer ensemble. C'est une caractéristique typique des réseaux sociaux où "l'ami de mon ami est probablement mon ami" (propriété de transitivité).

---

## Question 3: Connexité du réseau

### Réseau DBLP
- **Connexe**: Oui
- **Nombre de composantes connexes**: 1

Le réseau DBLP forme une seule grande composante connexe, ce qui signifie qu'il existe un chemin entre n'importe quelle paire de chercheurs dans le réseau.

### Réseau aléatoire de même taille et degré moyen

Avec N = 317,080 et <k> = 6.62:
- **Connexe**: Oui
- Un réseau aléatoire avec ces paramètres est également connexe

### Degré critique pour la connexité

#### Théorie
Pour un réseau aléatoire de taille N, le degré moyen critique au-dessus duquel le réseau devient connexe est:

**<k>_critique ≈ ln(N)**

Pour N = 317,080:
**<k>_critique ≈ ln(317,080) ≈ 12.67**

#### Résultats expérimentaux
Par échantillonnage et génération de réseaux aléatoires, nous avons trouvé expérimentalement un degré critique d'environ **12.5**, ce qui correspond très bien à la prédiction théorique.

### Conclusion
Le réseau DBLP (avec <k> = 6.62) est en dessous du seuil théorique mais reste connexe car il ne s'agit pas d'un réseau purement aléatoire. Sa structure en communautés avec clustering élevé assure la connexité même avec un degré moyen plus faible.

---

## Question 4: Distribution des degrés

### Visualisations

#### Échelle linéaire
![Distribution linéaire](output/images/dd_dblp_linear.png)

En échelle linéaire, on observe une queue lourde ("heavy tail") avec de nombreux nœuds de faible degré et quelques nœuds de très haut degré (hubs).

#### Échelle log-log
![Distribution log-log](output/images/dd_dblp_loglog.png)

**Observation cruciale**: En échelle log-log, la distribution forme une **ligne droite** sur plusieurs ordres de grandeur.

### Interprétation: Loi de puissance

La linéarité en échelle log-log indique que la distribution suit une **loi de puissance**:

```math
p_k = C \cdot k^{-\gamma}
```

où:
- `p_k` = probabilité qu'un nœud ait degré k
- `C` = constante de normalisation
- `γ` = exposant de la loi de puissance

#### Fit avec gnuplot

![Fit loi de puissance](output/images/dd_powerlaw_fit.png)

Résultats du fit (en excluant les petits degrés k < 10):
- **γ = 2.70 ± 0.04**
- **C ≈ 0.0002**

Cet exposant γ ≈ 2.7 est typique des réseaux sans échelle ("scale-free networks") et cohérent avec les valeurs observées dans d'autres réseaux sociaux (généralement entre 2 et 3).

### Comparaison avec la distribution de Poisson

![Comparaison avec Poisson](output/images/dd_comparison.png)

La distribution de Poisson (en rouge) ne correspond pas du tout aux données DBLP. La distribution de Poisson est caractéristique des réseaux aléatoires, alors que DBLP suit une loi de puissance, caractéristique des réseaux à attachement préférentiel.

### Conclusions

1. **Le réseau DBLP est un réseau sans échelle (scale-free)**: La distribution des degrés suit une loi de puissance avec γ ≈ 2.7

2. **Présence de hubs**: Quelques auteurs très prolifiques (haut degré) coexistent avec de nombreux auteurs moins connectés

3. **Pas un réseau aléatoire**: La distribution de Poisson ne modélise pas ce réseau

4. **Mécanisme probable**: Attachement préférentiel ("rich get richer") - les auteurs établis attirent plus de nouvelles collaborations

---

## Question 5: Distance moyenne

### Méthode
Calcul par échantillonnage pour des raisons de performance:
- Sélection aléatoire de **1,000 nœuds**
- Parcours en largeur (BFS) depuis chaque nœud
- Estimation de la distance moyenne sur ~317 millions de paires de nœuds

### Résultats

| Métrique | Valeur |
|----------|--------|
| Distance moyenne | **6.84** |
| Distance maximale observée | 23 |

### Hypothèse des "six degrés de séparation"

**CONFIRMÉE**

La distance moyenne de 6.84 confirme la célèbre hypothèse des "six degrés de séparation" qui stipule que deux personnes quelconques sont reliées par une chaîne de maximum 6 intermédiaires.

### Comparaison avec un réseau aléatoire théorique

Pour un réseau aléatoire, la distance moyenne théorique est:

```math
\ell \approx \frac{\ln(N)}{\ln(\langle k \rangle)} = \frac{\ln(317080)}{\ln(6.62)} \approx 6.5
```

Le réseau DBLP (6.8) est légèrement plus grand qu'un réseau aléatoire équivalent (6.5), ce qui est attendu car la structure en communautés augmente légèrement les distances.

### Distribution des distances

![Distribution des distances](output/images/distances_dblp.png)

La distribution est concentrée autour de 6-7 avec une forme en cloche caractéristique d'un réseau "petit monde" (small world).

### Conclusion: Réseau petit monde

Le réseau DBLP est un **réseau petit monde** (small-world network) caractérisé par:
1. **Courte distance moyenne** (~6.8)
2. **Clustering élevé** (0.632)

Cette combinaison (distances courtes + clustering élevé) est la signature des réseaux petit monde, par opposition aux réseaux aléatoires (distances courtes mais clustering faible) ou aux réseaux réguliers (clustering élevé mais longues distances).

---

## Question 6: Comparaison avec les générateurs

### Réseaux générés

Nous avons généré deux réseaux synthétiques avec des paramètres similaires au réseau DBLP:

1. **Réseau aléatoire** (modèle d'Erdős-Rényi)
   - Génération aléatoire d'arêtes
   - Même nombre de nœuds et degré moyen

2. **Réseau Barabási-Albert** (attachement préférentiel)
   - Nouveaux nœuds se connectent préférentiellement aux nœuds déjà bien connectés
   - Génère une loi de puissance

### Tableau comparatif

| Métrique | DBLP | Aléatoire | Barabási-Albert |
|----------|------|-----------|-----------------|
| Nœuds | 317,080 | 50,000* | 50,000* |
| Degré moyen | 6.62 | 6.62 | 6.62 |
| **Clustering** | **0.632** | **~0.00002** | **~0.005** |
| Distance moyenne | 6.8 | 6.5 | ~5.2 |
| **Exposant γ** | **2.70** | **N/A** | **~3.0** |
| Connexe | Oui | Oui | Oui |

*Taille réduite pour des raisons de performance computationnelle

### Visualisation comparative

![Comparaison des distributions](output/images/comparison_all_networks.png)

### Analyse des résultats

#### Réseau Aléatoire (Erdős-Rényi)
- **Distribution de Poisson**, pas de loi de puissance
- **Clustering extrêmement faible** (~0.00002)
- Distances courtes
- **Conclusion**: Inadéquat pour modéliser les réseaux sociaux

#### Réseau Barabási-Albert
- **Loi de puissance** avec γ ≈ 3.0
- Présence de hubs
- **Clustering très faible** (~0.005, soit **126× moins** que DBLP)
- Distances courtes
- **Conclusion**: Reproduit la loi de puissance mais échoue à capturer le clustering élevé

#### Réseau DBLP
- **Loi de puissance** avec γ ≈ 2.7
- **Clustering très élevé** (0.632)
- Distances courtes
- **Propriété unique**: Combine loi de puissance ET clustering élevé

### Conclusions

1. **Le modèle aléatoire est inadéquat**: Il ne capture ni la structure en loi de puissance ni le clustering

2. **Le modèle de Barabási-Albert est insuffisant**: Bien qu'il reproduise la loi de puissance (attachement préférentiel), il ne génère pas le clustering élevé observé dans les réseaux sociaux réels

3. **DBLP a des propriétés uniques**: La combinaison d'une distribution en loi de puissance avec un clustering élevé nécessite des mécanismes plus sophistiqués que le simple attachement préférentiel

4. **Implications**: Les réseaux sociaux réels ont des mécanismes de formation plus complexes, probablement incluant:
   - Attachement préférentiel (explique la loi de puissance)
   - Formation de triangles (explique le clustering)
   - Structure en communautés

---

## Question 7 (BONUS): Générateur par copie

### Motivation

Le modèle de Barabási-Albert reproduit la loi de puissance mais pas le clustering élevé. Peut-on faire mieux avec une méthode alternative?

### Algorithme proposé

Pour chaque nouveau nœud u:
1. Choisir un nœud v au hasard
2. Pour chaque voisin w de v:
   - Se connecter à w avec probabilité p
3. Se connecter à v (toujours)

### Intuition

Cet algorithme crée naturellement des **triangles** (clustering) car:
- Le nouveau nœud se connecte à v
- Il se connecte aussi aux voisins de v
- Si deux voisins de v sont connectés, on crée un triangle

### Résultats

Test avec p = 0.3 (réseau de 50,000 nœuds):

| Métrique | Valeur |
|----------|--------|
| Nombre d'arêtes | 124,330 |
| **Degré moyen** | **4.97** |
| **Coefficient de clustering** | **0.48** |

### Comparaison du clustering

| Modèle | Coefficient de clustering | Ratio |
|--------|---------------------------|-------|
| DBLP | 0.632 | 1.0× |
| **Copie (p=0.3)** | **0.48** | **0.76×** |
| Barabási-Albert | 0.005 | 0.008× |
| Aléatoire | 0.00002 | 0.00003× |

**Amélioration vs Barabási-Albert**: **96×** plus de clustering!

#### Visualisation

![Comparaison clustering (échelle linéaire)](output/images/clustering_comparison.png)

![Comparaison clustering (échelle log)](output/images/clustering_comparison_log.png)

L'échelle logarithmique permet de mieux visualiser les différences entre tous les modèles, notamment les très faibles valeurs du modèle aléatoire et de Barabási-Albert.

### Note importante: Choix de p=0.3

Avec des valeurs élevées de p (0.5 et 0.7), l'algorithme de copie présente un **comportement naturellement explosif**:

- **p=0.5**: Degré moyen ≈ 21.23, clustering ≈ 0.44
- **p=0.7**: Degré moyen ≈ 253+, clustering décroît

**Explication**: Plus le graphe grandit, plus les nœuds accumulent de voisins. Quand on choisit un nœud `v` avec beaucoup de voisins et qu'on se connecte à p% d'entre eux, le nombre de connexions explose rapidement. Ce phénomène est intrinsèque à l'algorithme de copie.

**Pourquoi p=0.3?** C'est la valeur optimale qui offre le meilleur compromis:
- Clustering élevé (0.48) proche de DBLP (0.632)
- Degré moyen raisonnable (≈5) sans explosion
- 96× meilleur que Barabási-Albert sur le clustering

### Analyse

#### Avantages
- **Clustering beaucoup plus élevé** que Barabási-Albert
- Se rapproche davantage des réseaux réels
- Mécanisme intuitivement plausible pour les réseaux sociaux

#### Limitations
- La distribution des degrés n'est pas parfaitement une loi de puissance pure
- Compromis à trouver entre degré moyen et clustering (via le paramètre p)
- Clustering encore inférieur à DBLP (0.48 vs 0.632)
- Degré moyen plus faible que DBLP (4.97 vs 6.62) avec p=0.3

### Conclusions

1. **Le générateur par copie améliore significativement le clustering** par rapport au modèle de Barabási-Albert

2. **Formation naturelle de triangles**: La méthode de copie crée automatiquement des structures triangulaires caractéristiques des réseaux sociaux

3. **Compromis nécessaire**: Le paramètre p permet d'ajuster le compromis entre degré moyen et clustering

4. **Modélisation plus réaliste**: Ce modèle capture mieux certaines propriétés des réseaux sociaux réels, bien que le réseau DBLP conserve des caractéristiques que même ce modèle avancé ne reproduit pas parfaitement

5. **Pistes d'amélioration**: Pour mieux modéliser DBLP, on pourrait combiner:
   - Attachement préférentiel (loi de puissance)
   - Mécanisme de copie (clustering)
   - Structure en communautés explicite

---

## Conclusions générales

### Caractéristiques du réseau DBLP

Le réseau de collaboration DBLP présente toutes les caractéristiques d'un **réseau social complexe**:

1. **Réseau sans échelle (scale-free)**
   - Distribution des degrés en loi de puissance: p_k ∝ k^(-2.7)
   - Présence de hubs (auteurs très prolifiques)

2. **Réseau petit monde (small-world)**
   - Distance moyenne courte: ~6.8
   - Clustering élevé: 0.632

3. **Structure en communautés**
   - Clustering 30,000× plus élevé qu'un réseau aléatoire
   - Formation de groupes de recherche densément connectés

### Mécanismes de formation

Les propriétés observées suggèrent plusieurs mécanismes:

1. **Attachement préférentiel**: Les auteurs établis attirent plus de nouvelles collaborations (→ loi de puissance)

2. **Transitivité sociale**: Si A collabore avec B et C, alors B et C ont une forte probabilité de collaborer (→ clustering élevé)

3. **Communautés thématiques**: Groupes de chercheurs travaillant sur des thèmes similaires (→ clustering localisé)

### Limitations des modèles théoriques

- **Erdős-Rényi (aléatoire)**: Complètement inadéquat
- **Barabási-Albert**: Capture la loi de puissance mais pas le clustering
- **Copie**: Améliore le clustering mais reste en deçà de la réalité

**Leçon**: Les réseaux sociaux réels sont plus complexes que les modèles simples et nécessitent des mécanismes multiples et synergiques.

### Implications scientifiques

1. **Pour la science**: Le réseau DBLP révèle la structure de la recherche en informatique avec des communautés thématiques et des chercheurs centraux

2. **Pour la modélisation**: Il faut combiner plusieurs mécanismes (attachement préférentiel + clustering + communautés) pour reproduire fidèlement les réseaux sociaux

3. **Universalité**: Ces propriétés (loi de puissance, petit monde, clustering) se retrouvent dans de nombreux autres réseaux: réseaux sociaux en ligne, réseaux biologiques, Internet, etc.

---

## Instructions d'exécution

### Compilation

```bash
mvn clean compile
```

### Exécution du programme

```bash
mvn exec:java
```

Le programme affiche un menu interactif permettant d'exécuter chaque question séparément ou toutes en séquence.

### Génération des graphiques

Après avoir exécuté les analyses, les données sont exportées dans `output/data/`. Pour générer les graphiques:

```bash
cd gnuplot
gnuplot plot_dd_linear.gnu
gnuplot plot_dd_loglog.gnu
gnuplot plot_dd_powerlaw.gnu
gnuplot plot_dd_comparison.gnu
gnuplot plot_distances.gnu
gnuplot plot_comparison_networks.gnu
gnuplot plot_clustering_comparison.gnu
gnuplot plot_clustering_comparison_log.gnu
```

Les images PNG seront générées dans `output/images/`.

### Temps d'exécution estimés

- Question 1 (Chargement): ~30-60 secondes
- Question 2 (Mesures de base): ~2-3 minutes
- Question 3 (Connexité): ~3-5 minutes
- Question 4 (Distribution): ~5 minutes
- **Question 5 (Distances): ~15-25 minutes** (temps long)
- **Question 6 (Générateurs): ~30-40 minutes** (temps long)
- **Question 7 (Bonus copie): ~15-20 minutes** (temps long)

**Total pour exécution complète**: ~1h30

---

## Références

### Données
- [SNAP Stanford: DBLP Collaboration Network](https://snap.stanford.edu/data/com-DBLP.html)

### Outils
- [GraphStream](https://graphstream-project.org/) - Library Java pour l'analyse de graphes
- [GraphStream Toolkit Documentation](https://graphstream-project.org/gs-algo/org/graphstream/algorithm/Toolkit.html)
- [gnuplot](http://www.gnuplot.info/) - Outil de visualisation

### Articles scientifiques
- Barabási, A.-L., & Albert, R. (1999). *Emergence of Scaling in Random Networks*. Science, 286(5439), 509-512.
- Watts, D. J., & Strogatz, S. H. (1998). *Collective dynamics of 'small-world' networks*. Nature, 393(6684), 440-442.
- Newman, M. E. J. (2001). *The structure of scientific collaboration networks*. PNAS, 98(2), 404-409.

---

**Auteur**: Hamadou BA
**Cours**: TP - Mesures de réseaux d'interaction