On the complexity of optimizing PageRank
(2012) ALGOTEL 2012 — Location: La Grande Motte, France (29.May.2012)
Files
onthecomplexityalgotel.pdf
Restricted Access - Adobe PDF
- 62.76 KB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Hollanders, R., Delvenne, J.-C., & Jungers, R. (2012). On the complexity of optimizing PageRank. 14èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications. Published. ALGOTEL 2012, La Grande Motte, France. https://hdl.handle.net/2078.5/252242