## [Graph-Laplacian](/de/node/57785) Definition 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 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 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 Fehlanwendung Die Verwendung des unnormalisierten Laplacians ohne Berücksichtigung starker Gradheterogenität kann Cluster- oder Diffusionsinterpretationen zugunsten hochgradiger Knoten verzerren. ## Konsequenz 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 Umkehrung Eine normalisierte Form skaliert nach Knotengraden, um den Einfluss auszugleichen; dagegen betont die Adjazenzmatrix direkte Verbindungen statt Glattheit. ## Abgrenzung Abgrenzung Vornehmlich für endliche ungerichtete Graphen formuliert; gerichtete Graphen, signierte Kanten und Hyperkanten erfordern alternative Definitionen des Laplacians oder asymmetrische Verallgemeinerungen. ## Semantische Spannung 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 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.