Algoritmo de transmisión para contar triángulos en un gráfico

Question

Como se describe en la referencia, el algoritmo (ver en la parte inferior) supone para generar un estimador $ \ hat t $ para el # de triángulos en un gráfico determinado $ g= (v, e) $ , denota $ t $ . Está escrito que "se puede mostrar fácilmente" que $$ E [\ hat t]= t $$ Pero desafortunadamente, no lo estoy viendo. Tratando de analizar $ e [\ hat t] $ , creo que lo siguiente:

• En la línea 1, denota la probabilidad de elegir aleatoriamente (y uniformemente) elegir un borde que forma parte de un triángulo como $ P $ . Dado que los triángulos pueden compartir bordes, $$ \ frac t m \ le p \ le \ frac {3t} m $$ Por ejemplo, considere el siguiente caso:

  

  El triángulo central no agrega nuevos bordes al # de posibilidades para elegir un borde que forma parte de un triángulo. Puede imaginar una configuración diferente, en la que solo hay los 3 triángulos exteriores y no se tocan entre sí (en esta configuración, no veremos el 4to triángulo central). En ambos casos ((Caso I) 4 triángulos como se ve en la imagen; (Caso II) 3 triángulos disjoint), la probabilidad de elegir un borde que forma parte de un triángulo es 1 (aunque el número de triángulos es diferente). < / p>

• En la línea 2, la probabilidad de elegir uniformemente al azar un vértice que "cierra un triángulo" con el borde del paso anterior es exactamente $ \ frac 1 {n -2} $ .

Por lo tanto, solo veo que

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

¿Qué estoy perdiendo?

---

Otra pregunta que tengo es con respecto a la línea 3. Se ordena la corriente, y primero recogemos un borde aleatorio $ (u, v) $ (línea 1), Luego, un vértice aleatorio $ w $ de $ v \ backslash \ {u, v \} $ (línea 2). Siento que el análisis debe tener en cuenta que en la Línea 3, verificamos si $ (u, w) $ y $ ( v, w) $ aparece después de $ (u, v) $ en el flujo. Tal vez después de que entienda la respuesta a mi primera pregunta, será más clara.

---

algoritmo:

1. Elija un borde $ (u, v) $ uniformemente al azar desde la corriente.
2. Elija un vértice $ W $ uniformemente al azar de $ v \ backslash \ {u, v \} $ < / span>
3. si $ (u, w) $ y $ (v, w) $ aparecen después de < Span Class="Math-contenedor"> $ (u, v) $ en el flujo, luego salida $ m (n-2) $ . Otra cosa, Salida $ 0 $ .

Además, aunque no lo vi escrito, creo que hay una suposición de que $ v $ se conoce por delante.

---

Referencia: Secuencias de datos Notas de la conferencia por el Prof. Amit Chakrabarti, sección "15.3 Contando triángulo", https://www.cs.dartmouth.edu/~ac/tach/data-streams-lecnotes.pdf

---

mejor saludos

Answer 1

Let $ (u, v, w) $ Sé un triángulo en particular en la corriente, y supongamos que el borde $ (u, v) $ aparece primero. La probabilidad de que elegimos $ (u, v) $ en el primer paso es $ 1 / m $ . La probabilidad de que elegimos $ w $ en el segundo paso es $ 1 / (n-2) $ . De ahí la probabilidad de que elegimos el triángulo $ (u, v, w) $ es $ 1 / [m (n-2 )] $ . Denotemos este evento por $ e_ {u, v, w} $ .

Si $ (u_1, v_1, w_1) $ y $ (u_2, v_2, w_2) $ son dos triángulos diferentes que los eventos $ e_ {u_1, v_1, w_1} $ y $ e_ {u_2, v_2, w_2} $ son disjoint (tenga en cuenta que los triángulos no tienen que ser desagradables). Por lo tanto, si hay $ t $ triángulos, entonces la probabilidad de que elegimos uno de ellos es exactamente $ t / [m ( N-2)] $ . Por lo tanto, la salida esperada del algoritmo es exactamente $ t $ .