幂迭代与无向图上的随机游走 令A为无向图的邻接矩阵，D为度数的对角矩阵.（注：因为是无向图，所以A是对称的） 记p(w)为时间t在点v的概率，则有 Pt+1(D)= p.() u:uv∈E 可以写出矩阵的形式：p+i=p(D-1A),进而有P:=p(D-1A):p为行向量 转移矩阵P:=D-1A 要研究Pt,只需要研究W=DAD的幂迭代，因为： W=D2 P D Z 对于实数对称矩阵w=VDVr的幂迭代： Wk VDkVT w的特征值是怎么样分布的？与邻接矩阵的谱相 12幂迭代与无向图上的随机游走 令�为无向图的邻接矩阵, � 为度数的对角矩阵. （注：因为是无向图，所以�是对称的） 记 �'(�)为时间�在点�的概率，则有 �'() � = B *:*,∈. �' � ⋅ 1 deg � 可以写出矩阵的形式：�+,- = �+(�.-�) , 进而有�+ = �/ �.-� + ； �'为行向量 转移矩阵 � ≔ �/)� 要研究�+, 只需要研究� = �/! "��/! "的幂迭代, 因为: � = � - 0 � �.- 0 对于实数对称矩阵� = ���#的幂迭代： �0 = ��0�1 = B )2324 �3 0�3�3 1 �的特征值是怎么样分布的？与邻接矩阵的谱相关 12