Local Computation of PageRank Contributions

被引:23
|
作者
Andersen, Reid [1 ]
Borgs, Christian [2 ]
Chayes, Jennifer [2 ]
Hopcroft, John [3 ]
Mirrokni, Vahab [4 ]
Teng, Shang-Hua [5 ]
机构
[1] Microsoft, One Microsoft Way, Redmond, WA 98052 USA
[2] Microsoft Res New England, Cambridge, MA 02142 USA
[3] Cornell Univ, Comp Sci Dept, Ithaca, NY 14853 USA
[4] NYC, Res Grp, Google Inc, New York, NY USA
[5] Boston Univ, Dept Comp Sci, Boston, MA USA
关键词
D O I
10.1080/15427951.2008.10129302
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 d. (0, 1), compute the set of all vertices that contribute to v at least a delta-fraction of v's PageRank. We call this set the delta-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 is an element of-approximation of the contribution vector for a given vertex by adaptively examining O(1/is an element of) 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 delta-contributing set of v and at most O(1/delta) vertices from the delta/2-contributing set of v, and that does so by examining at most O(1/delta) vertices. We also give a local algorithm for solving the following problem: If there exist k vertices that contribute a rho-fraction to the PageRank of v, find a set of k vertices that contribute at least a (rho-is an element of)-fraction to the PageRank of v. In this case, we prove that our algorithm examines at most O(k/is an element of) vertices.
引用
收藏
页码:23 / 45
页数:23
相关论文
empty
未找到相关数据