کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436670 | 690022 | 2014 | 21 صفحه PDF | دانلود رایگان |
We consider the LINK BUILDING problem, which involves maximizing the PageRank value of a given target vertex in a directed graph by adding k new links that point to the target (backlinks). We present a theorem describing how the topology of the graph affects the choice of potential new backlinks. Based on this theorem we show that no fully polynomial-time approximation scheme (FPTAS) exists for LINK BUILDING unless P=NPP=NP and we also show that LINK BUILDING is W[1]W[1]-hard.Furthermore, we show that this problem is in the class APX by presenting the polynomial time algorithm r-Greedy, which selects new backlinks in a greedy fashion and results in a new PageRank value for the target vertex that is within a constant factor from the best possible. We also consider the naive algorithm π-Naive, where we choose backlinks from vertices with high PageRank values compared to the out-degree and show that this algorithm performs much worse on certain graphs compared to our constant factor approximation. Finally, we provide a lower bound for the approximation ratio of our r-Greedy algorithm.
Journal: Theoretical Computer Science - Volume 518, 23 January 2014, Pages 96–116