Ergodic Control and Polyhedral approaches to PageRank Optimization

Olivier Fercoq 1, 2 Marianne Akian 1, 2 Mustapha Bouhtou 3 Stéphane Gaubert 1, 2
1 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : We study a general class of PageRank optimization problems which involve 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.
Type de document :
Article dans une revue
IEEE Transactions on Automatic Control, Institute of Electrical and Electronics Engineers, 2013, 58 (1), pp.134--148. 〈10.1109/TAC.2012.2226103〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00782749
Contributeur : Canimogy Cogoulane <>
Soumis le : mercredi 30 janvier 2013 - 15:20:35
Dernière modification le : jeudi 12 avril 2018 - 01:49:23

Lien texte intégral

Identifiants

Collections

Citation

Olivier Fercoq, Marianne Akian, Mustapha Bouhtou, Stéphane Gaubert. Ergodic Control and Polyhedral approaches to PageRank Optimization. IEEE Transactions on Automatic Control, Institute of Electrical and Electronics Engineers, 2013, 58 (1), pp.134--148. 〈10.1109/TAC.2012.2226103〉. 〈hal-00782749〉

Partager

Métriques

Consultations de la notice

313