A constant-factor approximation algorithm for the link building problem

DOI10.1007/978-3-642-17461-2_7MaRDI QIDQ3066446zbMATH OpenOpenAlexFDO

Authors Martin Olsen, Anastasios Viglas, Ilia Zvedeniouk

Publication date 10 January 2011

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.1369

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Internet topics (68M11)

Abstract: In this work we consider the problem of maximizing the PageRank of a given target node in a graph by adding $k$ new links. We consider the case that the new links must point to the given target node (backlinks). Previous work shows that this problem has no fully polynomial time approximation schemes unless $P=NP$. We present a polynomial time algorithm yielding a PageRank value within a constant factor from the optimal. We also consider the naive algorithm where we choose backlinks from nodes with high PageRank values compared to the outdegree and show that the naive algorithm performs much worse on certain graphs compared to the constant factor approximation scheme.

Recommendations

• On the approximability of the link building problem
• Maximizing PageRank with new backlinks
• The Computational Complexity of Link Building
• PageRank optimization by edge selection
• Maximizing PageRank via outlinks

Cited in

(7)

• On the approximability of the link building problem
• Maximizing PageRank via outlinks
• Maximizing PageRank with new backlinks
• Reputation games for undirected graphs
• PageRank optimization by edge selection
• The Computational Complexity of Link Building
• PageRank optimization in polynomial time by stochastic shortest path reformulation

This page was built for publication: A constant-factor approximation algorithm for the link building problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3066446)