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]

Matrice d'adjacence[modifier | modifier le code]

Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées . Chaque élément de la matrice d'adjacence du graphe est défini par :

Graphe Représentation par une matrice d'adjacence Représentation par une matrice laplacienne (non normalisée)
6n-graf.svg

Matrice des degrés et laplacienne[modifier | modifier le code]

La matrice des degrés est une matrice diagonale où les éléments correspondent au nombre de liens du sommet , c'est-à-dire à son degré. En utilisant cette matrice et la précédente, on peut également définir la matrice laplacienne  ; on obtient sa forme normalisée par , où est la matrice identité, ou on peut aussi l'obtenir directement par chacun de ses éléments :

Matrice d'incidence[modifier | modifier le code]

Enfin, la matrice d'incidence d'un graphe est la matrice de dimensions dans laquelle l'élément vaut 1 si le sommet est une extrémité de l'arête , et 0 sinon. On a l'ensemble de relations suivantes[1], où désigne la matrice identité :

  • Pour la matrice d'adjacence du line graph ,
  • Pour la matrice d'adjacence du graphe de subdivision ,

Notion de spectre, et de polynôme caractéristique[modifier | modifier le code]

Le spectre d'une matrice est l'ensemble de ses valeurs propres  ; si elles sont réelles, nous convenons de les classer : . Par extension, on parle du spectre du graphe. On rappelle que la multiplicité algébrique d'une valeur propre est la puissance du monôme 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 (appelé polynôme caractéristique du graphe), mais on peut aussi s'intéresser à des variantes[1] telles que ou .

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 est la matrice adjointe de . 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 de la matrice, c'est-à-dire sa plus grande valeur propre, satisfait 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 -régulier alors et la multiplicité de donne le nombre de composantes connexes.
  • Le graphe ne contient un cycle de longueur impaire que si est aussi une valeur propre[réf. nécessaire].
  • S'il y a valeurs propres distinctes, alors le diamètre satisfait .
  • La taille du stable maximum satisfait sont respectivement le nombre de valeurs propres plus petites, égales ou supérieures à 0.
  • est le nombre chromatique et la plus petite valeur propre.

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

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

  • .
  • si le graphe est connexe.
  • Si et que G soit un graphe complet alors , sinon .
  • Si le graphe est connexe alors . Si et alors a exactement composantes (i.e. graphes connexes).
  • .

Le théorème de Kirchhoff (aussi appelé matrix-tree theorem) donne une relation entre le nombre d'arbres couvrants et la matrice laplacienne.

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]

Article détaillé : Partitionnement spectral.

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]. On parle de partitionnement spectral. 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)

Liens externes[modifier | modifier le code]