2012 • Conference Paper
On the complexity of optimizing PageRank
Authors:
Hollanders, Romain,
Delvenne, Jean-Charles ,
Jungers, Raphaël M.
Published in:
ALGOTEL 2012
We consider the PageRank Optimization problem in which one seeks to maximize (or minimize) the PageRank of a node in a graph through adding or deleting links from a given subset. The problem can be modeled as a Markov Decision Process and has recently received much attention. We provide provably efficient methods to solve the problem on large graphs for a number of cases of practical importance and we show using perturbation analysis that for a close variation of the problem, the same techniques have exponential worst case complexity.