Local Computation of PageRank Contributions
Reid Andersen, Christian Borgs, Jennifer Chayes, John E. Hopcroft, Vahab Mirrokni, Shang‐Hua Teng · Internet Mathematics · 2008
Motivated by the problem of detecting link-spam, we consider the following graph-theoretic primitive: Given a webgraph _G_, a vertex _υ_ in _G_, and a parameter δ ∈ (0, 1), compute the set of all vertices that contribute to _υ_ at least a δ-fraction of _υ_'s PageRank. We call this set the δ-contributing set of _υ_. To this end, we define the contribution vector of _υ_ to be the vector whose entries measure the contributions of every vertex to the PageRank of _υ_. A local algorithm is one that produces a solution by adaptively examining only a small portion of the input graph near a specified vertex. We give an efficient local algorithm that computes an ε-approximation of the contribution vector for a given vertex by adaptively examining _O_(1/ε) vertices. Using this algorithm, we give a local approximation algorithm for the primitive defined above. Specifically, we give an algorithm that returns a set containing the δ-contributing set of _υ_ and at most _O_(1/δ) vertices from the δ/2-contributing set of _υ_, and that does so by examining at most _O_(1/δ) vertices. We also give a local algorithm for solving the following problem: If there exist _k_ vertices that contribute a _ρ_-fraction to the PageRank of _υ_, find a set of _k_ vertices that contribute at least a (_ρ_−ε)-fraction to the PageRank of _υ_. In this case, we prove that our algorithm examines at most _O_(_k_/ε) vertices.