Fastest mixing Markov chain on graphs with symmetries

Details Fastest mixing Markov chain on graphs with symmetries Fastest mixing Markov chain on graphs with symmetries

2007-09-06

arxiv.org/abs/0709.0955v1

SIAM Journal on Optimization, Vol. 20, Issue 2, pp. 792-819 (2009) .

Mathematics

Probability

39 pages, 15 figures

Scientific paper

10.1137/070689413

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, thus enable numerical solution of large-scale instances that are otherwise computationally infeasible. We obtain analytic or semi-analytic 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. We also establish the connection between these two approaches.

Affiliated with

Also associated with

No associations

Rating

Fastest mixing Markov chain on graphs with symmetries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fastest mixing Markov chain on graphs with symmetries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fastest mixing Markov chain on graphs with symmetries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-466564