中国科学院研究生院学报
中國科學院研究生院學報
중국과학원연구생원학보
JOURNAL OF THE GRADUATE SCHOOL OF THE CHINESE ACADEMY OF SCIENCES
2012年
1期
12-16
,共5页
马氏过程%最快混合%边传递图%特征值优化
馬氏過程%最快混閤%邊傳遞圖%特徵值優化
마씨과정%최쾌혼합%변전체도%특정치우화
Markov process: fast mixing%edge-transitive graph%eigenvalue optimization
考虑加权连通图上的简单连续时间马氏过程,每条边上赋权为马氏过程的转移速率,使得马氏过程混合时间最短的赋权问题称之为最快混合马氏过程问题(FMMP).我们证明FMMP在图自同构群的不变点集合中取到最优,并且在边传递图中解析地得到了最优解.
攷慮加權連通圖上的簡單連續時間馬氏過程,每條邊上賦權為馬氏過程的轉移速率,使得馬氏過程混閤時間最短的賦權問題稱之為最快混閤馬氏過程問題(FMMP).我們證明FMMP在圖自同構群的不變點集閤中取到最優,併且在邊傳遞圖中解析地得到瞭最優解.
고필가권련통도상적간단련속시간마씨과정,매조변상부권위마씨과정적전이속솔,사득마씨과정혼합시간최단적부권문제칭지위최쾌혼합마씨과정문제(FMMP).아문증명FMMP재도자동구군적불변점집합중취도최우,병차재변전체도중해석지득도료최우해.
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.
