Hei guys, I need some hints on Counting subgraphs in data streams.
Consider this 3-pass counting triangles algorithm:
1st Pass: count the number of edges |E| in the stream
2nd Pass: sample an edge e=(a,b) uniformly chosen among all edges from the stream. Choose a node v uniformly from V{a,b}
3rd Pass: Test if edges (a,v) and (b,v) are present in the stream. If (a,v) ∈ E and (b,v) ∈ E then output β=1 else output β=0.
Can this 3-pass counting triangles algorithm counts other kinds of subgraphs on three nodes (i.e, subgraphs of type T0, T1 or T2)? what would you change in the algorithm and in its analysis?
Now, considering the following variant of the sampling algorithm for counting triangles:
In pass 2, instead of sampling an edge (a, b) and a node v ≠ a, b, sample three distinct nodes a, b, and c. In pass 3, check for the existence of edges (a, b), (a, c), and (b, c).
My analysis should bring in configurations of type T0 (i.e, independent sets on three nodes) What we need is something like: - The expected value E[B]. - The proof by Chernoff Bounds. - This variant is better or worse than the original 3pass counting triangles algorithm? and Why?