回顾 上节课： ·电路电阻网络 ·“等效电阻”距离 这节课： 。f 随机游走的碰撞时间(Hitting time)和返程时 间(commute time). 0 线性规划LP 2
回顾 上节课: • 电路电阻网络 • “等效电阻”距离 这节课： • 随机游走的碰撞时间(Hitting time)和返程时 间(commute time) • 线性规划 LP 2
回顾：随机游走 1. f碰撞时间(Hitting time):Hu,v=min{t≥1|X1=u and X:=} and huv E[Huv]. 2. 返程时间(Commute time):Cuv=hu,v+hv,u 3.遍历时间(Cover time):covery定义为：从v出发的随机游走访 问每个节点至少一次需要的期望时间；coverg=max coverv 3
回顾：随机游走 1. 碰撞时间 (Hitting time): �!,# ≔ min � ≥ 1 | �$ = � ��� �% = � and ℎ!,# = �[�!,#]. 2. 返程时间 (Commute time): �!,# ≔ ℎ!,# + ℎ#,!. 3. 遍历时间 (Cover time): cover# 定义为：从�出发的随机游走访 问每个节点至少一次需要的期望时间；cover& ≔ max ' cover# 3
Commute time 定理.对任意的节点s和t,Cs,t=2mRer(s,t),其中m=|E(G)儿. 证明： 固定节点t,记hut为从点u节点t的hitting time,满足vu≠t R=1+:=d:-aou=心 102 考虑h*t这一向量，它满足 D-A (To be cont'd..) 4
Commute time 定理. 对任意的节点� 和 �, �(,% = 2��)** �,� , 其中� = � � . 证明：固定节点 � ，记ℎ!,#为从点 �节点 �的hitting time，满足∀� ≠ � ℎ!,% = 1 + 1 �! E #∼! ℎ#,% ⇒ �!ℎ!,% − E #∼! ℎ#,% = �! 考虑ℎ∗,%这一向量，它满足 � − � ℎ!,# ℎ#,# = �! �# − 2� (To be cont’d..) 4
Commute time 定理.对任意的节点s和t,Cst=2mRef(s,t),其中m=|E(G)儿. 证明：固定节点s,记hu.s为从点u节点s的hitting time,满足Vu≠s hg=1+∑：3dh:-∑A:=d 考虑九*S这一向量，它满足 ds -2m D-A du (To be cont'd..) 5
Commute time 定理. 对任意的节点� 和 �, �(,% = 2��)** �,� , 其中� = � � . 证明：固定节点 �，记ℎ!,$为从点 �节点 �的hitting time，满足∀� ≠ � ℎ!,( = 1 + 1 �! E #∼! ℎ#,( ⇒ �!ℎ!,( − E #∼! ℎ#,( = �! 考虑ℎ∗,(这一向量，它满足 � − � ℎ$,$ ℎ!,$ ℎ#,$ = �$ − 2� �! �# (To be cont’d..) 5
Commute time 定理、对任意的节点s和t,Cs,t=2mRef(s,t),其中m= E(G)儿. 证明(cont'd): ds-2m 2m L(h.,t-h.s)= u 0 d:-2m 2m 因此h-九 2m 2=bst。回顾L中=bt,有解，且解空间是一维的 令中= -, 有 2m Refr(S,t)=φ(s)-中(t)= hst-hss hithts hstt hts Cst 2m 2m 2m 2m 6
Commute time 定理. 对任意的节点� 和 �, �!,# = 2��$%% �,� , 其中� = � � . 证明(cont’d)： � ℎ∗,# − ℎ∗,$ = �! �" ⋮ �# − 2� − �! − 2� �" ⋮ �# = 2� 0 ⋮ −2� 因此 & '∗,&('∗,' )* = �!,#。回顾�� = �$#，有解，且解空间是一维的 令� = &∗,#'&∗,$ () ，有 �*++ �,� = � � − � � = ℎ$,# − ℎ$,$ 2� − ℎ#,# − ℎ#,$ 2� = ℎ!,# + ℎ#,! 2� = �$,# 2� 6
Cover time 推论.Cu,v≤2m,对于任意的uw∈E成立. 定理.连通图的遍历时间最多为2m(n一1) 7
Cover time 推论. �/,0 ≤ 2�，对于任意的�� ∈ �成立. 定理. 连通图的遍历时间最多为2�(� − 1). 7
Approximating Cover Time by Resistance Diameter Theorem.Let R(G):=max Reff(u,v)be the resistance diameter. L,0 Then,m·R(G)≤cover(G)≤2e3m·R(G).lnn+n
Approximating Cover Time by Resistance Diameter Theorem. Let � � ≔ max !,# �$%% �, � be the resistance diameter. Then, � ⋅ � � ≤ cover � ≤ 2�&� ⋅ � � ⋅ ln � + �
更多的联系与应用 Spectral Embedding/Partitioning 一课堂上：拉普拉斯矩阵的特征值与图的连通性的关系 一上次作业：使用拉普拉斯矩阵的特征向量画图，elastic spring networks 一更一般地，拉普拉斯矩阵的特征向量包含的信息可用于做图的分解/分割 -Cheeger's inequality and its generalizations ·图的稀疏化(Graph sparsification) 一 等效电阻与均匀随机生成树 一根据等效电阻，对边进行采样 - 更复杂的算法可以做到o(n)条边 ·计算等效电阻：解拉普拉斯方程组 一几乎线性时间里面求解； -作为对比：一般的线性方程组，高斯消元需要O(n3):迭代法则需要条件数比较好： 网络流问题：近似线性时间 开放研究问题：如果对有向图增加或删掉一条边，Pagerank会变化多少？
更多的联系与应用 • Spectral Embedding/Partitioning – 课堂上：拉普拉斯矩阵的特征值 与 图的连通性的关系 – 上次作业：使用拉普拉斯矩阵的特征向量画图, elastic spring networks – 更一般地，拉普拉斯矩阵的特征向量包含的信息可用于做图的分解/分割 – Cheeger’s inequality and its generalizations • 图的稀疏化 (Graph sparsification) – 等效电阻与均匀随机生成树 – 根据等效电阻，对边进行采样 – 更复杂的算法可以做到O(n)条边 • 计算等效电阻: 解拉普拉斯方程组 – 几乎线性时间里面求解; – 作为对比：一般的线性方程组，高斯消元需要 �(�&)；迭代法则需要条件数比较好； • 网络流问题：近似线性时间 • …… 开放研究问题：如果对有向图增加或删掉一条边，Pagerank会变化多少？
Optimization 给定连续可导f:R”→R,最小化f 例子： 最小二乘法：f(x)=‖Ax-b陉 向量投影：fo)=lca- 求伪逆(Pseudoinverse):f(x)=‖lxll陉，subject to Ax=b 对称矩阵的特征值：f(x)=xTAx,subject toxx=1 线性规划：f(x)=cx,subject to Ax≥b 主成分分析(Principal component analysis):f(C)=‖X-CCTX,subject to C CT laxd 离散组合优化：最小生成树，最小割、最大流（网络流），最短路径，最大 匹配；最大独立集、团、支配集，最小覆盖，背包问题，最大割，mx-SAT, 旅行商问题，最长路径（哈密顿路径）… 10
Optimization 给定连续可导�: ℝE → ℝ, 最小化� 例子： 最小二乘法：� � = �� − � � � 向量投影： � � = � � − � � � 求伪逆(Pseudoinverse)： � � = � � �, subject to � � = � 对称矩阵的特征值： � � = ��� �, subject to �F� = 1 线性规划： � � = ���, subject to �� ≥ � 主成分分析 (Principal component analysis)： � � = � − ���� � , subject to � �F = �G×G 离散组合优化：最小生成树，最小割、最大流（网络流），最短路径，最大 匹配；最大独立集、团、支配集，最小覆盖，背包问题，最大割，max-SAT， 旅行商问题，最长路径（哈密顿路径）…… 10
线性规划(Linear Programming) 例子：面包店 面粉 糖 鸡蛋 甜甜圈(Donuts) 2 2 7 蛋糕(Cake) 5 0 12 现有原料 ≤200 ≤300 ≤500 甜甜圈单个的利润=5，蛋糕单个的利润=25 在现有的原料的限制下，如何最大化利润？ 11
线性规划 (Linear Programming) 例子：面包店 甜甜圈单个的利润=5， 蛋糕单个的利润=25 在现有的原料的限制下，如何最大化利润？ 11 面粉 糖 鸡蛋 甜甜圈 (Donuts) 2 2 7 蛋糕 (Cake) 5 9 12 现有原料 ≤ 200 ≤ 300 ≤ 500