Speaker Srikanta Tirthapura
Host Milan Vojnovic
Affiliation Iowa State University
Date recorded 24 May 2013
We consider the estimation of local graph properties, which concern subgraphs that lie within the neighborhood of a vertex, such as counting the number of cliques with a certain number of vertices. We present a new algorithm for sampling the edges of the graph, called “neighborhood sampling”, which works in a single pass through the edges of the graph, presented in an arbitrary order. The algorithm is practical and easy to implement.
©2013 Microsoft Corporation. All rights reserved.