转移矩阵的谱分析 记W=AD-1为随机游走的转移矩阵，Z=1+2AD-1为惰性随机游走的转移炬 要研究P:=Wpo,可以先分析w的特征空间 注意：尽管A是对称的，W不一定是对称的 不过W与一个对称矩阵是相似的：DWDi=D(AD-1)D2=DAD左=A 1 1 定理.W与A拥有相同的特征值 注意：w不一定有两两正交的特征向量 7
8
d-regular graphs(d-正则图) 对于d-正则图，有W=A=1-L,记w的特征值为a1≥a2≥…之an，正交正归化的特征向量为，v2,,n 要研究p:=Wpo,可以把po=c1y1+…+cnn展开 那么W'po=c1aD1+c2a吃v2+…+Cna克n W=A=1-L的特征空间： ·12a1,am≥-1 1=a1,对应的特征向量为1 a1>2当且仅当图是连通的 a41=-an当且仅当图是二分图（课后练习） 可见连通性，和非二分图的性质，分别对应于a2<1和an>一1 这意味着，对连通的非二分图，Wpo→c11ast→∞ 如果a2<1-e,并且am>-1+e,则e越大，收敛越快 Fundamental Theorem of Markov chain, for undirected graph! C1V1是什么？ 对于d-正则图，元=豆=为特征值为1对应的特征向量，因此，=1a=。.)=六po)=言 2m n 因此c==元 8
9 Fundamental Theorem of Markov chain, for undirected graph!
Lazy Random Walks 要证明，=（侵1+AD),→品 随着t→oo: 2m 对d-正则图，W=A,z=1+aA 2 2d 若w的特征值为a1≥2≥…≥n 则Z的特征值为1-1≥ 1+2≥…2 2 1+n≥0 2 2 (课后练习) 定理对有限的连通无向图随着t→0，，=(1+A0Po→品，不管从任何p,出发 9
10 定理. 对有限的连通无向图 , 随着 � → ∞ ， � ! = #* � + #* � � ) # ! � 0 → 2⃗ *3 ，不管从任何 � 0出发