Welcome to Journal of University of Chinese Academy of Sciences,Today is

›› 2012, Vol. 29 ›› Issue (1): 12-16.DOI: 10.7523/j.issn.2095-6134.2012.1.002

• Research Articles • Previous Articles     Next Articles

A note on the fastest mixing Markov process on edge-transitive graphs

SHANG Yi-Lun   

  1. Institute for Cyber Security, University of Texas at San Antonio, Texas 78249, USA
  • Received:2010-12-02 Revised:2011-02-28 Online:2012-01-15

Abstract:

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.

Key words: Markov process, fast mixing, edge-transitive graph, eigenvalue optimization

CLC Number: