2012/02/13 by Borgs, Christian, Brautbar, Michael, Chayes, Jennifer +1 · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Social and Information Networks (cs.SI)
paper · doi:10.48550/arxiv.1202.2771
A fundamental problem arising in many applications in Web science and social network analysis is, given an arbitrary approximation factor c>1, to output a set S of nodes that with high probability contains all nodes of PageRank at least Δ, and no node of PageRank smaller than Δ/c. We call this problem \sc SignificantPageRanks. We develop a nearly optimal, local algorithm for the problem with runtime complexity O(n/Δ) on networks with n nodes. We show that any algorithm for solving this problem must have runtime of Ω(n/Δ), rendering our algorithm optimal up to logarithmic factors. Our algorithm comes with two main technical contributions. The first is a multi-scale sampling scheme for a basic matrix problem that could be of interest on its own. In the abstract matrix problem it is assumed that one can access an unknown \em right-stochastic matrix by querying its rows, where the cost of a query and the accuracy of the answers depend on a precision parameter ε. At a cost propositional to 1/ε, the query will return a list of O(1/ε) entries and their indices that provide an ε-precision approximation of the row. Our task is to find a set that contains all columns whose sum is at least Δ, and omits any column whose sum is less than Δ/c. Our multi-scale sampling scheme solves this problem with cost O(n/Δ), while traditional sampling algorithms would take time Θ((n/Δ)2). Our second main technical contribution is a new local algorithm for approximating personalized PageRank, which is more robust than the earlier ones developed in \citeJehW03,AndersenCL06 and is highly efficient particularly for networks with large in-degrees or out-degrees. Together with our multiscale sampling scheme we are able to optimally solve the \sc SignificantPageRanks problem.