Théorie spectrale des graphes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes (en). On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée.

Matrices décrivant un graphe[modifier | modifier le code]

Soit un graphe G = (V, E), où V désigne l'ensemble des sommets et E l'ensemble des arêtes. Le graphe possède |V| = n sommets, notés v_1, \cdots, v_n \in V et |E| = m arêtes, notées e_{ij}, v_i \in S, v_j \in S. Chaque élément de la matrice d'adjacence A du graphe G est défini par :

a_{ij}=\left\{\begin{array}{rl}
	1 & \mbox{si } (v_i,v_j)\in E \\
        0 & \mbox{sinon.}
\end{array}\right.
Graphe Représentation par une matrice d'adjacence Représentation par une matrice laplacienne (non normalisée)
6n-graf.svg
\begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 0\\
1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0\\
\end{pmatrix}
\begin{pmatrix}
 2 & -1 &  0 &  0 & -1 &  0\\
-1 &  3 & -1 &  0 & -1 &  0\\
 0 & -1 &  2 & -1 &  0 &  0\\
 0 &  0 & -1 &  3 & -1 & -1\\
-1 & -1 &  0 & -1 &  3 &  0\\
 0 &  0 &  0 & -1 &  0 &  1\\
\end{pmatrix}

La matrice des degrés D est une matrice diagonale où les éléments D_{ii} correspondent au nombre de liens du sommet i, c'est-à-dire à son degré. En utilisant cette matrice et la précédente, on peut également définir la matrice laplacienne L=D-A ; on obtient sa forme normalisée L' par L' = D^{-1/2}LD^{-1/2} = I - D^{-1/2}AD^{-1/2}, où I est la matrice identité, ou on peut aussi l'obtenir directement par chacun de ses éléments :

\ell_{i,j}:=
\begin{cases}
1 & \mbox{si}\ i = j\ \mbox{et}\ \deg(v_i) \neq 0\\
-\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} & \mbox{si}\ i \neq j\ \mbox{et}\ v_i \text{ est adjacent à } v_j \\
0 & \text{sinon}.
\end{cases}

Enfin, la matrice d'incidence M d'un graphe G = (V, E) est la matrice de dimensions |V| \times |E| dans laquelle l'élément b_{ij} vaut 1 si le sommet v_i est une extrémité de l'arête x_j, et 0 sinon. On a l'ensemble de relations suivantes[1], où I dénote la matrice identité :

Le spectre d'une matrice est l'ensemble de ses valeurs propres \lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1} ; par extension, on parle du spectre du graphe. On rappelle que la multiplicité algébrique d'une valeur propre \lambda est la puissance du monôme (X - \lambda) dans le polynôme caractéristique (c'est-à-dire la multiplicité de la racine dans le polynôme caractéristique). Il est également possible de modifier le polynôme caractéristique pour prendre en compte d'autres propriétés du graphe : on considère par défaut le polynôme P_G( \lambda ) = | \lambda I - A | (appelé polynôme caractéristique du graphe), mais on peut aussi s'intéresser à des variantes[1] telles que R_G( \lambda ) = |\lambda I - D - A| ou Q_G( \lambda ) = |D|^{-1} \cdot | \lambda D - A |.

Spectre de la matrice d'adjacence[modifier | modifier le code]

La matrice du graphe est positive, et elle ne peut être réduite si le graphe est connexe. Dans le cas d'un graphe non-orienté, la matrice est symétrique et hermitienne, c'est-à-dire que A^\dagger = AA^\dagger est la matrice adjointe de A. La trace de la matrice est égale au nombre de boucles : en effet, un élément sur la diagonale indique la présence d'une boucle et la trace est la somme de ces éléments. Nous avons les propriétés suivantes[1] :

  • Le rayon spectral \rho (A) de la matrice, c'est-à-dire sa plus grande valeur propre, satisfait 2 \cdot \cos(\frac{\pi}{n + 1}) \le \rho (A) \le n - 1 pour un graphe connexe. La borne inférieure est atteinte dans le cas d'un chemin et la supérieure par un graphe complet.
  • Si le graphe est k-régulier alors \rho (A) = k et la multiplicité de \rho(A) donne le nombre de composantes connexes.
  • Il existe une valeur propre nulle si et seulement si le graphe ne contient pas de cycle.
  • Le graphe ne contient un cycle de longueur impaire que si - \rho (A) est aussi une valeur propre.
  • S'il y a m valeurs propres distinctes, alors le diamètre D satisfait D \le m - 1.
  • La taille t du stable maximum satisfait t \le p_0 + \min(p_-,p_+)p_-,p_0,p_+ sont respectivement le nombre de valeurs propres plus petites, égales ou supérieures à 0.
  • \frac{\rho(A)}{-q} + 1 \le \chi(G) \le \rho(A) + 1\chi(G) est le nombre chromatique et q la plus petite valeur propre.

Spectre de la matrice laplacienne normalisée[modifier | modifier le code]

La valeur propre \lambda_1 est appelée la connectivité algébrique du graphe. Les propriétés essentielles du spectre sont résumées ci-dessous[2] :

  • \lambda_0 = 0.
  • \sum_i \lambda_i \le n si le graphe est connexe.
  • Si n \ge 2 et que G est un graphe complet alors \lambda_1 = \frac{n}{n-1}, sinon \lambda_1 \le 1.
  • Si le graphe est connexe alors \lambda_1 > 0. Si \lambda_i = 0 et \lambda_{i+1} \neq 0 alors G a exactement i+1 composantes (i.e. graphes connexes).
  • \lambda_i \le 2 \forall i \le n - 1.

Parmi les autres propriétés de cette matrice, son déterminant donne le nombre d'arbres couvrants du graphe.

Applications[modifier | modifier le code]

Analyse des réseaux[modifier | modifier le code]

La plupart des mesures effectuées sur des réseaux concernent le coefficient de clustering, la distance moyenne ou la distribution des degrés : l'utilisation des techniques spectrales est minoritaire, mais « les expériences en pratique suggèrent que l'analyse spectrale peut être bien adaptée aux données irrégulières [...] tandis que le coefficient de clustering est bien adapté pour les données plus régulières (et a donc été utilisé abondamment par les physiciens pour l'étude des grilles, cristaux, etc.) »[3]. En particulier, le spectre de différents échantillons de l'Internet au niveau des routeurs a été mesuré[3] : les auteurs de l'étude ont observé des différences au niveau géographique, proposant comme explication que le réseau en Amérique du Nord soit à un stade plus avancé que celui d'Asie et d'Europe; ces mesures ont aussi été comparées à celles relevées sur des modèles visant à être représentatifs de propriétés trouvées dans l'Internet, et essentiellement aucun des modèles ne correspondait à l'Internet au niveau du spectre.

Partitionnement de graphe[modifier | modifier le code]

L'analyse des vecteurs propres de la matrice laplacienne du graphe dans ce que l'on appelle la méthode spectrale, permet de trouver une partition du graphe[4]. Cette méthode a des applications dans des domaines aussi divers que la répartition de tâches en calcul parallèle, la segmentation d'image, la résolution de systèmes linéaires, etc.

Notes et références[modifier | modifier le code]

  1. a, b et c (en) Dragos M. Cvetkovic et Michael Doob et Horst Sachs - Spectra of Graphs, Heidelberg, Leipzig, 1994, (ISBN 3335004078).
  2. (en) Fan Chung - Spectral Graph Theory, Regional Conference Series in Mathematics, numéro 92, publié par l'American Mathematical Society, 1997
  3. a et b (en) Christos Gkantsidis, Milena Mihail et Ellen Zegura - Spectral Analysis of Internet Topologies, IEEE Infocom, 2003.
  4. (fr) Charles-Edmond Bichot - La méthode multiniveaux, chapitre du livre Partitionnement de graphe coordonné par Charles-Edmond Bichot et Patrick Siarry, Hermes-Lavoisier, p51-87, 2010. (ISBN 9782746230057)