Speaker:Seyyedeh Kiana Mousavi Hanjani

Title: Improved Triangle Counting in Graph Streams: Power of Multi-Sampling

Abstract: Some of the well known streaming algorithms to estimate number of triangles in a graph stream work as follows: Sample a single triangle with high enough probability and repeat this basic step to obtain a global triangle count. For example, the algorithm due to Buriolet  al. uniformly at random picks a single vertex v and a single edge e and checks whether the two cross edges that connect v to e appear in the stream. Similarly the neighborhood sampling algorithm attempts to sample a triangle by randomly choosing a single vertex v, a single neighbor u of v and waits for a third edge that completes the triangle. In both the algorithms, the basic sampling step is repeated multiple times to obtain an estimate for the global triangle count in the input graph stream.In this work, we propose a multi-sampling variant of these algorithms: In case of Buriolet  al’s algorithm, instead of randomly choosing a single vertex and edge, randomly sample multiple vertices and multiple edges and collect cross edges that connect sampled vertices to the sampled edges. In case of neighborhood sampling algorithm, randomly pick multiple edges and pick multiple neighbors of them. We provide a theoretical analysis of these algorithms and prove that these new algorithms improve upon the known space and accuracy bounds. We experimentally show that these algorithms outperform several well known triangle counting streaming algorithms.