A note on the fastest mixing Markov process on edge-transitive graphs
Received date: 2010-12-02
Revised date: 2011-02-28
Online published: 2012-01-15
尚轶伦 . 边传递图上的最快混合马氏过程[J]. 中国科学院大学学报, 2012 , 29(1) : 12 -16 . DOI: 10.7523/j.issn.2095-6134.2012.1.002
We consider a Markov process on a connected graph, where each edge is labeled with the transition rate between the two adjacent vertices. The fastest mixing Markov process (FMMP) problem is the problem of assigning transition rates to the edges so as to maximize the second smallest eigenvalue λ2 of the Laplacian of the weighted graph, which determines the mixing rate of the Markov process. We show that the FMMP problem always attains its optimum in the fixed-point subset of the feasible set under the automorphism group. This result can be used to reduce the number of optimization variables on graphs with symmetries. We analytically find the optimal solutions on edge-transitive graphs.
[1] Sun J, Boyd S, Xiao L, et al. The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem
[J]. SIAM Review, 2006, 48(4): 681-699.
[2] Boyd S, Diaconis P, Xiao L. Fastest mixing Markov chain on a graph
[J]. SIAM Review, 2004, 46(4): 667-689.
[3] Godsil C, Royle G. Algebraic graph theory
[M]. New York: Springer-Verlag, 2001.
[4] Brémaud P. Markov chains: Gibbs fields, monte carlo simulation, and queues
[M]. New York: Springer-Verlag, 1999.
[5] Fiedler M. Absolute algebraic connectivity of trees
[J]. Linear and Multilinear Algebra, 1990, 26(1-2): 85-106.
[6] Fiedler M. Some minimax problems for graphs
[J]. Discrete Math, 1993, 121(1-3): 65-74.
[7] Boyd S, Diaconis P, Parrilo P, et al. Fastest mxing Markov chain on graphs with symmetries
[J]. SIAM J Optim, 2009, 20(2): 792-819.
[8] Boyd S, Diaconis P, Sun J, et al. Fastest mixing Markov chain on a path
[J]. Amer Math Monthly, 2006, 113(1): 70-74.
[9] Roch S. Bounding fastest mixing
[J]. Electronic Communications in Probability, 2005, 10: 282-296.
[10] Xiao L, Boyd S. Fast linear iterations for distributed averaging
[J]. Systems and Control Letters, 2004, 53(1): 65-78.
[11] Xiao L, Boyd S. Optimal scaling of a gradient method for distributed resource allocation
[J]. Journal of Optimization Theory and Applications, 2006, 129(3): 469-488.
[12] de Klerk E, Pasechnik D V, Schrijver A. Reduction of symmetric semidefinite programs using the regular *-representation
[J]. Math Program, 2007, 109(2): 613-624.
/
| 〈 |
|
〉 |
