谱图理论(Spectral graph theory) PageRank 谱分析：特征值+特征向量 计算机科学： +相关的线性代数 。 Pagerank 迭代法解线性方程 图论与组合结构： ·纯电阻电路网络 ·连通性(Cheeger7不等式) 稀疏化Sparsification ·图染色 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)
▣顾：Random walk on graphs 给定图G=(V,E) 图上的随机游走： ·从一个给定的顶点出发 接下来，每一步都从当前顶点，移动到一个均匀随机选取的邻居 不断重复 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？（混合时间，mixing time) 4. 从点s出发，多久才会到达点t?(hitting time) 多久才会遍历每个顶点至少一次？（遍历时间，cover time)
回顾：Random walk on graphs 给定图� = (�, �) 图上的随机游走: • 从一个给定的顶点出发 • 接下来，每一步都从当前顶点，移动到一个均匀随机选取的邻居 • 不断重复 这个随机过程的“长期表现”是怎么样的呢？ 1. 重复t步之后，当前顶点是某个顶点u的概率是多少？ 2. 是否存在一个极限的随机分布，随机游走会收敛到它？（稳态） 3. 多久才会收敛？(混合时间，mixing time) 4. 从点s出发，多久才会到达点t? (hitting time) 5. 多久才会遍历每个顶点至少一次？(遍历时间，cover time) 4
回顾 上节课：无向图上的马尔可夫链基本定理 随机游走的混合时间(mixing time)与谱间隔 (spectral gap) 这节课：电路电阻网络 “等效电阻”距离 随机游走的碰撞时间(Hitting time)和遍历时间 (cover time) 5
回顾 上节课: 无向图上的马尔可夫链基本定理 随机游走的混合时间 (mixing time)与谱间隔 (spectral gap) 这节课：电路电阻网络 “等效电阻”距离 随机游走的碰撞时间(Hitting time)和遍历时间 (cover time) 5
电路网络 给定一个无向图，每条边上有一个电阻，电阻值为e 电路网络可以由基尔霍夫定律(Kirchhoff'slaw)和欧姆定律 (Ohm's law): ·基尔霍夫定律：所有进入某节点的电流的总和，等于所 有离开这节点的电流的总和 。 欧姆定律：把节点的电压（电势）记为中：VR,则有 中(W)一(v)=iuvTuv,其中iuw是u到v的方向电流 (特别地，有iuw=-ivu) ·如何计算电路网络？ 6
电路网络 给定一个无向图，每条边上有一个电阻，电阻值为�( 。 电路网络可以由基尔霍夫定律(Kirchhoff’s law)和欧姆定律 (Ohm’s law): • 基尔霍夫定律: 所有进入某节点的电流的总和，等于所 有离开这节点的电流的总和 • 欧姆定律: 把节点的电压（电势）记为�: � → ℝ，则有 � � − � � = �)*�)* ，其中�)*是�到�的方向电流 （特别地，有�)* = −�*)） • 如何计算电路网络？ 6
电路网络的矩阵表示 给定电阻%（或者电导率we=1/me),如果从节点s注入1A的电流，并且从节点t流出，如何求解/模拟电 路网络丙部的电流和电压？ 更一般地，记b为（从电路外部）流入到节点v∈V的方向电流 ·b。>0意味着（从外部)注入电流 b。<0意味着（向外部）流出的电流 ·除了源节点(source)和汇出节点(sink),其它内部节点有b,=0 翻译一下电流和电压需要遵循的定律： 对于每个节点 ·基尔霍夫定律： 内部流出的电流=外部流入的电流 Hv∈V u:vuEE 欧姆定律： (d)-φ(v)=iuvhuv台iuw=wun(p(u)-p(v)） 两相合并可得： b,=∑iu=∑wn((o)-)=degn(o)φ(o)-∑wpm u:vuEE 其中degw()=∑u:vuEE Wuv是节点v的加权的度数。特别地如果wuw=1,有b=L中 7
电路网络的矩阵表示 给定电阻 �! （或者电导率�! = 1/�!） ，如果从节点s注入1A的电流，并且从节点t流出，如何求解/模拟电 路网络内部的电流和电压？ 更一般地，记�"为（从电路外部）流入到节点� ∈ �的方向电流 • �" > 0意味着（从外部）注入电流 • �" < 0意味着（向外部）流出的电流 • 除了源节点(source)和汇出节点(sink)，其它内部节点有�" = 0 翻译一下电流和电压需要遵循的定律： • 基尔霍夫定律: + #:"#∈& �"# = �", ∀� ∈ � • 欧姆定律: � � − � � = �!"�!" ⇔ �#" = �#" � � − � � 两相合并可得： �" = . #:"#∈& �"# = . !:"!∈% �!" � � − � � = deg&(�)� � − . !:"!∈% �!"� � 其中 deg5(�) = ∑#:"#∈& �#"是节点 �的加权的度数。特别地如果�#" = 1，有� = �� 7 对于每个节点 内部流出的电流=外部流入的电流
电路网络的矩阵表示 给定电阻e,(或者电导率we=1/me),如果从节点s注入1A的电流，并 宜灰书点t流出，如何求解模拟电路网络内部的电流和电压？ 求解五=LΦ！ 计算出电压中之后，电流iuw=wuv(φ(u)一(v)可直接由欧姆定律得出 考虑incidence matrix B,有i=WBTΦ 事实上，拉普拉斯矩阵亦可以写成L=∑e We Deba=BWBT b=LΦ=BWBTΦ=Bi,基尔霍夫定律，flow conservation 注解：很多问题与电路网络的联系，正是从这些方程组开始 8
电路网络的矩阵表示 给定电阻 �! （或者电导率�! = 1/�!） ，如果从节点s注入1A的电流，并 且从节点t流出，如何求解/模拟电路网络内部的电流和电压？ 求解� = �� ！ 计算出电压 � 之后，电流�"# = �"# � � − � � 可直接由欧姆定律得出 考虑incidence matrix B，有�⃑ = ��7� 事实上，拉普拉斯矩阵亦可以写成� = ∑8 �8�8�8 7 = ���7 � = �� = ���7� = ��⃑, 基尔霍夫定律, flow conservation 注解：很多问题与电路网络的联系，正是从这些方程组开始 8
Pseudo-inverse of L 注意拉普拉斯矩阵L并不是满秩的，L1=可 所以LΦ=b不一定有唯一的解 回顾：如果图是连通的，则L的第二小特征值严格大于0；因此L的零空间 (nullspace)完全由1张成。 引理：如果存在向量Φ使得LΦ=五，则万1了 证明：假设本=∑：cv其中v1=1 则LΦ=c2几2v2+…+Cnn 因此LΦ11 对于电路网络来说，这也是合理的：外部流入的电流与流出的电流相等 9
Pseudo-inverse of L 注意拉普拉斯矩阵L并不是满秩的， �1 = 0 所以 �� = �不一定有唯一的解 回顾：如果图是连通的，则�的第二小特征值严格大于0；因此�的零空间 (nullspace)完全由 1张成。 引理：如果存在向量� 使得�� = �，则� ⊥ 1 证明：假设� = ∑9 �9�9，其中�: = : ; 1 则�� = �<�<�< + ⋯ + �;�;�; 因此 �� ⊥ 1 对于电路网络来说，这也是合理的：外部流入的电流与流出的电流相等 9
Pseudo-inverse of L 引理：如果1了，则存在向量Φ使得LΦ=五 证明：因为b11, 因此b=∑%-2a11 考虑6=张2凳，可以验证L项=6 因此L:=∑2元W是-个pseudoinverse(伪逆)： 任意向量万11都被映射到一个唯一的Φ使得LΦ=且Φ11 LΦ=b全体解集为{L6+c1:c∈R,Lb的所有“平移” ·特别地，如果固定一个节点的电压/电势(v)=0,有唯一解 10
Pseudo-inverse of L 引理：如果� ⊥ 1，则存在向量� 使得�� = � 证明： 因为� ⊥ 1，因此� = ∑$%& ' �$ �$ 考虑� = ∑./0 1 2( 3( �.，可以验证�� = � 因此�Ɨ ≔ ∑$%& ' * +0 �$�$ ,是一个pseudoinverse(伪逆)： • 任意向量 � ⊥ 1都被映射到一个唯一的�使得 �� = �且 � ⊥ 1 • �� = � 全体解集为 �Ɨ � + �1: � ∈ ℝ , �Ɨ �的所有“平移” • 特别地，如果固定一个节点的电压/电势� � = 0，有唯一解 10
Effective resistance(等效电阻) 节点s和t之间的等效电阻Refr(s,t):=中(s)-中(t),其中 Φ满足L中=b,b对应于从s到t发送1A电流的向量 相当于把整个图看成一个等效的大电阻的时候，对应的等 效的电阻 理：Rer(s,t)=bstLbst,其中向量bst∈Rn满足 bst(s)=1,bst(t)=-1,并且其它位置都为0 11
Effective resistance (等效电阻) 节点�和�之间的等效电阻�566 �,� ≔ � � − �(�)，其中 � 满足�� = �， �对应于从�到�发送1A电流的向量 相当于把整个图看成一个等效的大电阻的时候，对应的等 效的电阻 引理： �-.. �,� = �78 9 �Ɨ �78，其中向量�78 ∈ ℝ1满足 �78 � = 1, �78 � = −1，并且其它位置都为0 11
嫩编 Energy(电势能) εm=∑诏e e∈E 直观上，可以把整个网络看成从s到的一个大电阻 定理.c()=Refr(s,t),其中i是从s到t的单位电流： 证明：es话·6=Xea0-=中TL中， re 其中中满足L中=bst,因此中=Lbst 进而有e()=bstLbst=Ref(s,t) 12
Energy (电势能) Ɛ � ⃗ ≔ = (∈; �( 0 ⋅ �( 直观上，可以把整个网络看成从�到�的一个大电阻 定理. Ɛ � ⃗ = �566 �,� , 其中�是从�到�的单位电流. 证明： ∑(∈; �( 0 ⋅ �( = ∑( 0 = �9��, 其中�满足�� = �78，因此� = �Ɨ �78 进而有Ɛ � ⃗ = �78 9 �Ɨ �78 = �566 �,� 12