Théorie des réseaux
Le vocabulaire des graphes
- 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 1 : Le vocabulaire des graphes
La définition
Un graphe
G = (V, E)
V l’ensemble des sommets — ou nœuds —, E celui des arêtes — ou liens.
n = |V| est la taille, m = |E| le nombre d’arêtes.
V = \{1,2,3,4,5,6,7\}, \qquad n = 7
E = \{12,\ 13,\ 23,\ 34,\ 45,\ 56,\ 57,\ 67\}, \qquad m = 8
Quatre variantes
Orienté — l’arête a un sens : i \to j diffère de j \to i.
Pondéré — l’arête porte une intensité : montant, fréquence, durée.
Signé — l’arête porte un signe : alliance ou hostilité.
Biparti — deux types de sommets, les arêtes ne relient que des types différents.
Prêts interbancaires : orienté et pondéré — qui prête combien à qui.
Coauteurs d’un article : non orienté. Administrateurs et conseils d’administration : biparti.
Se tromper de variante fausse toutes les mesures qui suivent.
Le degré
La définition
k_i = |\,\{\,j : ij \in E\,\}\,|
En orienté, on distingue le degré entrant k_i^{\text{in}} et le degré sortant k_i^{\text{out}}.
| Nœud | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| k_i | 2 | 2 | 3 | 2 | 3 | 2 | 2 |
Le lemme des poignées de main
\sum_{i \in V} k_i \;=\; 2m
Chaque arête est comptée deux fois : une par extrémité.
2+2+3+2+3+2+2 = 16 = 2 \times 8
Le degré moyen vaut donc \bar{k} = \frac{2m}{n} = \frac{16}{7} \approx 2{,}29
Le premier théorème de la théorie des graphes
La somme des degrés est toujours paire. Le nombre de sommets de degré impair l’est aussi.
C’est le premier théorème de la théorie des graphes, dû à Euler en 1736 — et il suffit à réfuter bien des réseaux mal saisis.
Chemins et distances
Les définitions
Un chemin est une suite de sommets consécutivement reliés, sans répétition.
Sa longueur est son nombre d’arêtes.
La distance d(i,j) est la longueur du plus court chemin entre i et j ; elle vaut +\infty s’il n’y en a aucun.
d(1,2) = 1 \qquad d(1,4) = 2 \qquad d(1,5) = 3 \qquad d(1,6) = 4
Le chemin 1 \to 3 \to 4 \to 5 \to 6 est le plus court possible entre 1 et 6.
Diamètre et distance moyenne
\text{diametre} = \max_{i,j} d(i,j) \qquad \bar{d} = \frac{1}{\binom{n}{2}} \sum_{i<j} d(i,j)
Le diamètre vaut 4 : c’est la distance entre \{1,2\} et \{6,7\}.
La somme des 21 distances vaut 46, donc \bar{d} = \frac{46}{21} \approx 2{,}190
Le diamètre est le pire cas : il est sensible à un seul sommet excentré.
La distance moyenne décrit le cas courant. Un réseau de diamètre 12 et de distance moyenne 3 est un petit monde avec une queue — pas un réseau étiré.
Connexité
Les composantes
Un ensemble maximal de sommets deux à deux joignables.
Un graphe est connexe s’il n’a qu’une composante.
Fortement connexe : tout sommet est joignable depuis tout autre en respectant le sens.
Faiblement connexe : c’est vrai si l’on oublie les sens.
Une seule composante, de sept sommets. Toutes les distances sont finies, ce qui rend les mesures du chapitre 3 calculables sans précaution.
Ponts et points d’articulation
Un pont est une arête dont la suppression augmente le nombre de composantes.
Un point d’articulation est un sommet dont la suppression fait de même.
Les arêtes 3–4 et 4–5 sont des ponts. Les sommets 3, 4 et 5 sont des points d’articulation.
Retirer le nœud 4 coupe le réseau en deux triangles isolés.
Un pont est une vulnérabilité et une rente à la fois.
Vulnérabilité pour le système : sa disparition le fragmente. Rente pour celui qui l’occupe : rien ne passe sans lui. Le chapitre 3 chiffre cette rente, et le chapitre 13 en fait un critère de régulation.
Ce qu’il faut retenir
Le résumé du chapitre
- Un graphe est G = (V,E) ; il peut être orienté, pondéré, signé, biparti.
- Le degré compte les voisins ; \sum_i k_i = 2m, toujours pair.
- Notre réseau : n = 7, m = 8, \bar{k} \approx 2{,}29.
- La distance est la longueur du plus court chemin ; diamètre 4, moyenne 2{,}190.
- Diamètre et distance moyenne disent des choses différentes : pire cas et cas courant.
- Les arêtes 3–4 et 4–5 sont des ponts ; le nœud 4 est un point d’articulation.
Le chapitre 2 range tout cela dans une matrice — et découvre que les puissances de cette matrice comptent les chemins, ce qui donnera les centralités du chapitre 4.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)