@inproceedings{andersen2007local,
author = {Andersen, Reid and Borgs, Christian and Chayes, Jennifer and Hopcraft, John and Mirrokni, Vahab S. and Teng, Shang-Hua},
title = {Local Computation of PageRank Contributions},
booktitle = {Proceedings of the 5th Workshop on Algorithms and Models for the Web Graph (WAW)},
year = {2007},
month = {January},
abstract = {Motivated by the problem of detecting link-spam, we consider the following graph-theoretic primitive: Given a webgraph G, a vertex v in G, and a parameter δ ∈ (0, 1), compute the set of all vertices that contribute to v at least a δ fraction of v’s PageRank. We call this set the δ-contributing set of v. To this end, we define the contribution vector of v to be the vector whose entries measure the contributions of every vertex to the PageRank of v. 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 v and at most O(1/δ) vertices from the δ/2-contributing set of v, and which 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 v, find a set of k vertices that contribute at least a (ρ − )-fraction to the PageRank of v. In this case, we prove that our algorithm examines at most O(k/) vertices.},
url = {http://approjects.co.za/?big=en-us/research/publication/local-computation-pagerank-contributions/},
pages = {150-165},
edition = {Proceedings of the 5th Workshop on Algorithms and Models for the Web Graph (WAW)},
}