Théorie des réseaux
Le graphe aléatoire d’Erdos et Renyi
- Présentation du cours
- Pourquoi les réseaux en économie
- Le vocabulaire des graphes
- La matrice d'adjacence et l'algèbre des graphes
- Les centralités locales
- Les centralités spectrales
- Densité, clustering et assortativité
- Composantes, distances et petit monde
- Le graphe aléatoire d'Erdos et Renyi
- Petit monde et attachement préférentiel
- La détection de communautés
- La diffusion sur un réseau
- Les jeux en réseau
- L'identification des effets de pairs
- Réseaux financiers et risque systémique
- Réseaux de production et chocs sectoriels
- Mise en œuvre sur R et Python
Théorie des réseaux
Chapitre 7 : Le graphe aléatoire d’Erdos et Renyi
Le modèle
La définition
n sommets. Chaque paire est reliée indépendamment avec probabilité p.
Il n’y a rien d’autre : aucune préférence, aucune histoire, aucune géographie.
\mathbb{E}[m] = p\binom{n}{2} \qquad \bar{k} = p(n-1) \qquad k_i \sim \mathcal{B}(n-1,\, p)
Aucun réseau réel ne se forme au hasard. Mais il faut un point de comparaison.
Dire qu’un réseau est « très clusterisé » n’a de sens que par rapport à ce qu’un hasard pur produirait à densité égale.
La distribution des degrés
De la binomiale à Poisson
Quand n \to \infty à \bar{k} fixé, p = \bar{k}/(n-1) \to 0 et
\mathbb{P}(k_i = k) \;\longrightarrow\; e^{-\bar{k}}\,\frac{\bar{k}^{\,k}}{k!}
Elle est concentrée autour de sa moyenne : son écart-type vaut \sqrt{\bar{k}}.
Avec \bar{k} = 6, l’écart-type vaut 2{,}45. Un nœud de degré 100 a une probabilité de l’ordre de 10^{-70}.
Les réseaux réels contiennent des nœuds de degré cent ou mille fois la moyenne : un aéroport, une banque centrale, une page très citée.
Erdős-Rényi les déclare impossibles. C’est son échec principal, et le chapitre 8 y répondra.
La transition de phase
Le résultat d’Erdos et Renyi
Le comportement de G(n,p) dépend de \bar{k} :
\bar{k} < 1 : \text{ composantes de taille } O(\ln n) \bar{k} = 1 : \text{ composante de taille } O(n^{2/3}) \bar{k} > 1 : \text{ composante geante, de taille } O(n)
Chaque nœud atteint en moyenne \bar{k} nouveaux nœuds à chaque pas.
Si \bar{k} < 1, l’exploration s’éteint comme un processus de branchement sous-critique. Si \bar{k} > 1, elle explose. Le seuil est exactement 1.
Le calcul de la taille géante
Soit S la fraction des nœuds dans la composante géante. Elle vérifie
S = 1 - e^{-\bar{k}S}
| \bar{k} | S |
|---|---|
| 0{,}9 | 0{,}00 |
| 1{,}5 | 0{,}58 |
| 2 | 0{,}80 |
| 3 | 0{,}94 |
| 5 | 0{,}99 |
Ce que la courbe révèle
Deux liens par nœud suffisent à connecter 80\,\% du réseau. Cinq en connectent 99\,\%.
C’est ce qui explique la composante géante universelle du chapitre 6 : elle ne demande presque rien.
Ce que le modèle rate
Le clustering
Deux voisins de i sont reliés avec probabilité p, indépendamment de tout. Donc
\mathbb{E}[C] = p = \frac{\bar{k}}{n-1}
| Réseau | C observé | C attendu |
|---|---|---|
| Coauteurs (physique) | 0{,}45 | 0{,}00018 |
| Internet | 0{,}39 | 0{,}00060 |
| Acteurs de cinéma | 0{,}79 | 0{,}00027 |
Un écart de trois ordres de grandeur
Ce n’est pas une imprécision : c’est un échec qualitatif.
Le hasard pur ne ferme pas les triangles, parce qu’il ignore que les amis de vos amis ont une raison particulière de se rencontrer.
Le bilan
Réussi : distances courtes, en \ln n / \ln \bar{k} ; composante géante au-delà de \bar{k} = 1.
Manqué : le clustering, trop faible de trois ordres de grandeur ; la distribution des degrés, qui interdit les hubs.
Le modèle a identifié exactement ce qu’il faut expliquer.
Un modèle faux qui isole deux anomalies précises est plus utile qu’un modèle vague qui n’en isole aucune. Les chapitres 8 et 9 répondent aux deux, l’un après l’autre.
Ce qu’il faut retenir
Le résumé du chapitre
- G(n,p) relie chaque paire indépendamment avec probabilité p.
- Les degrés suivent une loi de Poisson : concentrée, sans hubs possibles.
- Transition de phase en \bar{k} = 1 : au-delà, une composante géante apparaît.
- S = 1 - e^{-\bar{k}S} : deux liens par nœud connectent 80\,\% du réseau.
- Le clustering prédit vaut p : mille fois trop faible.
- Le modèle réussit les distances, échoue sur le clustering et les hubs.
Le chapitre 8 corrige les deux défauts par deux idées distinctes : quelques raccourcis pour le clustering, et une règle d’attachement pour les hubs.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)