The Computational Complezity of Link Building

摘要：

We study the problem of adding k new links to a directed graph G(V, E) in order to maximize the minimum PageRank value for a given subset of the nodes. We show that this problem is NP-hard if k is part of the input. We present a simple and efficient randomized algorithm for the simple case where the objective is to compute one new link pointing to a given node t producing the maximum increase in the PageRank value for t. The algorithm computes an approximation of the PageRank value for t in GV, E U (v,t)) for all nodes v with a running time corresponding to a small and constant number of PageRank computations.

作者: Martin Olsen

作者单位: Department of Computer Science University of Aarhus Aabogade 34,DK 8200 Aarhus N, Denmark

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 119-129

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）