Ein linearer Operator auf Funktionen, die auf den Knoten eines Graphen definiert sind, typischerweise gegeben durch L = D − A, wobei D die diagonale Grade-Matrix und A die Adjazenzmatrix ist; er kodiert diskrete Diffusion und lokale Glätte auf dem Graphen.

Prinzip

Wendet man den Laplace-Operator auf eine Knotenfunktion an, berechnet er den Nettoabfluss (Differenz zwischen dem Wert an einem Knoten und dem Durchschnitt seiner Nachbarn); seine spektrale Zerlegung ordnet Variationsmoden, Konnektivität und Diffusionsraten.

Demonstration

Für einen ungerichteten gewichteten Graphen gilt (Lf)(i)=∑_j w_{ij}(f(i)−f(j)); die Vielfachheit des Eigenwerts Null entspricht der Anzahl zusammenhängender Komponenten, und der zweitkleinste Eigenwert (algebraische Konnektivität) quantifiziert Engpässe.

Fehlanwendung

Den unnormierten Laplacian zu verwenden, ohne Gradheterogenität zu berücksichtigen, wenn man Graphen mit stark variierenden Knotengraden vergleicht; das kann das spektrale Clustering und die Diffusionsinterpretation verfälschen.

Konsequenz

Eigenwerte und Eigenvektoren des Laplacians liefern Informationen über Konnektivität, Mischzeiten von Zufallswegen und können für Dimensionsreduktion, Glättung und Graphpartitionierung genutzt werden.

Umkehrung

Im Gegensatz zur Adjazenzmatrix, die paarweise Verbindungen ohne Gewichtung von Differenzen abbildet; das Adjazenzspektrum betont direkte Verbindungsmuster statt glatter Modi.

Abgrenzung

Der Standard-kombinatorische Laplacian ist für endliche, ungerichtete Graphen mit nichtnegativen Gewichten definiert; gerichtete Graphen, signierte Gewichte oder unendliche Graphen erfordern modifizierte Definitionen (normalisierter Laplacian, Random-Walk-Laplacian oder Operatoren auf ℓ^2-Räumen).

Semantische Spannung

Spannung zu diskreter Krümmung oder widerstandsbasierenden Operatoren: Der Laplacian misst lokale Differenz und Diffusion, während Widerstandsabstände globale effektive Widerstände betonen und andere spektrale Signale liefern können.

Synthese

Das Graph-Laplacian L = D−A ist der diskrete Zweit-Differenzenoperator für Knotenfunktionen; seine Wirkung kodiert lokale Abweichung vom Nachbarschafts-Mittelwert und sein Spektrum strukturiert Konnektivität, Diffusion und Glätte im Graphen.