Matrice dérivée d'un graphe, généralement définie comme la matrice des degrés moins la matrice d'adjacence, qui encode des relations de diffusion et des différences discrètes d'ordre deux sur l'ensemble des nœuds.

Principe

Représenter la diffusion discrète et les formes quadratiques sur les graphes afin que le flux, la régularité et le coût de coupure s'expriment comme des formes bilinéaires des valeurs nodales.

Démonstration

Pour un graphe avec matrice diagonale des degrés D et matrice d'adjacence A, le laplacien combinatoire L = D − A donne pour un vecteur x la forme quadratique x^T L x = somme sur les arêtes (x_i − x_j)^2 / 2, mesurant la variation le long des arêtes.

Mauvaise application

Employer le laplacien non normalisé sans tenir compte d'une hétérogénéité marquée des degrés peut biaiser les évaluations de regroupement ou d'interprétation de diffusion vers les nœuds de grand degré.

Conséquence

Fournit un opérateur linéaire dont la décomposition modale oriente la diffusion, le partitionnement et le lissage sur les graphes ; de nombreux algorithmes exploitent ses modes de basse fréquence pour révéler des communautés.

Inversion

Une forme normalisée rescale par les degrés des nœuds pour égaliser l'influence ; inversement, la matrice d'adjacence met l'accent sur les liens directs plutôt que sur la régularité.

Limite

Formulé principalement pour des graphes finis non orientés ; les graphes orientés, arêtes signées et hyperarêtes exigent d'autres définitions du laplacien ou des généralisations asymétriques.

Tension sémantique

Par rapport à l'adjacence : le laplacien met l'accent sur les différences et les flux entre valeurs nodales voisines, tandis que l'adjacence met l'accent sur la force des connexions directes.

Synthèse

Opérateur matriciel tenant compte des degrés qui convertit la variation des valeurs nodales en un coût quadratique, agissant comme l'analogue discret d'un opérateur différentiel d'ordre deux pour la diffusion et le partitionnement sur graphe.