【24h】

Local Computation of PageRank Contributions

机译:PageRank贡献的本地计算

获取原文
获取原文并翻译 | 示例

摘要

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.
机译:出于检测链接垃圾邮件的问题,我们考虑以下图论原语:给定一个网状图G,一个G中的顶点v和一个参数δ∈(0,1),计算出所有有助于v至少是v的PageRank的δ分数。我们称此集合为v的δ贡献集。为此,我们将v的贡献向量定义为向量,其条目测量每个顶点对v的PageRank的贡献。局部算法是一种产生解的算法通过自适应地检查输入图的指定顶点附近的一小部分。我们给出了一种有效的局部算法,该算法通过自适应检查O(1 /ε)顶点来计算给定顶点的贡献向量的ε-逼近。使用该算法,我们为上面定义的图元给出了局部近似算法。具体来说,我们提供一种算法,该算法返回一个包含v的δ贡献集和v的δ/ 2贡献集最多O(1 /δ)个顶点的集合,并且该算法通过检查最多O(1 /δ)顶点。我们还给出了解决以下问题的局部算法:如果存在k个顶点,对v的PageRank有一个ρ分数,请找到一组k个顶点,至少对(PageRank)贡献一个(ρ-ε)分数。在这种情况下,我们证明了我们的算法最多检查O(k /∈)个顶点。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号