回顾与补充 上节课：随机游走(Random walk),Page Rank 。 记X为时间t随机游走所处的状态，则转移矩阵P,/=Pr[Xt+1= jxt=订 记p(i)为时间t在状态的概率，则有pt+i=p:·P 不可约：强连通 ·周期：gcd{t|(P)i>0},周期为1称为非周期性的 对于有限，不可约，非周期的马尔可夫链，有以下事实： 1.存在一个稳态分布元. 2. 随着t→o,p都会收敛到屁，无论从什么样的0开始. 3. 稳态分布是唯一的 4. π()=
回顾与补充 上节课: 随机游走 (Random walk), Page Rank • 记�!为时间�随机游走所处的状态, 则转移矩阵 �!,# = Pr[�$%& = �|�$ = �] • 记�$(�)为时间�在状态�的概率, 则有�$%& = �$ ⋅ � • 不可约: 强连通 • 周期：gcd � �$ !,! > 0}，周期为1称为非周期性的 对于有限，不可约，非周期的马尔可夫链，有以下事实： 1. 存在一个稳态分布�. 2. 随着 � → ∞， �! 都会收敛到�，无论从什么样的�"开始. 3. 稳态分布是唯一的 4. � � = # $! 2
谱图理论(Spectral graph theory) PageRank 谱分析：特征值+特征向量 计算机科学： +相关的线性代数 。 Pagerank ·稀疏化Sparsification 图论与组合结构： 迭代法解线性方程 ·连通性(Cheeger-不等式) 电阻网络 ·图染色 Expander codes(LDPC, 聚类(Clustering) Tanner codes) Mixing of random walks 不可近似性(Dinur''s proof of Expander graphs (efficient the PCP theorem) network,superconcentrators) 去随机化(Derandomization) 3
谱图理论 (Spectral graph theory) 3 谱分析：特征值 + 特征向量 + 相关的线性代数 图论与组合结构: • 连通性 (Cheeger不等式) • 图染色 • 聚类(Clustering) • Mixing of random walks • Expander graphs (efficient network, superconcentrators) 计算机科学: • Pagerank • 稀疏化Sparsification • 迭代法解线性方程 • 电阻网络 • Expander codes (LDPC, Tanner codes) • 不可近似性(Dinur’s proof of the PCP theorem) • 去随机化 (Derandomization)
矩阵的幂 回顾已经多次出现的矩阵的幂 。 对于可以对角化的矩阵A,收敛只需要特征值的幂是收敛的（特别地，谱半径p(A)=1 也有可能是收敛的) x=a1V1+a2v2+…+an)n Akx=afa1vi+afa2v2 +..+afanvn ·但一般来说，可能需要使用：谱半径p(A)<1当且仅当imAk=0 课后练习：考61引的特征值？日广=？ - 注意：随机游走的转移矩阵一定不会是日》对应的只会是2Y] 随机游走：P+1=p·P,转移矩阵P=D-1A,及其相似的对角阵W=DAD克 -这节课：马尔可夫链基本定理在无向图上成立：对于连通的，非二分图，存在唯一 的稳态分布，且会收敛 -3 完整证明可参照Olle Haggstrom的Finite Markov chains and algorithmic applications 5
矩阵的幂 回顾已经多次出现的矩阵的幂 • 对于可以对角化的矩阵�，收敛只需要特征值的幂是收敛的（特别地，谱半径� � = 1 也有可能是收敛的） � = ���� + ���� + ⋯ + ���� ��� = �� ����� + �� ����� + ⋯ + �� ����� • 但一般来说，可能需要使用：谱半径� � < 1当且仅当 lim %→' �% = 0 – 课后练习：考虑 � � � � 的特征值？ � � � � � =? – 注意：随机游走的转移矩阵一定不会是 � � � � ，对应的只会是 �/� �/� � � • 随机游走：�()* = �( ⋅ �，转移矩阵� ≔ �+*�，及其相似的对角阵� = �+" #��+" # – 这节课：马尔可夫链基本定理在无向图上成立：对于连通的，非二分图，存在唯一 的稳态分布，且会收敛 – 完整证明可参照Olle Häggström的Finite Markov chains and algorithmic applications 5
Graph spectrum 考虑图的邻接矩阵，它的代数性质（如特征值与特征向量） 能否与图本身的组合性质（连通性，是否二分图）相对应？ 图的邻接矩阵的例子：完全图A=J-1=11r-1 J的特征值和特征向量是什么？ Ji=ni 6
Graph spectrum 考虑图的邻接矩阵，它的代数性质（如特征值与特征向量） 能否与图本身的组合性质（连通性，是否二分图）相对应？ 图的邻接矩阵的例子：完全图 � = � − � = 1 1( − � � 的特征值和特征向量是什么？ � 1 = � 1 6
Graph spectrum 考虑图的邻接矩阵，它的代数性质（如特征值与特征向量)能否与图本身的组合性质相对应？ 图的邻接矩阵的例子：二分图 。 引理：对于二分图G,如果a是A(G)的一个特征值，且重数为k,那么-也是A(G)的 一个特征值，重数也是k 。 特征值的重数(multiplicity) -代数重数(algebraic multiplicity):特征多项式里面，根的重复次数 -几何重数(geometric multiplicity小：特征值对应的特征空间的维度 一对于可对角化的矩阵（特别地，对于无向图的邻接矩阵，它们是一样的） 7
Graph spectrum 考虑图的邻接矩阵，它的代数性质（如特征值与特征向量）能否与图本身的组合性质相对应？ 图的邻接矩阵的例子：二分图 • 引理：对于二分图�，如果 � 是� � 的一个特征值，且重数为�，那么−�也是� � 的 一个特征值，重数也是� • 特征值的重数(multiplicity) – 代数重数(algebraic multiplicity)：特征多项式里面，根的重复次数 – 几何重数(geometric multiplicity)：特征值对应的特征空间的维度 – 对于可对角化的矩阵（特别地，对于无向图的邻接矩阵，它们是一样的） 7
Graph spectrum 引理：对于二分图G,如果a是A(G)的一个特征值，且重数为k,那么-α也是A(G)的一个特征值，重数也是k U V 证明：把A表示为U[0B1 假设()是A的一个特征向量，对应特征值为a: ()=[g81G)=a) 因此B'x=ay,By=ax。再考虑() A()g81()()-(）=-(） 因此-α也是A的特征值 最后，注意到：α的重数为k一存在k个线性无关的特征向量对应的特征值α 对每一个分别取反后依然是线性无关的，因此-α的重数也为k 8
Graph spectrum 引理：对于二分图�，如果�是� � 的一个特征值，且重数为�，那么−�也是� � 的一个特征值，重数也是� 证明：把�表示为 � � � � 0 � �! 0 假设 " # 是� 的一个特征向量，对应特征值为�： �� �!� = 0 � �! 0 � � = � � � 因此 �!� = ��, �� = ��。再考虑 " $# � � −� = 0 � �! 0 � −� = −�� �!� = −�� �� = −� � −� 因此 −�也是� 的特征值 最后，注意到：�的重数为 � ⇔ 存在 �个线性无关的特征向量对应的特征值� 对每一个分别取反后依然是线性无关的，因此−�的重数也为 � 8
Graph spectrum 事实上，引理的反方向也是对的。 引理：设A(G)的特征值为a1≥a2≥…≥an,如果i,a:=-an-i+1, 那么G一定是二分图 证明：首先证明：对于任意奇数k,∑=0 A的特征值为a1,a2,,an则Ak的特征值为a,a吃，，a,因此对于任意奇数k, trace(a)=∑=0 组合含义：(4*)=长度为k的从到的行走方案的数目 trae(4)=∑a)u=0,又因为a)u≥0，所以(4a=0 即，对于任意奇数k,长度为k的环路不存在。因此，一定是二分图 9
Graph spectrum 事实上，引理的反方向也是对的。 引理：设� � 的特征值为�/ ≥ �0 ≥ ⋯ ≥ �1，如果∀�, �% = −�&$%'(，那么�一定是二分图 证明：首先证明：对于任意奇数�, ∑2 �2 3 = 0 � 的特征值为�(, �), … , �&则 �3 的特征值为�/ 3, �0 3, … , �1 3，因此对于任意奇数k， ����� �3 = : 2 �2 3 = 0 组合含义: �3 2,4 = 长度为k的从�到�的行走方案的数目 ����� �3 = : 2 �3 2,2 = 0，又因为 �3 2,2 ≥ 0，所以 �3 2,2 = 0 即，对于任意奇数k ，长度为k的环路不存在。因此，一定是二分图 9
Largest eigenvalue of adjacency matrix 图的邻接矩阵A的最大特征值cmax≤degmax(G) 证明：设v为对应最大特征值的特征向量，有Av=1v 令y=max:>0,则(Av)j=(1)j a1y=∑Aau≤degmax(G)·y →max≤degmax(G) 10
Largest eigenvalue of adjacency matrix 图的邻接矩阵A的最大特征值�)*+ ≤ deg)*+(�) 证明：设�为对应最大特征值的特征向量，有�� = � 0，则 �� , = �.� , ⇒ �.�, = & - �,,-�- ≤ deg)*+ � ⋅ �, ⇒ �)*+ ≤ deg)*+(�) 10
Laplacian matrix 给定图G,它的拉普拉斯矩阵L(G)定义为L(G)=D(G)-A(G),其 中D(G)是对角线上为度数的矩阵 对于d-正则图，L(G)=dI一A(G),因此正则图的拉普拉斯矩阵和邻接矩 阵的特征空间是一样的。但一般图上并不成立。 可以写出L(G)=∑e∈ELe,其中Le是只有e这一条边的图的拉普拉斯矩阵 另外：xTLx=∑ieE(x-x)2 11
Laplacian matrix 给定图�，它的拉普拉斯矩阵�(�)定义为� � ≔ � � − �(�), 其 中 �(�)是对角线上为度数的矩阵 对于�-正则图， � � = �� − � � ，因此正则图的拉普拉斯矩阵和邻接矩 阵的特征空间是一样的。但一般图上并不成立。 可以写出� � = ∑>∈@ �>，其中�=是只有e这一条边的图的拉普拉斯矩阵 另外：�>� � = ∑?@∈B �? − �@ C 11
Laplacian matrix 给定图G,它的拉普拉斯矩阵L(G)定义为L(G)=D(G)一 A(G),其中D(G)是对角线上为度数的矩阵 性质：了是L(G)的一个特征向量，对应特征值是0 性质：L(G)≥0 12
Laplacian matrix 给定图�，它的拉普拉斯矩阵�(�)定义为� � ≔ � � − �(�), 其中 �(�)是对角线上为度数的矩阵 性质： 1 是�(�)的一个特征向量，对应特征值是0 性质：� � ≽ 0 12