Barcode eines Diagramms

Mithilfe der persistenten Homologie können wir die (topologische) Form einer Punktwolke mithilfe der folgenden dreistufigen Methode analysieren:

• Konvertieren Sie den eingestellten Punkt in einen einfachen Komplex (und es gibt verschiedene Möglichkeiten, dies zu tun), der durch einen "Rausch" -Parameter parametrisiert wird
• Berechnen Sie die Homologiegruppen dieses Komplexes (erneut durch den Parameter parametrisiert).
• Betrachten Sie die Entwicklung der Gruppen, während sich der Parameter weiterentwickelt.

Die "Lebenszeit" der verschiedenen Gruppen sieht aus wie eine Sammlung von Intervallen, die als "Barcode" der Form bezeichnet wird.

Gibt es eine einfache Erklärung dafür, wie der Barcode aussieht, wenn der einfache Komplex nur ein 1-Skelett (dh ein Diagramm) ist? Mit anderen Worten, nehmen wir an, wir beginnen mit einem Diagramm (anstelle einer Punktmenge) und führen dann die verbleibenden zwei Schritte wie oben aus.

Betti-0 ist ein Intervall für jeden Scheitelpunkt, wobei eines der beteiligten Intervalle jedes Mal verschwindet, wenn eine Kante zwei Komponenten verbindet. Dies ist einer Spur eines Union-Find sehr ähnlich, der in der Grafik ausgeführt wird.

Betti-1 ist ein Intervall für jede wesentliche geschlossene Schleife; entsprechend einer laufenden aktualisierten Basis für den Zyklusraum . Da es sich um ein Diagramm handelt, werden diese immer dann angezeigt, wenn eine Kante hinzugefügt wird, die zwei nicht zusammenhängende Komponenten nicht verbindet und nie wieder verschwindet.

Der Graph ist bereits ein einfacher Komplex, der aus 0 und 1 Vereinfachungen (Knoten und Kanten) besteht. Die Barcodedarstellung ist nur dann sinnvoll, wenn der einfache Komplex Schritt für Schritt so aufgebaut ist, dass der Komplex in Schritt k eine Teilmenge des Komplexes in Schritt k + 1 ist, dh die Eckpunkte und Kanten werden in einer bestimmten Reihenfolge in ihn eingefügt.

Angenommen, die Eckpunkte werden zum "Zeitpunkt" / "Parameterwert" 0 hinzugefügt und alle Kanten werden zum "Zeitpunkt" / "Parameterwert" 1 hinzugefügt: Der betti_0-Barcode ist einfach ein Satz von Linien, die die Anzahl der disjunkten Komponenten von darstellen Der Graph und betti_1 sind einfach eine Reihe von Linien, die jede "grundlegende" Schleife im Graph darstellen (siehe Zyklusraum eines Graphen).

Es gibt verschiedene Möglichkeiten, solche Ordnungsfunktionen in einem Diagramm zu konstruieren, z. B. eine Funktion über den Scheitelpunkten zu berechnen (z. B. den Grad eines Scheitelpunkts) und zu sagen, dass Scheitelpunkte mit niedrigeren Graden vor den Scheitelpunkten mit höherem Grad "geboren" werden. Angenommen, eine Kante wird hinzugefügt, wenn beide Scheitelpunkte vorhanden sind. Jetzt können Sie unter der Gradverteilung eine persistente Homologieansicht des angegebenen Diagramms erstellen. Viele andere solche Funktionen können konstruiert werden, z. B. Pagerank, Laplace usw.

Was oben gesagt wurde, ist richtig, aber ich werde eine interessante Falte hinzufügen, die besser bekannt sein sollte.

Wenn Sie den Diagrammabstand als Persistenzparameter verwenden und dann die Persistenz des Rips-Komplexes berechnen, können Sie auch eine höherdimensionale Homologie finden. Zum Beispiel sehen die Persistenz-Betti-Zahlen für N Punkte, die auf einem Kreis gleich groß sind, folgendermaßen aus:

$$\begin{array}{*{27}{l}} N & b1 & b2 & b3 & b4 & b5 & b6 & b7 & b8 & b9 & b10 & b11 & b12 \\ 3 & & & & & & & & & & & \\ 4 & 1 & & & & & & & & & & \\ 5 & 1 & & & & & & & & & & \\ 6 & 1 & 1 & & & & & & & & & \\ 7 & 1 & & & & & & & & & & \\ 8 & 1 & 0 & 1& & & & & & & & & \\ 9 & 1 & 2 & & & & & & & & & \\ 10 & 1 & 0 & 0 & 1 & & & & & & & \\ 11 & 1 & 0 & 1 & & & & & & & & \\ 12 & 1 & 3 & 0 & 0 & 1 & & & & & & \\ 13 & 1 & 0 & 1 & & & & & & & & \\ 14 & 1 & 0 & 1 & 0 & 0 & 1 & & & & & \\ 15 & 1 & 4 & 0 & 2 & & & & & & & & \\ 16 & 1 & 0 & 1 & 0 & 0 & 0 &1 & & & & \\ 17 & 1 & 0 & 1 & 0 & 1 & & & & & & & \\ 18 & 1 & 5 & 1 & 0 & 0 & 0 & 0 & 1 & & & \\ \end{array}$$

(wobei Persistenz Betti Zahl nur bedeutet, die Anzahl der Balken beliebiger Länge zu zählen, die in jeder Dimension erscheinen)

Der Unterschied zwischen dieser Situation und der gestellten Frage besteht darin, dass ich das Diagramm nicht filtere, sondern auf dem abstrakten metrischen Raum bleibe, der durch die Kantenabstände des Diagramms realisiert wird.