# Approximating PageRank locally with sublinear query complexity.

Can we approximate the centrality score of a given node by exploring only a vanishing fraction of the graph? In this paper we develop a combination of techniques that we apply to the case of PageRank, where the centrality of a node depends on \emph{every} arc in the graph. We obtain an algorithm that, given any one node in any $n$-node graph, with probability $1-\delta$ returns a multiplicative $(1\pm\epsilon)$ approximation of its PageRank score using at most $O\big(n^{\frac{2}{3}}\sqrt[3]{\log(n/\delta)}\,\ln(1/\delta)^\frac{1}{3}\epsilon^{-\frac{2}{3}}\big) = \tilde{O}(n^{\frac{2}{3}})$ graph exploration queries -- where a query returns either a given node's list of neighbours, or a node chosen uniformly at random. Until now, every algorithm required in general $\Omega(n)$ queries. We also show that this upper bound is essentially optimal by proving an almost matching lower bound. Our techniques can be applied to other centrality measures, even though we leave the analysis of the resulting bounds for future work.

Publisher URL: http://arxiv.org/abs/1404.1864

DOI: arXiv:1404.1864v2

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

Researcher displays publicly available abstracts and doesnâ€™t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.