Théorie des réseaux
Composantes, distances et petit monde
- 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 6 : Composantes, distances et petit monde
Les composantes
Ce qu’on observe dans les grands réseaux
Presque tous les grands réseaux réels ont une composante qui contient la majorité des nœuds, et une poussière de petites composantes autour.
| Réseau | Part dans la géante |
|---|---|
| Web (Broder et al., 2000) | \approx 90\,\% |
| Coauteurs en physique | \approx 85\,\% |
| Interbancaire européen | > 95\,\% |
Il en faut très peu
Le chapitre 7 démontrera qu’au-delà d’un seuil de densité très bas, une composante géante apparaît presque sûrement.
Il faut très peu de liens pour qu’un réseau devienne connexe : c’est le premier résultat contre-intuitif du domaine.
Le calcul des distances
Le parcours en largeur
On explore par couches : les voisins du départ sont à distance 1, leurs voisins non encore vus à distance 2, et ainsi de suite.
Coût : O(n + m) pour un sommet, donc O(n(n+m)) pour toutes les paires.
| Couche | Nœuds | Distance |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 2, 3 | 1 |
| 2 | 4 | 2 |
| 3 | 5 | 3 |
| 4 | 6, 7 | 4 |
L’excentricité et ses résumés
L’excentricité de i : \ e(i) = \max_j d(i,j).
Le diamètre : \max_i e(i). Le rayon : \min_i e(i).
Les nœuds d’excentricité minimale forment le centre du graphe.
| Nœud | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| e(i) | 4 | 4 | 3 | \mathbf{2} | 3 | 4 | 4 |
Diamètre 4, rayon 2, centre = \{4\}.
Le centre du graphe
Cinquième mesure, cinquième fois qu’il ressort — et toujours pour la même raison géométrique.
Le centre d’un graphe minimise le pire cas, ce qui en fait le bon emplacement pour un entrepôt, un serveur ou une caserne.
Le petit monde
L’expérience de Milgram
Des habitants du Nebraska devaient faire parvenir une lettre à un agent de change de Boston, en la remettant à une connaissance personnelle susceptible de le rapprocher.
Médiane des chaînes abouties : cinq intermédiaires — d’où l’expression six degrés de séparation.
Sur 296 lettres envoyées, 64 seulement sont arrivées.
La médiane porte donc sur les chaînes abouties : les chaînes longues avaient plus d’occasions de s’interrompre. Le chiffre est biaisé vers le bas, et il faut le dire.
Sur Facebook en 2016, la distance moyenne mesurée sur 1{,}6 milliard de comptes vaut 3{,}57.
Ici, aucun biais d’attrition : le réseau entier est observé. Le fait tient, même si l’expérience de 1967 le prouvait mal.
Pourquoi le monde est petit
L’argument de croissance
Si chacun a \bar{k} contacts sans recoupement, le nombre de personnes atteintes en \ell pas vaut \bar{k}^{\,\ell}.
Atteindre n personnes demande donc \ell \approx \frac{\ln n}{\ln \bar{k}}
Avec n = 8 \times 10^9 et \bar{k} = 100 :
\ell \approx \frac{22{,}8}{4{,}6} \approx 5
Une croissance logarithmique
Multiplier la population par mille n’ajoute que trois pas.
C’est cela, le petit monde : pas que les distances soient courtes, mais qu’elles croissent extraordinairement lentement.
Le problème que cet argument ignore
Vos amis se connaissent entre eux : le clustering est élevé, donc \bar{k}^{\,\ell} surestime largement l’atteinte.
Or un réseau très clusterisé a des distances longues, pas courtes. Un réseau régulier en anneau a un diamètre de l’ordre de n.
Les réseaux réels ont à la fois un clustering élevé — comme un anneau — et des distances courtes — comme un graphe aléatoire.
Aucun des deux modèles ne produit les deux à la fois. C’est l’énigme que le chapitre 8 résoudra en une ligne.
Ce qu’il faut retenir
Le résumé du chapitre
- Les grands réseaux ont une composante géante qui contient l’essentiel des nœuds.
- Le BFS calcule les distances en O(n+m) par sommet.
- Sur notre réseau : diamètre 4, rayon 2, centre = \{4\}.
- Milgram (1967) : cinq intermédiaires — mais sur 64 chaînes abouties sur 296.
- Facebook (2016) confirme sans biais : distance moyenne 3{,}57.
- La distance croît comme \ln n / \ln \bar{k} : très lentement.
Le chapitre 7 construit le premier modèle de formation : on relie chaque paire au hasard, et l’on regarde ce qui en sort. Ce sera à la fois très instructif et manifestement faux.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)