Fast Incremental Proximity Search in Large Graphs (2008)

Purnamrita Sarkar, Andrew W. Moore, Amit Prakash

Abstract

In this paper we investigate two aspects of
ranking problems on large graphs. First,
we augment the deterministic pruning algo-
rithm in Sarkar and Moore (2007) with sam-
pling techniques to compute approximately
correct rankings with high probability un-
der random walk based proximity measures
at query time. Second, we prove some sur-
prising locality properties of these proximity
measures by examining the short term behav-
ior of random walks. The proposed algorithm
can answer queries on the fly without caching
any information about the entire graph. We
present empirical results on a 600,000 node
author-word-citation graph from the Citeseer
domain on a single CPU machine where the
average query processing time is around 4
seconds. We present quanti¯able link pre-
diction tasks. On most of them our tech-
niques outperform Personalized Pagerank, a
well-known diffusion based proximity mea-
sure.

Full text

Download (application/pdf, 248.5 kB)

Approximate BibTeX Entry

@inproceedings{sarkar_moore_prakash08,
    Year = {2008},
    Title = {Fast Incremental Proximity Search in Large Graphs}
}