Dreiecke in einem Diagramm finden: andere Ansätze neben dem Testen von Eigenschaften?

Wir arbeiten an einem Artikel, in dem einige Algorithmen zum Auffinden von Dreiecken und Netzwerkmotiven (Untergraphen konstanter Größe, auch als Graphlets bezeichnet) in einer verteilten Umgebung vorgestellt werden. Wir charakterisieren den Kompromiss zwischen der Anzahl der Dreiecke im Diagramm und der erforderlichen Kommunikationslast. Ich suche nach Hinweisen auf Arbeiten zu dieser Frage im zentralisierten Modell.

Das Problem ist, dass fast alles, was ich zu diesem Thema gefunden habe, das einen theoretischen Charakter hatte, im Rahmen von Eigenschaftstests war . Um den Unterschied zu veranschaulichen, betrachten Sie den Fall eines Graphen mit Eckpunkten, der aus Dreiecken besteht, die sich alle die Kante teilen . Unter dem Gesichtspunkt der Eigenschaftsprüfung ist dieses Diagramm nahezu dreieckfrei (das Entfernen dieser kritischen Kante erledigt den Job), während es eine lineare Anzahl von Dreiecken aufweist, was nach unseren Maßstäben sehr viel ist. $n$ $n-2$ $\left(1,2\right)$

Alle Referenzen werden geschätzt.

Bearbeiten: Ich interessiere mich hauptsächlich für Algorithmen, mit denen schnell festgestellt werden kann, ob das Diagramm Dreiecke enthält. Bei Algorithmen zur Auflistung von Dreiecken (oder anderen Untergraphen) wird die Laufzeit natürlich von unten durch die Anzahl der Dreiecke im Diagramm begrenzt, da der Algorithmus sie alle auflisten muss, was solche Instanzen in gewissem Sinne schwieriger macht. Unter dem Gesichtspunkt eines Entscheidungsproblems ("dreieckfrei oder nicht") erleichtert das Vorhandensein vieler Dreiecke das Problem tatsächlich, da Sie leicht eines finden können.

reference-request graph-theory graph-algorithms Shir
quelle

Angesichts Davids Antwort bin ich mir nicht sicher, ob ich mehr verstehe, was Sie wollen. Sie mögen das Eigenschaftstest-Framework nicht, möchten aber die Komplexität der Abfrage einschränken? Ist das Beispiel, das Sie in der Frage geben, ein schlechter Fall, weil Sie auch die Anzahl der Dreiecke schätzen möchten ?

Suresh Venkat

Folgendes möchte ich - einen probabilistischen Algorithmus, der den Graphen abfragt und in der Lage ist, zwischen Graphen mit vielen Dreiecken und Graphen mit keinem zu unterscheiden. Siehe zum Beispiel dl.acm.org/citation.cfm?id=1873611 von Gonen, Ron und Shavit. In ihrem Artikel ist die Abfrage jedoch eingeschränkt (wenn ich das richtig verstehe, sind Kantenabfragen nicht zulässig, es sei denn, sie wurden aus einer gleichmäßigen Verteilung entnommen).

Shir

Sie möchten also einen sublinearen Algorithmus, der die Anzahl der Dreiecke schätzt?

Suresh Venkat

Einige einfache Beobachtungen: Angenommen, Sie haben T-Dreiecke und dürfen randomisieren. Dann können Sie Folgendes abtasten: (1) eine Kante und Sie treffen ein Dreieck mit einer Wahrscheinlichkeit von mindestens ~ T ^ {2/3} / m, da die minimale Anzahl von Kanten, die Sie in einem Diagramm mit T Dreiecken haben können, ~ T ^ ist {2/3}; Sobald Sie eine Kante haben, können Sie in n Schritten überprüfen, ob sie sich in einem Dreieck befindet, sodass Sie einen Algorithmus mit der erwarteten Laufzeit erhalten ~ mn / T ^ {2/3}; (2) Sie können ein zufälliges Dreifach von Eckpunkten auswählen und mit der Wahrscheinlichkeit T / n ^ 3 wird es ein Dreieck sein, so dass Sie eine Laufzeit von ~ n ^ 3 / T erhalten. Sie können auch einige etwas anspruchsvollere Dinge tun. Hilft das?

Virgi

Oh, und außerdem kann jeder Algorithmus, der erkennen kann, ob ein gegebener Graph in ~ n ^ {3-eps} Zeit ein Dreieck enthält, in einen Algorithmus umgewandelt werden, der nxn Boolesche Matrizen in ~ n ^ {3-eps / 3} Zeit multiplizieren kann Aus diesem Grund sind auch nette einfache Dreieckserkennungsalgorithmen von Interesse, obwohl es natürlich schwierig ist, zwischen den Fällen eines 0- oder 1-Dreiecks zu unterscheiden, und für diesen Fall wissen wir nichts besseres als das Rechnen der Würfel der Adjazenzmatrix.

Virgi

Antworten:

Mehrere Referenzen zum Problem des Testens auf das Vorhandensein eines Dreiecks (genau, nicht im Framework für Eigenschaftstests) finden Sie in der dreieckfreien Grafik auf Wikipedia. Insbesondere Alon, Yuster und Zwick (ESA'94) geben einen O (m ^ {1.41}) -Algorithmus an, und dies kann auch in einer schnellen Matrixmultiplikationszeit durchgeführt werden, was für dichte Graphen besser ist.

Wenn Sie mit etwas in der Einstellung für dynamische Diagrammalgorithmen einverstanden sind, habe ich auch eine zum Zählen der Dreiecke:

Der h-Index eines Graphen und seine Anwendung auf dynamische Subgraphenstatistiken, D. Eppstein und ES Spiro, arXiv: 0904.3741 und WADS 2009.

In unserer Arbeit zitieren wir Chiba und Nishizeki (SICOMP 1985) sowie Itai und Rodeh (SICOMP 1978) für die grundlegenden statischen Algorithmus-Fakten, die ein Graph mit m Kanten höchstens O (m ^ {3/2}) Dreiecke in der haben kann schlimmsten Fall und dass sie in dieser Zeit aufgelistet werden können.

David Eppstein
quelle

Danke für die schnelle Antwort. Ich sehe jetzt, dass ich in meiner Frage nicht genau wusste, wonach wir suchen. Ich habe die Referenzen natürlich in Wikipedia gesehen, aber sie passen nicht ganz zusammen, da ich nach etwas im Bereich der Komplexität von Abfragen oder der Laufzeit für einen probabilistischen Algorithmus suche. Ich werde die Frage bearbeiten, um dies widerzuspiegeln. Stimmen Sie also für die Antwort ab, aber ich werde sie nicht akzeptieren, da ich immer noch nach einer Antwort suche. :)

Shir

$\Omega(n^2)$ $n$ $O(n^2)$

Wenn Sie wissen möchten, warum, ziehen Sie die folgende Diagrammfamilie in Betracht:

$G_{0}$ $v$ $X$ $Y$ $(n - 1)/2$ $X$ $v$ $Y$ $v$

$i \in X$ $j \in Y$ $G_{ij}$ $G_0$ $ij$

$G_0$ $G_{ij}$ $G_0$ $G_{ij}$ $i$ $j$ $(n - 1)^2/4$

Artem Kaznatcheev
quelle

Komplexität der WRT-Abfrage, siehe auch "Quantenalgorithmen für das Dreiecksproblem", Magniez, Santha und Szegedy, SODA'05 und arXiv: quant-ph / 0310134.

David Eppstein

Ihr Beispiel zeigt nur, dass für den Fall eines einzelnen Dreiecks (ich denke, es lässt sich leicht auf O (1) verallgemeinern) der Kompromiss zwischen der Anzahl der Dreiecke und der Wahrscheinlichkeit, eines zu treffen, oder ein Hinweis auf a nicht charakterisiert wird gute Probenahmestrategie.

Shir

Θ (n^{2})

$\Theta(n^2)$

Ω (n)

$\Omega(n)$

Ω (\sqrt{N})

$\Omega(\sqrt{N})$

n

$n$

1 - 1 / \sqrt{n}

$1-1/\sqrt{n}$

\sqrt{n}

$\sqrt{n}$

Ich verstehe Ihre Frage in Bezug auf Ihr Endziel nicht genau. Sie könnten jedoch die FPT-Version des Dreiecksverpackungsproblems in Betracht ziehen, wenn dies bei Ihrem Problem hilfreich ist. Insbesondere können Sie Edge Disjoint Triangle Packing (EDTP) oder Vertex Disjoint Triangle Packing (VDTP) in Betracht ziehen und die Instanz des Diagramms in Bezug auf die Anzahl der Scheitelpunkte auf O (k) bzw. O (k ^ 2) kernelisieren. Sie können auch die Anzahl der Dreiecke [O (k ^ 3)] kernelisieren. Nach der Kernelisierung wäre es einfacher, die Dreiecke in der Diagramminstanz zu analysieren.

Nikhil
quelle