Eine aus einem Graphen abgeleitete Matrix, üblicherweise als Gradmatrix minus Adjazenzmatrix definiert, die diffusionsähnliche Beziehungen und diskrete zweite Differenzen über die Knotenmenge kodiert.

Prinzip

Diskrete Diffusion und quadratische Formen auf Graphen darstellen, sodass Fluss, Glattheit und Schnittkosten als bilineare Formen von Knotenwerten ausgedrückt werden können.

Demonstration

Für einen Graphen mit Grad-Diagonalmatrix D und Adjazenz A ergibt der kombinatorische Laplacian L = D − A für einen Vektor x die quadratische Form x^T L x = Summe über Kanten (x_i − x_j)^2 / 2, welche die Variation über Kanten misst.

Fehlanwendung

Die Verwendung des unnormalisierten Laplacians ohne Berücksichtigung starker Gradheterogenität kann Cluster- oder Diffusionsinterpretationen zugunsten hochgradiger Knoten verzerren.

Konsequenz

Stellt einen linearen Operator bereit, dessen modale Zerlegung Diffusion, Partitionierung und Glättung auf Graphen leitet; viele Verfahren nutzen seine niederfrequenten Modi zur Erkennung von Gemeinschaftsstrukturen.

Umkehrung

Eine normalisierte Form skaliert nach Knotengraden, um den Einfluss auszugleichen; dagegen betont die Adjazenzmatrix direkte Verbindungen statt Glattheit.

Abgrenzung

Vornehmlich für endliche ungerichtete Graphen formuliert; gerichtete Graphen, signierte Kanten und Hyperkanten erfordern alternative Definitionen des Laplacians oder asymmetrische Verallgemeinerungen.

Semantische Spannung

Im Gegensatz zur Adjazenz: Der Laplacian betont Unterschiede und Flüsse zwischen benachbarten Knotenwerten, während die Adjazenz direkte Verbindungsstärken in den Vordergrund stellt.

Synthese

Ein gradbeachtender Matrixoperator, der Knotenwertvariation in eine quadratische Kostenfunktion überführt und als diskretes Gegenstück zu einem zweiten Differentialoperator für Diffusion und Partitionierung auf Graphen dient.