Ergodic Control and Polyhedral Approaches to PageRank Optimization

DOI10.1109/TAC.2012.2226103MaRDI QIDQ5353079zbMATH OpenOpenAlexFDO

Authors Olivier Fercoq, Marianne Akian, Mustapha Bouhtou, Stéphane Gaubert

Publication date 8 September 2017

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Internet topics (68M11) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: We study a general class of PageRank optimization problems which consist in finding an optimal outlink strategy for a web site subject to design constraints. We consider both a continuous problem, in which one can choose the intensity of a link, and a discrete one, in which in each page, there are obligatory links, facultative links and forbidden links. We show that the continuous problem, as well as its discrete variant when there are no constraints coupling different pages, can both be modeled by constrained Markov decision processes with ergodic reward, in which the webmaster determines the transition probabilities of websurfers. Although the number of actions turns out to be exponential, we show that an associated polytope of transition measures has a concise representation, from which we deduce that the continuous problem is solvable in polynomial time, and that the same is true for the discrete problem when there are no coupling constraints. We also provide efficient algorithms, adapted to very large networks. Then, we investigate the qualitative features of optimal outlink strategies, and identify in particular assumptions under which there exists a "master" page to which all controlled pages should point. We report numerical results on fragments of the real web graph.

Cited in

(13)

• Hitting times in Markov chains with restart and their application to network centrality
• PageRank computation via a distributed randomized approach with lossy communication
• The greedy strategy for optimizing the Perron eigenvalue
• Perron vector optimization applied to search engines
• PageRank optimization by edge selection
• On the approximability of the link building problem
• Parametric controllability of the personalized PageRank: Classic model vs biplex approach
• Hardness of bounding influence via graph modification
• On the initial value of PageRank
• A note on valid inequalities for PageRank optimization with edge selection constraints
• Enforcing Katz and PageRank centrality measures in complex networks
• Fully personalized PageRank and algebraic methods to distribute a random walker
• A pseudo-gradient approach for model-free Markov chain optimization

This page was built for publication: Ergodic Control and Polyhedral Approaches to PageRank Optimization

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