Streaming algoritmo para contagem de triângulos em um gráfico

Question

Como descrito na referência, o algoritmo (ver em baixo), supõe-se que a saída de um estimador $\hat T$ para o nº de triângulos em um gráfico dado $G = (V, E)$, denotada $T$.Está escrito que "ele pode ser facilmente mostrado" que $$ E[\hat T] = T $$ Mas, infelizmente, eu não estou vendo ele.Tentando analisar $E[\hat T]$, Eu penso da seguinte forma:

• Na linha 1, indicam a probabilidade aleatoriamente (e uniforme) escolher uma borda que faz parte de um triângulo como $p$.Desde triângulos pode compartilhar bordas, $$ \frac T m \le p \le \frac {3T} m $$ Por exemplo, considere o seguinte caso:

  

  A central triângulo não adiciona novas bordas para o # de possibilidades para escolher uma borda que faz parte de um triângulo.Você pode imaginar uma configuração diferente, em que há apenas a 3 exterior triângulos e eles não se tocam (nesta configuração, não veremos a central de 4 de triângulo).Em ambos os casos ((caso i) 4 triângulos, como visto na imagem;(caso ii) 3 disjuntos triângulos), a probabilidade de escolher uma borda que faz parte de um triângulo é 1 (apesar de o número de triângulos é diferente).

• Na linha 2, a probabilidade de escolher uniformemente aleatoriamente um vértice que "fecha um triângulo" com a borda da etapa anterior é exatamente $\frac 1 {n-2}$.

Portanto, só vejo que

$$ T \le E[\hat T] \le 3T $$

O que eu estou ausente?

---

Outra pergunta que eu tenho é a respeito da linha 3.O fluxo é ordenado, e fizemos a primeira escolha aleatória de borda $(u, v)$ (linha 1) e, em seguida, um vértice aleatório $w$ a partir de $V \barra invertida \{u, v\}$ (linha 2).Eu sinto que a análise deve levar em conta que a linha 3 podemos verificar se $(u, w)$ e $(v, w)$ aparecer depois de $(u, v)$ no fluxo.Talvez depois eu vou entender a resposta para a minha primeira pergunta, ele vai ser mais claro.

---

Algoritmo:

1. Escolha uma borda $(u, v)$ uniformemente ao acaso a partir do fluxo.
2. Escolha um vértice $w$ uniformemente ao acaso a partir de $V \barra invertida \{u, v\}$
3. Se $(u, w)$ e $(v, w)$ aparecer depois $(u, v)$ na sequência, em seguida, saída $m(n-2)$.Outra coisa, saída $0$.

Também, apesar de eu não vê-lo escrito, eu acredito que há uma suposição de que a $V$ é conhecido antecipadamente.

---

Referência:Fluxos de dados anotações de aula do Prof.Amit Chakrabarti, seção "15.3 Triângulo de Contagem" https://www.cs.dartmouth.edu/~ac/Ensinar/dados-sequências-lecnotes.pdf

---

Melhores cumprimentos

Answer 1

Deixe $(u,v,w)$ ser um determinado triângulo no riacho, e acho que a borda $(u,v)$ aparece em primeiro lugar.A probabilidade de que escolhemos $(u,v)$ o primeiro passo é $1/m$.A probabilidade de que escolhemos $w$ na segunda etapa, é $1/(n-2)$.Daí a probabilidade de que escolhemos o triângulo $(u,v,w)$ é $1/[m(n-2)]$.Vamos denotar este evento $E_{u,v,w}$.

Se $(u_1,v_1,w_1)$ e $(u_2,v_2,w_2)$ são dois diferentes triângulos que os eventos $E_{u_1,v_1,w_1}$ e $E_{u_2,v_2,w_2}$ são disjuntos (observe que os triângulos não tem que ser separado).Portanto, se há $T$ triângulos, então a probabilidade de que escolhemos um deles é exatamente $T/[m(n-2)]$.Portanto, o resultado esperado do algoritmo é exatamente $T$.