Théorie spectrale des graphes

En mathématiques, 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. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée.

Matrices décrivant un graphe

modifier

Matrice d'adjacence

modifier

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)
     

Matrice des degrés et laplacienne

modifier

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 non normalisée  .

On obtient sa forme normalisée   par  , où   est la matrice identité. On obtient aussi   directement par chacun de ses éléments :

 

Matrice d'incidence

modifier

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

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

La matrice du graphe est définie 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 où le graphe est un chemin et la supérieure est atteinte pour le 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 inférieures, égales ou supérieures à 0.
  •    est le nombre chromatique et   la plus petite valeur propre.


Spectre de la matrice laplacienne normalisée

modifier

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 est 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

Analyse des réseaux

modifier

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

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
  1. a b et c (en) Dragos M. Cvetkovic, Michael Doob et Horst Sachs, Spectra of Graphs, Heidelberg et Leipzig, Academic Press, (réimpr. 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