Streaming Algoritmo per il conteggio dei triangoli in un grafico

Question

Come descritto nel riferimento, l'algoritmo (vedi in basso) suppone per emettere un stimatore $ \ hat t $ per il numero di triangoli in un determinato grafico $ G= (V, E) $ , denotato $ T $ . È scritto che "può essere facilmente mostrato" quello $$ E [\ hat t]= t $$ Ma sfortunatamente, non lo vedo. Cercando di analizzare $ e [\ hat t] $ , penso come segue:

.

• Alla linea 1, denota la probabilità di in modo casuale (e uniformemente) Scegliere un bordo che fa parte di un triangolo come $ p $ . Poiché i triangoli possono condividere i bordi, $$ \ frac t m \ le p \ le \ frac {3t} m $$ Ad esempio, considera il seguente caso:

  

  Il triangolo centrale non aggiunge nuovi bordi al numero delle possibilità di scegliere un bordo che fa parte di un triangolo. Puoi immaginare una configurazione diversa, in cui ci sono solo i 3 triangoli esterni e non si toccano l'un l'altro (in questa configurazione, non vedremo il 4 ° triangolo centrale). In entrambi i casi ((caso I) 4 triangoli come visto nell'immagine; (caso II) 3 triangoli disgiunti), la probabilità di scegliere un bordo che fa parte di un triangolo è 1 (anche se il numero di triangoli è diverso). < / P >.

• Alla linea 2, la probabilità di scegliere in modo uniforme a caso un vertice che "chiude un triangolo" con il bordo dal passaggio precedente è esattamente $ \ frac 1 {n -2} $ .

Perciò lo vedo solo

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

Cosa mi manca?

---

.

Un'altra domanda che ho riguarda la linea 3. Il flusso è stato ordinato e prendiamo per la prima volta un bordo casuale $ (u, v) $ (linea 1), Quindi un vertice casuale $ w $ da $ v \ backslash \ {u, v \ \} $ (linea 2). Sento che l'analisi dovrebbe prendere in considerazione che alla linea 3 controlliamo se $ (u, w) $ e $ ( v, w) $ appaiono dopo $ (u, v) $ nel flusso. Forse dopo aver capito la risposta alla mia prima domanda, sarà più chiaro.

---

.

Algoritmo:

.
1. Scegli un bordo $ (u, v) $ uniformemente a caso dal flusso.
2. Scegli un vertice $ w $ uniformemente a caso da $ v \ backslash \ {u, v \} $
3. se $ (u, w) $ e $ (V, W) $ appaiono dopo < Span Class="Math-Container"> $ (u, v) $ nel flusso, quindi output $ m (n-2) $ . Altrimenti, output $ 0 $ .

Inoltre, anche se non l'ho visto scritto, credo che ci sia un'ipotesi che $ V $ è noto in anticipo.

---

.

Riferimento: DATA STREAMS TRASPORTO NOTE DA PROF. AMIT Chakrabarti, sezione "15.3 Conteggio del triangolo", https://www.cs.dartmouth.edu/~ac/teach/data-streams-lecnotes.pdf

---

.

Cordiali saluti

Answer 1

Let $ (u, v, w) $ essere un triangolo particolare nel flusso e supponiamo che il bordo $ (u, v) $ appare prima. La probabilità che abbiamo scelto $ (u, v) $ nel primo passo è $ 1 / m $ . La probabilità che abbiamo scelto $ W $ nel secondo passo è $ 1 / (n-2) $ . Da qui la probabilità che abbiamo scelto il triangolo $ (u, v, w) $ è $ 1 / [m (n-2 )] $ . Deniamo questo evento di $ e_ {u, v, w} $ .

Se $ (u_1, v_1, w_1) $ e $ (u_2, v_2, w_2) $ sono due triangoli diversi che gli eventi $ e_ {u_1, v_1, w_1} $ e $ e_ {u_2, v_2, w_2} $ sono disgiunti (nota che i triangoli non devono essere disgiunti). Pertanto se ci sono $ T $ triangoli, quindi la probabilità che abbiamo scelto uno di loro è esattamente $ t / [m ( N-2)] $ . Pertanto l'uscita prevista dell'algoritmo è esattamente $ T $ .