Local Computation of PageRank Contributions

@inproceedings{andersen2007local, 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.}, author = {Andersen, Reid and Borgs, Christian and Chayes, Jennifer and Hopcraft, John and Mirrokni, Vahab and Teng, Shang-Hua }, booktitle = {Algorithms and Models for the Web-Graph}, citeulike-article-id = {2051137}, comment = {Provides an approximation algorithm for, given a graph G, a vertex v and a parameter \delta, determine a set of vertices contributing a \delta fraction of the PageRank of v.}, doi = {http://dx.doi.org/10.1007/978-3-540-77004-6\_12}, journal = {Algorithms and Models for the Web-Graph}, keywords = {adversarial-ir, ranking, web-graph}, pages = {150--165}, posted-at = {2008-01-29 15:31:43}, priority = {0}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {Local Computation of PageRank Contributions}, url = {http://dx.doi.org/10.1007/978-3-540-77004-6\_12}, volume = {4863}, year = {2007} }

TY - CONF ID - andersen2007local L3 - citeulike-article-id:2051137 TI - Local Computation of PageRank Contributions T2 - Algorithms and Models for the Web-Graph SE - Lecture Notes in Computer Science JF - Algorithms and Models for the Web-Graph VL - 4863 SP - 150 EP - 165 PB - Springer N2 - 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. KW - adversarial-ir KW - ranking KW - web-graph N1 - Provides an approximation algorithm for, given a graph G, a vertex v and a parameter \delta, determine a set of vertices contributing a \delta fraction of the PageRank of v. AU - Andersen, Reid AU - Borgs, Christian AU - Chayes, Jennifer AU - Hopcraft, John AU - Mirrokni, Vahab AU - Teng, Shang-Hua PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-77004-6_12 ER -