Abstract

Network proximity is at the heart of a large class of network analytics and information retrieval techniques, including node/ edge rankings, network alignment, and random-walk based proximity queries, among many others. Owing to its importance, significant effort has been devoted to accelerating iterative processes underlying network proximity computations. These techniques rely on numerical proper-ties of power iterations, as well as structural properties of the networks to reduce the runtime of iterative algorithms.

In this paper, we present an alternate approach to acceleration of network proximity queries using Chebyshev polynomials. We show that our approach, called Chopper, yields asymptotically faster convergence in theory, and significantly reduced convergence times in practice. We also show that other existing acceleration techniques can be used in conjunction with Chopper to further reduce runtime. Using a number of large real-world networks, and top-k proximity queries as the benchmark problem, we show that Chop-per outperforms existing methods for wide ranges of parameter values. Chopper is implemented in Matlab and is freely available at http://compbio.case.edu/chopper/.


Filed under: Graph Mining and Social Networks | Mining Rich Data Types


Comments