Théorie spectrale des graphes

Théorie spectrale des graphes

La théorie spectrale des graphes s'intéresse aux rapports entre le spectre d'un graphe et ses propriétés, et fait partie de la théorie algébrique des graphes. Un graphe peut-être représenté par plusieurs matrices, et les valeurs propres d'une matrice constituent son spectre. On s'intéresse en général à la matrice d'adjacence et la matrice laplacienne normalisée.

Sommaire

Matrices et leurs relations

Soit un graphe G = (V,E), où V dénote l'ensemble des sommets et E l'ensemble des arêtes. Le graphe possède | V | = n sommets, dénotés par v_1, \cdots, v_n \in V et | E | = m arêtes, dénotées par 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 Dii correspondent au nombre de connexions 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 = DA; on obtient sa forme normalisée L' par L' = D − 1 / 2LD − 1 / 2 = ID − 1 / 2AD − 1 / 2, où I dénote 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 a } 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 | x | E | dans laquelle l'entrée bij vaut 1 si le sommet vi est une extrémité de l'arête xj, 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 λ est la puissance du monôme (X − λ) dans le polynôme caractéristique (i.e. 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 PG(λ) = | λIA | , mais on peut aussi s'intéresser à des variantes[1] telles que RG(λ) = | λIDA | ou QG(λ) = | D | − 1 * | λDA | .

Spectre de la matrice d'adjacence

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 ρ(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 ρ(A) = k et la multiplicité de ρ(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 − ρ(A) est aussi une valeur propre.
  • S'il y a k 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 ,p0,p + sont respectivement le nombre de valeurs propres plus petites, égales ou supérieures à 0.</math>.
  • \frac{\rho(A)}{-q} + 1 \le \chi(G) \le \rho(A) + 1χ(G) est le nombre chromatique et q la plus petite valeur propre.

Spectre de la matrice laplacienne normalisée

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

  • λ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 λ1 > 0. Si λ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

Analyse des réseaux

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

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.

Références

  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)

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorie spectrale des graphes de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Théorie spectrale — des graphes La théorie spectrale des graphes s intéresse aux rapports entre le spectre d un graphe et ses propriétés, et fait partie de la théorie algébrique des graphes. Un graphe peut être représenté par plusieurs matrices, et les valeurs… …   Wikipédia en Français

  • Théorie des graphes — Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une théorie informatique et mathématique. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette… …   Wikipédia en Français

  • Lexique De La Théorie Des Graphes — Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique de la theorie des graphes — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique en théorie des graphes — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique de la théorie des graphes — Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Acyclique (grap …   Wikipédia en Français

  • Theorie des graphes — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”