Algorithme en streaming pour compter les triangles dans un graphique

Question

Comme décrit dans la référence, l'algorithme (voir en bas) suppose de sortir un estimateur $ \ chapeau t $ pour le nombre de triangles dans un graphique donné $ g= (v, e) $ , noté $ t $ . Il est écrit que "on peut facilement montrer" que $$ E [\ chapeau t]= t $$ Mais malheureusement, je ne le vois pas. Essayer d'analyser e $ E [\ chapeau t] $ , je pense comme suit:

• à la ligne 1, désigne la probabilité de choisir de manière aléatoire (et uniformément) choisir un bord qui fait partie d'un triangle comme $ p $ . Puisque les triangles peuvent partager des bords, $$ \ frac t m \ le p \ le \ frac {3t} m $$ Par exemple, considérons le cas suivant:

  

  Le triangle central n'ajoute pas de nouvelles bords au nombre de possibilités de choisir un bord qui fait partie d'un triangle. Vous pouvez imaginer une configuration différente dans laquelle il n'y a que les 3 triangles extérieurs et ils ne se touchent pas (dans cette configuration, nous ne verrons pas le 4ème triangle central). Dans les deux cas ((cas i) 4 triangles comme on le voit dans l'image; (cas II) 3 triangles disjoints), la probabilité de choisir un bord qui fait partie d'un triangle est de 1 (bien que le nombre de triangles soit différent). < / p>

• à la ligne 2, la probabilité de choisir uniformément à un sommet aléatoire à un sommet aléatoire qui "ferme un triangle" avec le bord de l'étape précédente est exactement $ \ frac 1 {n -2} $ .

donc je ne vois que ça

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

Qu'est-ce que je manque?

---

Une autre question que j'ai concerne la ligne 3. Le flux est commandé et nous choisissons d'abord un bord aléatoire $ (u, v) $ (ligne 1), Puis un sommet aléatoire $ w $ de $ v \ backslash \ {u, v \} $ (ligne 2). Je pense que l'analyse doit prendre en compte celle de la ligne 3, nous vérifions si $ (u, w) $ et $ ( v, w) $ apparaît après $ (u, v) $ dans le flux. Peut-être que après que je comprendrai la réponse à ma première question, ce sera plus clair.

---

algorithme:

1. Choisissez une bordure $ (u, v) $ uniformément au hasard du flux.
2. Choisissez un sommet $ w $ uniformément au hasard à partir de $ v \ backslash \ {u, v \} $ < / span>
3. si $ (u, w) $ et $ (v, w) $ apparaît après < SPAN CLASSE="MATH-CONTENEUR"> $ (U, V) $ Dans le flux, alors sortie M (N-2) $ . Sinon, sortie $ 0 $ .

Aussi, bien que je ne l'ai pas vu écrit, je pense qu'il y a une hypothèse que $ v $ est connu à l'avance.

---

Référence: Streams de données Notes de cours par professeur AMIT CHAKRABARTI, section "15.3 comptage triangle", https://www.cs.dartmouth.edu/~ac/teach/data-streams-lecnotes.pdf

---

meilleures salutations

Answer 1

let $ (u, v, w) $ soit un triangle particulier dans le flux, et supposons que le bord $ (u, v) $ apparaît en premier. La probabilité que nous ayons choisi $ (u, v) $ dans la première étape est 1 $ / m $ . La probabilité que nous ayons choisi $ w $ dans la deuxième étape est 1 $ / (n-2) $ . D'où la probabilité que nous avons choisi le triangle $ (u, v, w) $ est 1 $ / [m (n-2 )] $ . Notons cet événement par $ e_ {u, v, w} $ .

si $ (u_1, v_1, w_1) $ et $ (u_2, v_2, w_2) $ sont deux triangles différents que les événements $ e_ {u_1, v_1, w_1} $ et $ e_ {u_2, v_2, w_2} $ est disjoint (notez que les triangles ne doivent pas être disjoints). Par conséquent, s'il y a $ t $ triangles, alors la probabilité que nous ayons choisi l'une d'elles est exactement $ t / [m ( n-2)] $ . Par conséquent, la sortie attendue de l'algorithme est exactement $ t $ .