Barcode eines Diagramms

8

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.

Suresh Venkat
quelle

Antworten:

9

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.

Mikael Vejdemo-Johansson
quelle
3

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.

Gurjeet
quelle
1

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:

N.b1b2b3b4b5b6b7b8b9b10b11b12341516117181019121010011110112130011310114101001fünfzehn140216101000117101011815100001

(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.

Anthony Bak
quelle
Wenn ich also richtig verstehe, ist der Komplex zum "Zeitpunkt" t der induzierte Graph auf allen Scheitelpunkten höchstens in der Entfernung tvon einem kanonischen Scheitelpunkt?
Suresh Venkat
1
Zum Zeitpunkt t verbinden wir alle Eckpunkte in einem Abstand t voneinander, aber wir bauen auch den Rest des Rips-Komplexes auf. Das heißt, was Sie beschrieben haben, ist der Ein-Komplex des Rips-Komplexes auf Ebene t - wenn ein Dreifach von Eckpunkten verbunden ist, fügen wir automatisch ein Gesicht usw. hinzu. Es ist relativ einfach, den Fall N = 6 mit einem Stift und Papier zu berechnen Bild.
Anthony Bak
@SureshVenkat - Ich habe festgestellt, dass ich Ihren Kommentar falsch verstanden habe. Es gibt keinen kanonischen Scheitelpunkt. Wenn Sie nur an das Ein-Skelett (das Diagramm) denken möchten, sage ich, dass Sie für jeden Scheitelpunkt Kanten zu allen Scheitelpunkten innerhalb des Abstands t (Abstand im ursprünglichen Diagramm) hinzufügen. Sie fügen auch einfachere Dimensionen hinzu, wenn alle Gesichter bereits enthalten sind.
Anthony Bak
@ DavidRicherby - Ich denke, Sie haben meine Antwort falsch verstanden.
Anthony Bak
@AnthonyBak Du hast recht - sorry. Ich würde dennoch eine Umformulierung empfehlen, da sich die Reihenfolge der Antworten ändert, wenn sie Stimmen erhalten. Das bedeutet, dass das, was oben war, als Sie die Antwort geschrieben haben, nicht unbedingt oben ist, wenn jemand kommt, um sie zu lesen.
David Richerby