A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs (2007)

Purnamrita Sarkar, Andrew W. Moore

Abstract

Recently there has been much interest in
graph-based learning, with applications in
collaborative fltering for recommender net-
works, link prediction for social networks and
fraud detection. These networks can consist
of millions of entities, and so it is very important to develop highly effcient techniques.
We are especially interested in accelerating
random walk approaches to compute some
very interesting proximity measures of these
kinds of graphs. These measures have been
shown to do well empirically (Liben-Nowell
& Kleinberg, 2003; Brand, 2005). We intro-
duce a truncated variation on a well-known
measure, namely commute times arising from
random walks on graphs. We present a very
novel algorithm to compute all interesting
pairs of approximate nearest neighbors in
truncated commute times, without comput-
ing it between all pairs. We show results on
both simulated and real graphs of size up to
100,000 entities, which indicate near-linear
scaling in computation time.

Full text

Download (application/pdf, 217.9 kB)

Approximate BibTeX Entry

@inproceedings{sarkar_moore_uai07,
    Year = {2007},
    Title = {A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs}
}