更多的联系与应用 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会变化多少？