Opérateur linéaire agissant sur les fonctions définies sur les sommets d'un graphe, donné classiquement par L = D − A où D est la matrice diagonale des degrés et A la matrice d'adjacence ; il encode la diffusion discrète et la régularité locale sur le graphe.

Principe

Agissant sur une fonction de sommet, le laplacien calcule le flux net (la différence entre la valeur au sommet et la moyenne de ses voisins) et sa décomposition spectrale organise les modes de variation, la connectivité et les vitesses de diffusion.

Démonstration

Pour un graphe non orienté pondéré, (Lf)(i)=∑_j w_{ij}(f(i)−f(j)) ; la multiplicité de la valeur propre nulle égale le nombre de composantes connexes et la deuxième plus petite valeur propre (connectivité algébrique) quantifie les goulots d'étranglement.

Mauvaise application

Employer le laplacien non normalisé sans compenser l'hétérogénéité des degrés quand on compare des graphes aux degrés de sommet très variables ; cela peut fausser le clustering spectral et l'interprétation de la diffusion.

Conséquence

Les valeurs et vecteurs propres du laplacien renseignent sur la connectivité, les temps de mélange des marches aléatoires, et servent pour la réduction de dimension, le lissage et le partitionnement du graphe.

Inversion

À opposer à l'opérateur d'adjacence, qui enregistre les connexions binaires sans pondérer les différences ; le spectre de l'adjacence met en valeur les motifs de connexions directes plutôt que les modes lisses.

Limite

Le laplacien combinatoire standard est défini pour des graphes finis non orientés avec poids non négatifs ; les graphes orientés, les poids signés ou les graphes infinis exigent des définitions modifiées (laplacien normalisé, laplacien de marche aléatoire, ou opérateurs sur ℓ^2).

Tension sémantique

Tension avec des notions comme la courbure discrète ou les opérateurs basés sur la résistance : le laplacien mesure la différence locale et la diffusion, tandis que la distance de résistance met l'accent sur la résistance effective globale et peut donner des signaux spectraux différents.

Synthèse

Le laplacien de graphe L = D−A est l'opérateur discret des secondes différences sur les fonctions de sommets ; son action encode l'écart local à la moyenne des voisins et son spectre organise la connectivité, la diffusion et la régularité sur le graphe.