A constant-factor approximation algorithm for the link building problem

DOI10.1007/978-3-642-17461-2_7zbMATH Open1310.68034arXiv1204.1369OpenAlexW1588499150MaRDI QIDQ3066446FDOQ3066446

Authors: Martin Olsen, Anastasios Viglas, Ilia Zvedeniouk 

Publication date: 10 January 2011

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

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.

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

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

Mathematics Subject Classification ID

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

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)