Ergodic Control and Polyhedral Approaches to PageRank Optimization
Ergodic Control and Polyhedral Approaches to PageRank Optimization
复制标题
DOI：
10.1109/tac.2012.2226103
复制
发表时间：
2010-11
影响因子：
6.8
通讯作者：
Olivier Fercoq;M. Akian;M. Bouhtou;S. Gaubert
中科院分区：
文献类型：
--
作者：
Olivier Fercoq;M. Akian;M. Bouhtou;S. Gaubert
我们研究了一类一般的PageRank优化问题，它涉及到为一个受设计约束的网站找到一个最佳的外链策略。我们既考虑一个连续的问题，其中人们可以选择链接的强度，也考虑一个离散的问题，其中在每个页面中都有强制性链接，兼性链接和禁止链接。我们证明了当没有约束耦合不同页面时，连续问题及其离散变体都可以通过具有遍历奖励的约束马尔可夫决策过程建模，其中网站管理员决定浏览者的转移概率。虽然行动的数量是指数的，但我们证明了过渡措施的相关多体具有简洁的表示，由此我们推断出连续问题在多项式时间内可解，并且当没有耦合约束时，离散问题也是如此。我们也提供有效的算法，适用于非常大的网络。然后，我们研究了最优外链策略的定性特征，并确定了在特定的假设下存在一个所有受控页面都应该指向的“主”页面。我们报告了真实网络图片段的数值结果。
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.