Neighborhood Sampling for Estimating Local Properties on a Graph Stream

Speaker  Srikanta Tirthapura

Host  Milan Vojnovic

Affiliation  Iowa State University

Duration  00:28:17

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.
> Neighborhood Sampling for Estimating Local Properties on a Graph Stream