1,720,977 research outputs found
Local Computation of PageRank: the Ranking Side
No full textImagine 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 -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 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
A Theoretical Study of a Generalized Version of Kleinberg's HITS Algorithm
No full textKleinberg's HITS algorithm (Kleinberg 1999), which was originally developed in a Web context, tries to infer the authoritativeness of a Web page in relation to a specific query using the structure of a subgraph of the Web graph, which is obtained considering this specific query. Recent applications of this algorithm in contexts far removed from that of Web searching (Bacchin, Ferro and Melucci 2002, Ng et al. 2001) inspired us to study the algorithm in the abstract, independently of its particular applications, trying to mathematically illuminate its behaviour. In the present paper we detail this theoretical analysis. The original work starts from the definition of a revised and more general version of the algorithm, which includes the classic one as a particular case. We perform an analysis of the structure of two particular matrices, essential to studying the behaviour of the algorithm, and we prove the convergence of the algorithm in the most general case, finding the analytic expression of the vectors to which it converges. Then we study the symmetry of the algorithm and prove the equivalence between the existence of symmetry and the independence from the order of execution of some basic operations on initial vectors. Finally, we expound some interesting consequences of our theoretical results
Approximating PageRank locally with sublinear query complexity
No full textThe problem of approximating the PageRank score of a node with minimal information about the rest of the graph has attracted considerable attention in the last decade; but its central question, whether it is in general necessary to explore a non-vanishing fraction of the graph, remained open until now (only for specific graphs and/or nodes was a solution known). We present the first algorithm that produces a (1\pm\epsilon)-approximation of the score of any one node in any n-node graph with probability (1-\epsilon) visiting at most O(n^\frac{2}{3}\sqrt[3]{\log(n)})=o(n) nodes. Our result is essentially tight (we prove that visiting \Omega(n^\frac{2}{3}) nodes is in general necessary to solve even an easier "ranking" version of the problem under any "natural" graph exploration model, including all those in the literature) but it can be further improved for some classes of graphs and/or nodes of practical interest - e.g. to O(n^\frac{1}{2} \gamma^\frac{1}{2}) nodes in graphs with maximum outdegree \gamma
The Power of Local Information in PageRank
No full textCan one assess, by visiting only a small portion of a graph,
if a given node has a signicantly higher PageRank score
than another? We show that the answer strongly depends
on the interplay between the required correctness guarantees
(is one willing to accept a small probability of error?) and
the graph exploration model (can one only visit parents and
children of already visited nodes?)
What does it mean to converge in rank?
No full textWe give the first rigourous, formal definition of convergence in rank of an iterative ranking algorithm - an intuitive notion whose formalization is more challenging than it might at first appear. We then compare, in the context of the well known PageRank algorithm, the rate of convergence in rank with the “classic” rate of convergence of the score vector. Even though both might appear to depend essentially on the same factors, subtle differences make it possible for either to be arbitrarily slow even when the other is quite fast. Thus, making predictions on one based on the other can be completely misleading
Score and rank convergence of HITS.
No full textHow 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
HITS can converge slowly, but not too slowly, in score and rank
No full textThis paper 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
Brief announcement: On approximating pageRank locally with sublinear query complexity
No full textCan 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±ε)-approximation of the score of any given node with probability (1−δ), using at most On2/3ln(n)1/3ln(1/δ)2/3ε−2/3= Õ(n2/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 OE4/5d−3/5ln(n)1/5ln(1/δ)3/5ε−6/5= Õ(E4/5) arcs, where E is the total number of arcs in the graph and d is its average degree
Sublinear algorithms for local graph centrality estimation
Get PDFWe 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(m^2/3 Δ^1/3 d^-2/3 , m 4/5 d -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 (m^1/2 Δ^1/2 d^-1/2 , m^2/3 d^-1/3 )) for both query complexity and computational complexity. Moreover, our technique yields a Õ(n^2/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
- …
