Abstract. We study the complexity of local graph-centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, which we apply to PageRank and Heat Kernel, for constructing a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of [Formula: see text] nodes and [Formula: see text] arcs, with probability [Formula: see text] computes a multiplicative [Formula: see text]-approximation of its score by examining only [Formula: see text] nodes/arcs, where [Formula: see text] is the maximum outdegree of the graph and [Formula: see text] and [Formula: see text] factors are omitted for readability. A similar bound holds for computational cost. We also prove a lower bound of [Formula: see text] for both query complexity and computational complexity. Moreover, in the jump-and-crawl graph-access model, our technique yields a [Formula: see text]-queries algorithm; we show that this algorithm is optimal up to a logarithmic factor—in fact, sublogarithmic in the case of PageRank. These are the first algorithms with sublinear worst-case bounds for general directed graphs and any choice of the target node.

Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require \(\tilde {O}(\tau /\pi (v))\) operations to approximate the probability π ( v ) of a state v in a chain with mixing time τ , and even the best available techniques still have complexity \(\tilde {O}(\tau ^{1.5}/\pi (v)^{0.5})\) ; and since these complexities depend inversely on π ( v ), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this “small- π ( v ) barrier”.

We study the complexity of local graph centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, that we apply to the PageRank and Heat Kernel centralities, for building a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of m arcs, with probability (1-δ) computes a multiplicative (1±ε)-approximation of its score by examining only Õ(min(m2/3Δ1/3d-2/3, m4/5d-3/5)) nodes/arcs, where Δ and d are respectively the maximum and average outdegree of the graph (omitting for readability poly(ε-1) and polylog(δ-1) factors). A similar bound holds for computational cost. We also prove a lower bound of Ω(min (m1/2Δ1/2d-1/2, m2/3d-1/3)) for both query complexity and computational complexity. Moreover, our technique yields a Õ(n2/3)-queries algorithm for an n-node graph in the access model of [Brautbar et al., 2010], widely used in social network mining; we show this algorithm is optimal up to a sublogarithmic factor. These are the first algorithms yielding worst-case sublinear bounds for general directed graphs and any choice of the target node.

Can one compute the PageRank score of a single, arbitrary node in a graph, exploring only a vanishing fraction of the graph? We provide a positive answer to this extensively researched open question. We develop the first algorithm that, for any n -node graph, returns a multiplicative $(1\pmε)$-approximation of the score of any given node with probability $(1-δ)$, using at most $O\big(n^2/3 łn(n)^1/3 łn(1/δ)^2/3 ε^-2/3 \big) = \tildeO (n^2/3 )$ queries which return either a node chosen uniformly at random, or the list of neighbours of a given node. Alternatively, we show that the same guarantees can be attained by fetching at most $O\big( E^4/5 d^-3/5 łn(n)^1/5 łn(1/δ)^3/5 ε^-6/5 \big) = \tildeO (E^4/5 )$ arcs, where E is the total number of arcs in the graph and d is its average degree.

This article explores the fundamental question of how many iterations the celebrated HITS algorithm requires on a general graph to converge in score and, perhaps more importantly, in rank (i.e. to “get right” the order of the nodes). We prove upper and almost matching lower bounds. We also extend our results to weighted graphs.

Imagine you are a social network user who wants to search, in a list of potential candidates, for the best candidate for a job on the basis of their PageRank-induced importance ranking. Is it possible to compute this ranking for a low cost, by visiting only small subnetworks around the nodes that represent each candidate? The fundamental problem underpinning this question, i.e. computing locally the PageRank ranking of k nodes in an $n$-node graph, was first raised by Chen et al. (CIKM 2004) and then restated by Bar-Yossef and Mashiach (CIKM 2008). In this paper we formalize and provide the first analysis of the problem, proving that any local algorithm that computes a correct ranking must take into consideration Ω(√(kn)) nodes -- even when ranking the top $k$ nodes of the graph, even if their PageRank scores are "well separated", and even if the algorithm is randomized (and we prove a stronger Ω(n) bound for deterministic algorithms). Experiments carried out on large, publicly available crawls of the web and of a social network show that also in practice the fraction of the graph to be visited to compute the ranking may be considerable, both for algorithms that are always correct and for algorithms that employ (efficient) local score approximations.

How many iterations does the (ever more) popular HITS algorithm require to converge in score and, perhaps more importantly, in rank (i.e. to get the nodes of a graph "in the right order")? After pinning down the elusive notion of convergence in rank we provide the first non-trivial bounds on the convergence of HITS. A "worst case" example, requiring a number of iterations superexponential in the size of the target graph to achieve even "mild" convergence, suggests the need for greater caution in the experimental evaluation of the algorithm - as recent results of poor performance (e.g. vs. SALSA) might be due to insufficient iterations, rather than to an intrinsic deficiency of HITS. An almost matching upper bound shows that, as long as one employs exponential acceleration e.g. through a "squaring trick", a polynomial running time (practical in many application domains) always provides strong convergence guarantees.