Streaming-Algorithmus zum Zählen von Dreiecke in einem Graphen

Question

Wie in der Referenz beschrieben, setzt der Algorithmus (siehe unten) an, um einen Schätzer $ \ Hat T $ für die # der Dreiecke in einem bestimmten Graphen auszugeben $ g= (V, E) $ , gekennzeichnete $ T $ . Es ist geschrieben, dass "das leicht gezeigt werden kann $$ E [\ hat t]= t $$ Aber leider sehe ich es nicht. Ich versuche, $ E [\ Hat T] $ zu analysieren, denke ich wie folgt:

.

• an der Linie 1, bezeichnen die Wahrscheinlichkeit, zufällig (und gleichmäßig) eine Kante auszuwählen, die Teil eines Dreiecks als $ P $ ist. Da Dreiecke Kanten teilen können, $$ \ frac t m \ le p \ le \ frac {3t} m $$ Berücksichtigen Sie beispielsweise den folgenden Fall:

  

  ">
  "

  Das zentrale Dreieck fügt der Anzahl der Möglichkeiten nicht neue Kanten hinzu, um eine Kante zu wählen, die Teil eines Dreiecks ist. Sie können sich eine andere Konfiguration vorstellen, in der sich nur die 3 äußeren Dreiecke befinden und sie nicht berühren (in dieser Konfiguration werden wir das zentrale 4. Dreieck nicht sehen). In beiden Fällen ((Fall I) 4 Dreiecke wie im Bild zu sehen; (Fall II) 3 Disjoint-Dreiecke), die Wahrscheinlichkeit, eine Kante zu wählen, die Teil eines Dreiecks ist, 1 (obwohl die Anzahl der Dreiecke anders ist). < / p>

• an der Linie 2, die Wahrscheinlichkeit, einheitlich an zufälligen einen Scheitelpunkt auszuwählen, der "ein Dreieck schließt" mit der Kante des vorherigen Schritts ist genau $ \ frac 1 {n -2} $ .

deshalb sehe ich nur das

$$ T \ le e [\ hat t] \ le 3t $$

Was vermisse ich?

---

Eine andere Frage, die ich in Bezug auf die Linie 3. Der Stream ist bestellt, und wir wählen zunächst einen Zufallskanten $ (U, V) $ (Zeile 1), Dann ein zufälliger Scheitelpunkt $ W $ aus $ v \ backslash \ {u, v \ \ \ $ (Zeile 2). Ich habe das Gefühl, dass die Analyse berücksichtigen sollte, dass in Zeile 3, ob $ (U, W) $ und $ ( v, w) $ Erscheint nach $ (u, v) $ im bream. Vielleicht verstehe ich die Antwort auf meine erste Frage, es wird klarer sein.

---

Algorithmus:

.
1. Wählen Sie eine Kante $ (u, v) $ gleichmäßig aus dem Bach einheitlich.
2. Wählen Sie einen Scheitelpunkt $ W $ Uniform zufällig von $ v \ backslash \ {u, v \} $ < / span>
3. wenn $ (u, w) $ und $ (v, w) $ nach < Span-Klasse="Math-Container"> $ (u, v) $ im Stream, dann -Ausgut $ M (N-2) $ . Sonst, Ausgang $ 0 $ .

Obwohl ich es nicht geschrieben habe, glaube ich, dass es eine Annahme gibt, dass $ V $ voraus bekannt ist.

---

Referenz: Datenströme Vortragshinweise von Prof. Amit Chakrabarti, Abschnitt "15.3 Dreieckzählen", https://www.cs.dartmouth.edu/~ac/teach/data-streams-decnotes.pdf

---

beste grüße

Answer 1

lass $ (u, v, w) $ ein bestimmtes Dreieck im Bach sein, und nehme an, dass der Rand $ (u, v) $ erscheint zuerst. Die Wahrscheinlichkeit, dass wir $ (u, v) $ im ersten Schritt ausgewählt haben, ist $ 1 / M $ . Die Wahrscheinlichkeit, dass wir $ W $ im zweiten Schritt gewählt haben, ist $ 1 / (N-2) $ . Somit die Wahrscheinlichkeit, dass wir das Dreieck $ (U, V, W) $ ausgewählt haben, ist $ 1 / [M (N-2 )] $ . Lassen Sie uns dieses Ereignis mit $ E_ {U, V, W} $ bezeichnen.

wenn $ (u_1, v_1, w_1) $ und $ (u_2, v_2, w_2) $ sind zwei verschiedene Dreiecke, die die Ereignisse $ e_ {u_1, v_1, w_1} $ und $ e_ {u_2, v_2, W_2} $ sind disjunkt (beachten Sie, dass die Dreiecke nicht disjunkt sein müssen). Wenn also T $ Dreiecke vorhanden sind, dann ist die Wahrscheinlichkeit, dass wir einen von ihnen entschieden haben, genau $ t / [m ( n-2)] $ . Daher ist die erwartete Ausgabe des Algorithmus genau $ t $ .