谱图理论(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 对于每个节点 内部流出的电流=外部流入的电流