Neighborhood Sampling for Estimating Local Properties on a Graph Stream

Date

May 24, 2013

Speaker

Srikanta Tirthapura

Affiliation

Iowa State University

Overview

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.