Introduction

L’analyse spectrale des graphes repose sur l’étude des valeurs propres et vecteurs propres des matrices associées au graphe, notamment la matrice d’adjacence $A$, la matrice de degré $D$, et la matrice de Laplacien $L=D−A$. Ces matrices capturent les différentes facettes de la structure du graphe et permettent d’en extraire des informations profondes sur sa connectivité, sa bipartition ou encore ses communautés.

Quelques faits clés (sans démonstration ici) :

• Les valeurs propres de \(A\) décrivent la structure globale du graphe, par exemple la présence de communautés ou la régularité du graphe.
• Pour un graphe non orienté, \(L\) possède toujours une valeur propre égale à \(0\). Le nombre de valeurs propres nulles est exactement le nombre de composantes connexes du graphe.
• La plus petite valeur propre strictement positive de \(L\) (souvent notée \(\lambda_2\), la « Fiedler value ») mesure en un certain sens la qualité de la connexité : plus \(\lambda_2\) est grande, plus le graphe est « bien connecté ».
• Pour un graphe biparti, comme évoqué plus haut, le spectre de \(A\) est symétrique : si \(\lambda\) est valeur propre, \(-\lambda\) en est aussi une. Cela permet de reconnaître la bipartité par des critères purement algébriques.

Un exemple typique d’application est le clustering spectral : on diagonalise (ou on approxime) la matrice \(L_{\text{norm}}\), on regarde quelques vecteurs propres associés aux plus petites valeurs propres, puis on applique un algorithme de clustering classique (comme \(k\)-means) dans cet espace réduit.

En pratique, on évite de calculer toutes les valeurs propres : on utilise des méthodes itératives (power iteration, Lanczos) adaptées aux matrices creuses.

Reference interessante : math.uchicago

Matrice de degré et Laplacien

On définit d’abord la matrice de degré \(D\) comme une matrice diagonale où : $D_{ii} = \deg(x_i), \quad D_{ij} = 0 \text{ si } i \ne j. $ Dit autrement :
\[ D_{ii} = \deg(i) = \sum_{j=1}^n A_{ij}. \]

Pour un graphe non orienté simple (sans boucle), la matrice de Laplacien est donnée par : $L = D - A$. Cette matrice est symétrique, définie positive, et joue pour les graphes un rôle analogue à l’opérateur laplacien en analyse (diffusion, chaleur, etc.).

• Matrice d’adjacence $A$
  • Elle encode la structure de connexion du graphe.
  • Son spectre (ensemble de valeurs propres) reflète la présence de motifs ou de sous-structures.
• Matrice de degré $D$
  • Elle mesure la densité locale de chaque nœud
• Matrice de Laplacien $L$
  • Elle compare la valeur en un sommet à la moyenne de ses voisins (diffusion, chaleur, lissage).
  • Si un sommet est très différent de ses voisins, la valeur associee sera grande
  • Utilisee en analyse d’image : https://homepages.inf.ed.ac.uk/rbf/HIPR2/log.htm
  • Dit autrement c’est une derivee spatial

On peut aussi définir un laplacien normalisé (utile en clustering spectral) via $L_{\text{norm}} = I - D^{-1/2} A D^{-1/2}$, lorsque tous les degrés sont strictement positifs. Concernant $D^{-1/2}$, c’est très simple puisque $D$ est diagonal. On peu prednre le raccouci suivant :

\[ D = \begin{bmatrix} d_1 & 0 & 0 \\ 0 & d_2 & 0 \\ 0 & 0 & d_3 \end{bmatrix} ; D^{-1/2} = \begin{bmatrix} \frac{1}{\sqrt{d_1}} & 0 & 0 \\ 0 & \frac{1}{\sqrt{d_2}} & 0 \\ 0 & 0 & \frac{1}{\sqrt{d_3}} \end{bmatrix} \]

import numpy as np

A = np.array([
    [0, 1, 1],
    [1, 0, 0],
    [1, 0, 0]
])

deg = A.sum(axis=1)

# laplacien
D = np.diag(deg)
L = D - A

# laplacien normalisé
D_inv_sqrt = np.diag(1/np.sqrt(deg))
I = np.eye(len(A))
L_norm = I - D_inv_sqrt @ A @ D_inv_sqrt

Valeurs et vecteurs propres

On considère une matrice carrée \(M\). Une valeur propre \(\lambda\) et un vecteur propre non nul \(v\) satisfont : $M v = \lambda v$. Autrement dit, $(M - \lambda I)v = 0$. Dit autrement c’est un systeme d’equation polynomial.

Pour trouver les valeurs propres :

1. On cherche les \(\lambda\) tels que le système \((M - \lambda I)v = 0\) admette une solution non triviale (autre que \(v = 0\)).
2. Cela arrive exactement quand \(\det(M - \lambda I) = 0\).
3. On résout donc l’équation caractéristique \(\det(M - \lambda I) = 0\) (polynôme en \(\lambda\)).
4. Les racines obtenues sont les valeurs propres.

Pour chaque valeur propre \(\lambda\) :

1. On remplace \(\lambda\) dans \(M - \lambda I\).
2. On résout le système linéaire \((M - \lambda I)v = 0\).
3. Les solutions non nulles \(v\) forment l’espace propre associé à \(\lambda\)

En pratique :

• à la main, on fait cela uniquement pour des petites matrices (2×2, 3×3), pour des exercices etudiants …
• donc pour comprendre et potentielement implementer ces fonctions sur ordinateur …
• globalement on utilisera des fonctions numériques (numpy.linalg.eig, scipy.linalg.eig, etc.)

\(Lf\) et interprétation

Si \(f : V \to \mathbb{R}\) est une fonction sur les sommets, que l’on voit comme un vecteur \(f \in \mathbb{R}^n\), alors la \(i\)-ème composante de \(Lf\) vaut
\[ (Lf)_i = \deg(i)\, f(i) - \sum_{j \sim i} f(j), \]
où la somme porte sur les voisins \(j\) de \(i\).

• Si \(f(i)\) est très différent de la moyenne de \(f\) sur les voisins de \(i\), alors \((Lf)_i\) est grand en valeur absolue.
• Si \(f\) est “lisse” sur le graphe (les voisins ont des valeurs proches), alors \(Lf\) est petit.

On peut donc voir \(L\) comme un opérateur qui mesure le désaccord local entre un sommet et ses voisins.

Connexité et valeurs propres

Pour un graphe simple non orienté \(G\) avec Laplacien \(L = D - A\) :

1. \(L\) est symétrique et semi‑définie positive : toutes ses valeurs propres sont réelles et \(\lambda_i \ge 0\).
2. \(0\) est toujours une valeur propre de \(L\), avec pour vecteur propre associé le vecteur constant \(\mathbf{1} = (1,\dots,1)^\top\).
3. Le nombre de valeurs propres nulles de \(L\) est exactement le nombre de composantes connexes de \(G\).

Le fait que \(L\) soit symétrique vient de ce que \(A\) et \(D\) le sont. Pour la semi‑définie positivité, on montre que pour tout \(x \in \mathbb{R}^n\), ce qui force toutes les valeurs propres à être non négatives.

\[ x^\top L x = \frac{1}{2} \sum_{\{i,j\} \in E} (x_i - x_j)^2 \ge 0, \]

La nullité correspond à \(x_i = x_j\) pour tout \(\{i,j\} \in E\) : sur chaque composante connexe, \(x\) doit être constant. Le nombre de degrés de liberté (constantes indépendantes) est donc le nombre de composantes connexes.

Caleur de Fiedler

On note $0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n$ les valeurs propres de \(L\), comptées avec multiplicité. La valeur \(\lambda_2\) est appelée valeur de Fiedler, et un vecteur propre associé \(v_2\) est appelé vecteur de Fiedler.

• Si \(\lambda_2 > 0\), le graphe est connexe. Si \(\lambda_2 = 0\), il est déconnecté.
• Plus \(\lambda_2\) est grande, plus le graphe est “bien connecté” : il n’existe pas de coupure de petite capacité qui sépare le graphe en deux gros morceaux.
• Les composantes de \(v_2\) varient doucement et se regroupent souvent en deux blocs (valeurs positives vs négatives), ce qui suggère une partition naturelle du graphe en deux sous‑ensembles.

Fiedler partition

Soit un graphe avec deux communautés faiblement connectées (par quelques arêtes seulement). On calcule \(L\), puis ses deux plus petites valeurs propres. On vérifie que \(\lambda_1 = 0\) et que \(\lambda_2\) est très proche de 0.

• Le vecteur propre \(v_2\) a des composantes positives sur la première communauté, et négatives sur la seconde (ou l’inverse).
• En séparant les sommets selon le signe de \(v_2(i)\), on obtient une coupure de Fiedler, souvent proche de la meilleure coupure possible.

Graphes bipartis

Un graphe non orienté \(G = (V,E)\) est biparti s’il existe une partition de l’ensemble des sommets \(V = U \cup W\) telle que :

• \(U \cap W = \emptyset\),
• chaque arête \(\{i,j\} \in E\) relie un sommet de \(U\) à un sommet de \(W\).

Autrement dit, il n’y a aucune arête entre deux sommets de \(U\), ni entre deux sommets de \(W\).

Théorème (forme bloc de \(A\)) Si \(G\) est biparti avec partition \(V = U \cup W\), alors on peut réordonner les sommets (mettre d’abord ceux de \(U\), puis ceux de \(W\)) de sorte que la matrice d’adjacence \(A\) s’écrive sous la forme bloc \(B\) est la matrice de bi‑adjacence entre \(U\) et \(W\) :

\[ A = \begin{pmatrix} 0 & B \\ B^\top & 0 \end{pmatrix}, \]

Cette écriture reflète exactement le fait qu’il n’y a pas d’arêtes internes dans \(U\) ni dans \(W\) (blocs diagonaux nuls), seulement des arêtes entre les deux parties (blocs \(B\) et \(B^\top\)).

from collections import deque

def bipartition(adj_list):
    n = len(adj_list)
    color = [-1] * n
    for s in range(n):
        if color[s] != -1:
            continue
        color[s] = 0
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in adj_list[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return None  # non biparti
    U = [i for i in range(n) if color[i] == 0]
    W = [i for i in range(n) if color[i] == 1]
    return U, W

import numpy as np

def reorder_adjacency(A, U, W):
    perm = np.array(U + W)
    A_perm = A[np.ix_(perm, perm)]
    return A_perm, perm

Interprétation spectrale

Pour un graphe biparti, le spectre de \(A\) est symétrique par rapport à 0 : si \(\lambda\) est valeur propre de \(A\), alors \(-\lambda\) l’est aussi, avec la même multiplicité.

Idée. Dans la forme bloc :

\[ A = \begin{pmatrix} 0 & B \\ B^\top & 0 \end{pmatrix}, \]

on vérifie que si \((x, y)^T\) est un vecteur propre de valeur propre \(\lambda\), alors \((x, -y)^T\) est vecteur propre de valeur propre \(-\lambda\). D’où la symétrie du spectre.

Extraction des deux parties

On peut utiliser un critère spectral pour retrouver la bipartition :

• On calcule la plus grande valeur propre \(\lambda_{\max}\) de \(A\) et un vecteur propre associé \(v\).
• Pour un graphe biparti connexe, on sait (Perron‑Frobenius adapté) qu’il existe un vecteur propre pour \(-\lambda_{\max}\) qui s’obtient en changeant le signe sur une des deux parties.
• En pratique, on regarde le signe des composantes de \(v\) (ou d’un vecteur propre de \(-\lambda_{\max}\)) :
  • indices où \(v_i > 0\) ⇒ première classe,
  • indices où \(v_i < 0\) ⇒ seconde classe.

Cela marche bien pour des graphes “fortement” bipartis ou des sous‑graphes bipartis, et peut servir de base à des heuristiques pour trouver de grands sous‑graphes bipartis… La suite peut devenir complexe et surtout hors programme.