Auswirkung verschiedener Graphoperationen auf die algebraische Konnektivität von Graphlaplace?

8

Die algebraische Konnektivität eines Graphen G ist der zweitkleinste Eigenwert der Laplace-Matrix von G. Dieser Eigenwert ist genau dann größer als 0, wenn G ein verbundener Graph ist. Die Größe dieses Werts gibt an, wie gut das Gesamtdiagramm verbunden ist.

Zum Beispiel ändert das " Hinzufügen von Selbstschleifen " nicht die Laplace-Eigenwerte (insbesondere die algebraische Konnektivität) des Graphen. Weil Laplace (G) = DA in Bezug auf das Hinzufügen von Selbstschleifen unveränderlich ist.

Meine Frage ist:

Hat jemand die Auswirkung verschiedener Operationen (wie z. B. Kantenkontraktion) auf das Spektrum von Laplace untersucht? Kennst du gute Referenzen?

Anmerkung: Die genaue Definition der algebraischen Konnektivität hängt von der Art des verwendeten Laplace ab. Für diese Frage bevorzuge ich die Fan-Chung-Definition in SPECTRAL GRAPH THEORY . In diesem Buch hat Fan Chung eine neu skalierte Version des Laplace veröffentlicht, wodurch die Abhängigkeit von der Anzahl der Eckpunkte beseitigt wird.

graph-theory co.combinatorics spectral-graph-theory js
quelle
4
Es wäre hilfreich, wenn Sie Motivation und Hintergrundinformationen liefern. Bitte lesen Sie Wie man eine gute Frage stellt. und die FAQ der Site .
Kaveh
Ich interessiere mich auch für den Fall der Kantenkontraktion. Ich habe zuvor einige Zeit damit verbracht, Referenzen über die Beziehung zwischen Eigenwerten und Nebenoperationen zu finden, ohne Erfolg.
Hsien-Chih Chang 16 之
4
Die Motivation scheint mir ziemlich klar zu sein.
Suresh Venkat
2
Ich bin zweiter Suresh, zu wissen, wie verschiedene Operationen den Laplace beeinflussen, ist an sich interessant und dieses Problem zeigt sich in verschiedenen Kontexten.
Marcin Kotowski

Antworten:

5

Intuitive Operationen, die die Konnektivität bewahren, verringern die Eigenwerte nicht. Das Hinzufügen von Kanten zum Diagramm verringert beispielsweise nicht die Konnektivität.

Wenn H ein Teilgraph eines Graphen G ist, wissen wir im Allgemeinen durch Interlacing, dass der i-te größte Laplace-Eigenwert von H nicht größer ist als der i-größte Laplace-Eigenwert von G. Ein Beweis kann in Satz 3.2 gefunden werden. 1 des Buches " Spectra of Graphs " von Brouwer und Haemers. Beachten Sie, dass die im Buch verwendete Definition von Laplace nicht normalisiert ist. Es hat Knotengrade auf der Diagonale und -1 (oder 0, wenn keine Kante vorhanden ist) in den nicht diagonalen Einträgen.

Hsien-Chih Chang 張顯 之
quelle
Danke Chang. Ihre Antwort ist wirklich nützlich für mich. Wenn wir jedoch die nicht normalisierte Definition von Laplace verwenden, scheinen viele Vergleiche bedeutungslos zu sein. Zum Beispiel haben wir Algebraische Konnektivität (K10) = 10 und Algebraische Konnektivität (K20) = 20. Beide Diagramme sind jedoch vollständig verbundene einfache Diagramme. Wenn wir jedoch den normalisierten Laplace-Wert verwenden, ist NormalizedAlgebraicConnectivity (K10) = NormalizedAlgebraicConnectivity (K20) = 1, und daher scheint der Vergleich der normalisierten Version rationaler und natürlicher zu sein.
js
@ Behnam: Ich stimme dir zu. Nach der Normalisierung können sich jedoch einige der nicht abnehmenden Eigenschaften unterscheiden. (Angenommen, man kann beim Löschen von Kanten für die nicht normalisierten Kanten eine strikte Verringerung des größten Laplace-Wertes sicherstellen, nicht jedoch für die normalisierten.)
Hsien-Chih Chang 16 之
@ Hsien-Chih Chang "Intuitive Operationen, die die Konnektivität bewahren, verringern die Eigenwerte nicht. Wenn Sie beispielsweise dem Diagramm Kanten hinzufügen, wird die Konnektivität nicht verringert." Bist du sicher? Hast du einen Beweis? Ist das Folgende ein Gegenbeispiel? Beginnen Sie mit einem Pfaddiagramm und fügen Sie Kanten hinzu, um das Lollipop-Diagramm zu bilden . Die Deckungszeit wird schlechter; es geht von nach . Was passiert mit den Eigenwerten in diesem Beispiel? Θ ( n 3 )Θ(n2)Θ(n3)
Tyson Williams
@TysonWilliams Du hast sehr recht. Dies ist einer der theoretischen Aspekte, bei denen sich normalisierte und nicht normalisierte Laplace unterscheiden. Durch das Hinzufügen von Kanten steigt die nicht normalisierte algebraische Konnektivität immer an (Fiedler), aber es gibt (nicht einmal sehr knifflige) Beispiele, die zeigen, dass an den falschen Stellen hinzugefügte Kanten die Konnektivität beeinträchtigen können. Dies ist besonders leicht zu erkennen, wenn Sie Kantengewichte berücksichtigen.
Delio M.