Sublinear Time Algorithm for PageRank Computations

Details Sublinear Time Algorithm for PageRank Computations Sublinear Time Algorithm for PageRank Computations

2012-02-13

arxiv.org/abs/1202.2771v3

Computer Science

Data Structures and Algorithms

Scientific paper

In a network, identifying all vertices whose PageRank is more than a given threshold value $\Delta$ is a basic problem that has arisen in Web and social network analyses. In this paper, we develop a nearly optimal, sublinear time, randomized algorithm for a close variant of this problem. When given a directed network \graph, a threshold value $\Delta$, and a positive constant $c>3$, with probability $1-o(1)$, our algorithm will return a subset $S\subseteq V$ with the property that $S$ contains all vertices of PageRank at least $\Delta$ and no vertex with PageRank less than $\Delta/c$. The running time of our algorithm is always $\tilde{O}(\frac{n}{\Delta})$. In addition, our algorithm can be efficiently implemented in various network access models including the Jump and Crawl query model recently studied by \cite{brautbar_kearns10}, making it suitable for dealing with large social and information networks. As part of our analysis, we show that any algorithm for solving this problem must have expected time complexity of ${\Omega}(\frac{n}{\Delta})$. Thus, our algorithm is optimal up to logarithmic factors. Our algorithm (for identifying vertices with significant PageRank) applies a multi-scale sampling scheme that uses a fast personalized PageRank estimator as its main subroutine. For that, we develop a new local randomized algorithm for approximating personalized PageRank which is more robust than the earlier ones developed by Jeh and Widom \cite{JehW03} and by Andersen, Chung, and Lang \cite{AndersenCL06}.

Affiliated with

Also associated with

No associations

Rating

Sublinear Time Algorithm for PageRank Computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sublinear Time Algorithm for PageRank Computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sublinear Time Algorithm for PageRank Computations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-682658