## March 6, Winter 2009: Theory Seminar

### 1:00pm in 253 ICS

# Fast Approximation of the Neighborhood Function for Massive Graphs

## Presented by Nate Gertsch, UC Irvine

The neighbourhood, N(h), is the number of the pairs of nodes
that are within distance h. The neighbourhood function provides useful
information for graphs such as the structure of XML documents, OODBs,
Web graphs, telephone (caller-callee) records, citations graphs, to
name a few. It is very expensive to compute the neighbourhood function
exactly on large graphs. Instead, we propose an algorithm using
approximation counting. Our approximation runs with any amount of
available memory, providing excellent scalability to arbitrarily large
graphs. By applying our approximation algorithm on large real and
synthetic graphs, we find that our approximation algorithm is
significantly faster and more accurate than the best prior
approximation scheme. Our approximation runs over 400 times faster
than the exact computation (with less than a 10% error).