Théorie des réseaux
La matrice d’adjacence et l’algèbre 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 2 : La matrice d’adjacence et l’algèbre des graphes
La matrice d’adjacence
La définition
A_{ij} = \begin{cases} 1 & \text{si } ij \in E\\ 0 & \text{sinon}\end{cases}
Pour un graphe non orienté, \mathbf{A} est symétrique et sa diagonale est nulle.
\mathbf{A} = \begin{pmatrix} 0&1&1&0&0&0&0\\ 1&0&1&0&0&0&0\\ 1&1&0&1&0&0&0\\ 0&0&1&0&1&0&0\\ 0&0&0&1&0&1&1\\ 0&0&0&0&1&0&1\\ 0&0&0&0&1&1&0 \end{pmatrix}
Ce qu’elle donne immédiatement
Le degré est la somme d’une ligne : k_i = \sum_j A_{ij}.
Le nombre d’arêtes vaut m = \tfrac{1}{2}\sum_{ij}A_{ij}.
Le vecteur des degrés s’écrit \mathbf{k} = \mathbf{A}\mathbf{1}.
Sur 49 cases, 16 valent 1. Sur un réseau de 10^5 nœuds et 10^6 arêtes, la proportion tombe à 2 \times 10^{-4}.
On ne stocke jamais la matrice d’un grand réseau : on stocke la liste des arêtes.
Puissances et chemins
Le résultat
(\mathbf{A}^r)_{ij} \;=\; \text{nombre de parcours de longueur exactement } r \text{ de } i \text{ vers } j
Un parcours peut repasser par un sommet — contrairement à un chemin.
(\mathbf{A}^2)_{ij} = \sum_h A_{ih}A_{hj}
Chaque terme vaut 1 si h est voisin de i et de j. La somme compte donc les intermédiaires possibles — c’est-à-dire les parcours de longueur 2.
Ce qu’on en tire
(\mathbf{A}^2)_{ii} = k_i : les parcours de longueur 2 qui reviennent sont les aller-retours vers un voisin.
(\mathbf{A}^3)_{ii} = 2 \times le nombre de triangles contenant i.
\operatorname{trace}(\mathbf{A}^3) = 6 \times le nombre total de triangles.
Deux triangles : \{1,2,3\} et \{5,6,7\}.
\operatorname{trace}(\mathbf{A}^3) = 6 \times 2 = 12
Compter les triangles d’un réseau d’un million de nœuds par énumération est hors de portée.
Le compter par une trace de produit matriciel est une opération d’algèbre linéaire creuse — quelques secondes.
Les autres matrices
Le laplacien
\mathbf{L} = \mathbf{D} - \mathbf{A}, \qquad \mathbf{D} = \operatorname{diag}(k_1,\dots,k_n)
\mathbf{L} est symétrique, semi-définie positive, et la somme de chaque ligne est nulle.
\mathbf{L}\mathbf{1} = \mathbf{0}
donc 0 est toujours valeur propre. Sa multiplicité est le nombre de composantes connexes.
Compter les composantes d’un réseau revient à compter les zéros du spectre de \mathbf{L}.
La deuxième plus petite valeur propre — la connectivité algébrique de Fiedler — mesure à quel point le graphe est difficile à couper. C’est l’outil du chapitre 9.
La matrice stochastique
P_{ij} = \frac{A_{ij}}{k_i}
P_{ij} est la probabilité qu’un marcheur en i passe en j. Chaque ligne somme à 1.
Sur un graphe connexe non biparti, la marche converge vers \pi_i = \frac{k_i}{2m}
La fraction du temps passée en un nœud est proportionnelle à son degré. C’est l’idée dont PageRank est une variante — et c’est le chapitre 4.
Le spectre
Le rayon spectral
La plus grande valeur propre de \mathbf{A}. Pour un graphe connexe, elle est simple et son vecteur propre est strictement positif — théorème de Perron-Frobenius.
\bar{k} \;\leq\; \lambda_1 \;\leq\; k_{\max}
\bar{k} = 2{,}29 \;\leq\; \lambda_1 \approx 2{,}343 \;\leq\; 3 = k_{\max}
Le polynôme caractéristique se réduit, par symétrie du réseau, à \lambda^3 - \lambda^2 - 4\lambda + 2 = 0.
Pourquoi lambda 1 nous intéressera
Le seuil épidémique — une contagion se propage si le taux de transmission dépasse 1/\lambda_1 (chapitre 10).
La centralité de vecteur propre — le vecteur propre associé la définit (chapitre 4).
La stabilité d’un jeu en réseau — l’équilibre existe et est unique si \lambda_1 est assez petit (chapitre 11).
Trois questions économiques sans rapport apparent — épidémie, pouvoir, équilibre — dépendent du même nombre.
C’est l’argument le plus fort en faveur de l’approche par les réseaux : elle unifie ce que l’intuition sépare.
Ce qu’il faut retenir
Le résumé du chapitre
- \mathbf{A} code le graphe ; \mathbf{k} = \mathbf{A}\mathbf{1}, m = \tfrac12 \sum A_{ij}.
- (\mathbf{A}^r)_{ij} compte les parcours de longueur r.
- \operatorname{trace}(\mathbf{A}^3) = 6 \times le nombre de triangles — ici 12.
- Le laplacien \mathbf{L} = \mathbf{D} - \mathbf{A} compte les composantes par ses zéros.
- La marche aléatoire a pour loi stationnaire \pi_i = k_i/2m.
- \lambda_1 \approx 2{,}343 gouvernera le seuil épidémique, la centralité spectrale et l’équilibre des jeux.
Le chapitre 3 pose la question centrale du cours : qui est important dans un réseau ? Il y répond de trois façons différentes, qui ne donnent pas le même classement.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)