Fastest mixing Markov chain on graphs with symmetries

Stephen Boyd, Persi Diaconis, Pablo Parrilo, Lin Xiao

Research output: Contribution to journalArticlepeer-review

70 Scopus citations

Abstract

We show how to exploit symmetries of a graph to efficiently compute the fastest mixing Markov chain on the graph (i.e., find the transition probabilities on the edges to minimize the second-largest eigenvalue modulus of the transition probability matrix). Exploiting symmetry can lead to significant reduction in both the number of variables and the size of matrices in the corresponding semidefinite program, and thus enable numerical solution of large-scale instances that are otherwise computationally infeasible. We obtain analytic or semianalytic results for particular classes of graphs, such as edge-transitive and distance-transitive graphs. We describe two general approaches for symmetry exploitation, based on orbit theory and block-diagonalization, respectively, and establish a formal connection between them.

Original languageEnglish
Pages (from-to)792-819
Number of pages28
JournalSIAM Journal on Optimization
Volume20
Issue number2
DOIs
StatePublished - 2009
Externally publishedYes

Keywords

  • Eigenvalue optimization
  • Fast mixing
  • Graph automorphism
  • Group representation
  • Markov chains
  • Semidefinite programming

Fingerprint

Dive into the research topics of 'Fastest mixing Markov chain on graphs with symmetries'. Together they form a unique fingerprint.

Cite this