An approximation algorithm for the link building problem

Details An approximation algorithm for the link building problem An approximation algorithm for the link building problem

2012-04-05

arxiv.org/abs/1204.1369v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An approximation algorithm for the link building problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An approximation algorithm for the link building problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An approximation algorithm for the link building problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-182926