Ergodic Control and Polyhedral Approaches to PageRank Optimization

Olivier Fercoq, Marianne Akian, Mustapha Bouhtou, Stephane Gaubert

TL;DR

This paper tackles the problem of optimizing a website's PageRank by strategically choosing hyperlinks. The authors develop polynomial-time algorithms for both continuous (link weight tuning) and discrete (link presence/absence) optimization, even with complex design constraints. They show that optimizing PageRank can be as efficient as computing it, and identify conditions for a "master page" strategy.

What Problem Does This Paper Address?

The core problem is how a website owner (the "webmaster") can strategically design the hyperlinks within their site to maximize a desired outcome, such as user engagement or overall site popularity, as measured by PageRank. This is crucial for e-business and search engine optimization. The authors consider two main scenarios:

  1. Continuous Optimization: The webmaster can adjust the "intensity" or weight of each hyperlink (e.g., by changing font size, color, or position). This leads to a continuum of possible transition probabilities for how a "websurfer" navigates the site.
  2. Discrete Optimization: For each page, the webmaster decides which of a set of "facultative" links to include, given some "obligatory" and "forbidden" links.

A key challenge is that the number of possible link configurations can be astronomically large, making brute-force optimization infeasible. Furthermore, websites often have design constraints imposed by developers or business goals, which need to be incorporated. The paper aims to provide efficient, theoretically sound methods to solve these optimization problems, even for large web graphs.

Methods

The paper frames the PageRank optimization problem as a constrained Markov Decision Process (MDP) with an ergodic reward. Here's a breakdown of their approach:

  • Modeling: They represent the websurfer's navigation as a Markov chain with a transition matrix $P$. The webmaster's actions (choosing link intensities or presence) directly influence this matrix. The goal is to maximize a utility function (often linear, representing total income from clicks) subject to constraints on $P$.
  • Polytope Representation: A crucial insight is that the set of admissible transition probability matrices for a single page, even with discrete choices, can be represented by a polytope (a geometric shape defined by linear inequalities). They show these polytopes have a "concise representation," meaning they can be described efficiently.
  • Ergodic Control: The problem is then reformulated as an ergodic control problem. This is a standard framework in MDPs for finding optimal policies in infinite-horizon problems where the average reward is maximized.
  • Polynomial-Time Solvability: By leveraging the concise representation of the polytopes and the theory of well-described Markov decision processes, they prove that the optimization problem can be solved in polynomial time with respect to the input size. This is a significant theoretical result, as it implies that optimizing PageRank is not computationally much harder than computing it.
  • Algorithms: They propose efficient algorithms, including a value iteration scheme for local constraints and a Lagrangian relaxation approach for handling coupling constraints.

Datasets

  • Real Web Graph Fragments: The authors report numerical results on fragments of real web graphs. Specifically, they mention:
  • A 1500-page fragment from their laboratory's web presence.
  • A fragment of the web graph from universities in New Zealand (413,639 nodes and 2,668,244 links).
  • No New Benchmarks Introduced: The paper uses existing web graph data for evaluation.

Key Insights and Ideas

  • PageRank Optimization as MDP: Framing PageRank optimization as a constrained MDP with ergodic reward provides a powerful theoretical framework.
  • Concise Polytope Representation: The key to polynomial-time solvability lies in showing that the action spaces (admissible transition probabilities) can be represented by efficiently described polytopes. This is a novel contribution for this specific problem.
  • "Master Page" Phenomenon: Under certain conditions (e.g., linear rewards, no coupling constraints), there exists an optimal strategy where all controlled pages should link to a single "master page." This suggests a potentially degenerate but effective strategy for maximizing certain objectives.
  • Optimization vs. Computation Efficiency: The paper demonstrates that optimizing PageRank can be achieved with computational complexity comparable to simply computing it, especially when there are no complex coupling constraints.

Key Results

  • Polynomial-Time Solvability: Both continuous and discrete PageRank optimization problems are shown to be solvable in polynomial time when there are no coupling constraints between pages. This extends to the continuous problem even with coupling constraints.
  • Efficient Algorithms: Scalable algorithms are provided, including a fixed-point scheme for local constraints and a Lagrangian relaxation approach for coupling constraints.
  • "Master Page" Identification: Conditions are identified under which an optimal strategy involves directing all links to a single "master page."
  • Numerical Results: Experiments on real web graph fragments show significant improvements in PageRank scores. For example, one experiment showed a 49% increase in the sum of PageRank scores for a controlled set of pages. Another showed a 22.6% increase in PageRank for a specific page.

Limitations and Future Work

  • Discrete Problem with Coupling Constraints: The discrete PageRank optimization problem with general coupling constraints is shown to be NP-complete. While heuristics are proposed, finding exact optimal solutions remains challenging.
  • "Degenerate" Strategies: The "master page" strategy, while optimal for certain objectives, might not always align with the goal of conveying information effectively. The authors acknowledge this and suggest that this work could be useful for detecting link spamming.
  • Future Research: The authors suggest further research into designing web sites with goals beyond just maximizing PageRank, such as fairness or usefulness. They also note that the bounding techniques developed could be adapted for problems with mutual exclusion constraints.

Summary updated

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.
BibTeX
@article{fercoq2013ergodic,
  author = {Olivier Fercoq and Marianne Akian and Mustapha Bouhtou and Stephane Gaubert},
  title = {{Ergodic Control and Polyhedral Approaches to PageRank Optimization}},
  journal = {IEEE Trans. Automatic Control},
  year = {2013},
  url = {https://openreview.net/forum?id=T3vo9H80AU},
}

Loading related content...

Figure