生物医学网络科学Biomedical Network Science
同步与协同动力学04 / 16

拉普拉斯谱与代数连通度

阅读
约 3 分钟

从共识动力学、相同振荡器的同步稳定性，到谱聚类与随机游走，图拉普拉斯矩阵都是核心对象。本页集中整理它的定义、性质、典型图的谱与计算方法，供后面几个页面引用。

拉普拉斯矩阵：对无向（可加权）网络，L=D−AL=D-A，D=diag(k1,…,kN)D=\mathrm{diag}(k_1,\dots,k_N) 为度（或强度）矩阵。即 Lii=kiL_{ii}=k_i，Lij=−AijL_{ij}=-A_{ij}（i≠ji\ne j），每行和为零。其特征值记为 0=μ1≤μ2≤⋯≤μN.0=\mu_1\le\mu_2\le\cdots\le\mu_N . μ2\mu_2 称为代数连通度（algebraic connectivity，Fiedler 1973），对应特征向量称为 Fiedler 向量；μN/μ2\mu_N/\mu_2 称为特征值比（eigenratio）。

基本性质

  • 半正定：𝒙⊤L𝒙=∑(i,j)∈Ewij(xi−xj)2≥0\mathbf x^\top L\mathbf x=\sum_{(i,j)\in E}w_{ij}(x_i-x_j)^2\ge0，所以所有 μk≥0\mu_k\ge0；𝟏\mathbf 1 总是 0 特征值的特征向量。
  • 连通分量：0 特征值的重数等于连通分量个数；因此 μ2>0⇔\mu_2>0\iff 网络连通。μ2\mu_2 越接近 0，网络越接近“断成两块”。
  • 迹：∑kμk=trL=∑iki=2m\sum_k\mu_k=\mathrm{tr}\,L=\sum_ik_i=2m（无权网络），所以平均特征值等于平均度。
  • 加边单调：加入一条边后，每个特征值都不减，且新旧谱交错：μk(G)≤μk(G+e)≤μk+1(G)\mu_k(G)\le\mu_k(G+e)\le\mu_{k+1}(G)。注意这只保证“不减”，并不保证 μ2\mu_2 一定增加（见下面的环形图算例）。
  • 常用界（无权网络）：
    • μ2≤NN−1kmin\mu_2\le\dfrac{N}{N-1}k_{\min}（Fiedler 1973）：一个低度节点就能把 μ2\mu_2 压低；
    • μ2≥4N⋅diam(G)\mu_2\ge\dfrac{4}{N\cdot\mathrm{diam}(G)}（Mohar 1991）：直径越大，μ2\mu_2 的下界越低；
    • kmax+1≤μN≤max⁡(i,j)∈E(ki+kj)≤2kmaxk_{\max}+1\le\mu_N\le\max_{(i,j)\in E}(k_i+k_j)\le2k_{\max}（至少有一条边时）：枢纽决定 μN\mu_N。
  • Cheeger 不等式：设 h(G)=min⁡|S|≤N/2|∂S||S|h(G)=\min_{|S|\le N/2}\dfrac{|\partial S|}{|S|} 为“最窄瓶颈”（切掉的边数与较小一侧节点数之比），则 μ2/2≤h(G)≤2kmaxμ2\mu_2/2\le h(G)\le\sqrt{2k_{\max}\mu_2}。μ2\mu_2 小意味着存在一个代价很低的二分——这是 Fiedler 向量可以用来做谱二分（见谱方法与层次聚类）的理论依据。

上面三条界合在一起说明：枢纽抬高 μN\mu_N，低度节点和瓶颈压低 μ2\mu_2，二者都会增大特征值比。这是后面“异质性悖论”的谱学根源。

典型图的拉普拉斯谱

图（NN 个节点） 拉普拉斯特征值 μ2\mu_2 μN/μ2\mu_N/\mu_2
完全图 KNK_N 00，NN（N−1N-1 重） NN 11
星图 SNS_N 00，11（N−2N-2 重），NN 11 NN
环 CNC_N 2−2cos⁡(2πk/N)2-2\cos(2\pi k/N)，k=0,…,N−1k=0,\dots,N-1 2−2cos⁡(2π/N)2-2\cos(2\pi/N) NN 大时约 N2/π2N^2/\pi^2
路径 PNP_N 2−2cos⁡(πk/N)2-2\cos(\pi k/N)，k=0,…,N−1k=0,\dots,N-1 2−2cos⁡(π/N)2-2\cos(\pi/N) NN 大时约 4N2/π24N^2/\pi^2

手算例：3 个节点的路径（也就是 3 节点星图） L=(1−10−12−10−11),L=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}, 特征值为 0,1,30,1,3（迹 =4=2m=4=2m），Fiedler 向量 ∝(1,0,−1)\propto(1,0,-1)：两端取相反符号，中间为 0，自然地把两端分开。特征值比 =3=3；若再连上两端成为三角形 K3K_3，特征值变为 0,3,30,3,3，特征值比降为 1。

环上加捷径：N=10N=10 的环 μ2≈0.382\mu_2\approx0.382，且 μ2\mu_2 是二重特征值（对应 cos\cos 与 sin\sin 两个模式）。加一条对径捷径只能抬高其中一个，μ2\mu_2 不变，而 μN\mu_N 增大，特征值比反而从 10.5 升到 12.7；再加一条与之“错开”的捷径，μ2\mu_2 升到约 0.70，特征值比降到 7.3（本站代码数值结果）。这个小例子说明谱的简并会让“加边改善同步”的直觉失效，优化网络时要直接计算谱。

归一化拉普拉斯

ℒ=I−D−1/2AD−1/2\mathcal L=I-D^{-1/2}AD^{-1/2}，特征值落在 [0,2][0,2]，且 2 是特征值当且仅当某个连通分量是二分图。它与随机游走转移矩阵 P=D−1AP=D^{-1}A 的谱一一对应（λ(P)=1−λ(ℒ)\lambda(P)=1-\lambda(\mathcal L)），适用于按度归一化的耦合 Kki∑jAij(⋅)\frac{K}{k_i}\sum_j A_{ij}(\cdot)，也决定随机游走的混合时间。度非常不均匀时，使用 LL 还是 ℒ\mathcal L 会改变“哪个网络更易同步”的排序，报告结果时须说明。

计算

  • 稠密特征分解（numpy.linalg.eigvalsh）复杂度 O(N3)O(N^3)，NN 在数千以内可用；
  • 大型稀疏网络只需要两端的少数特征值：用 Lanczos/LOBPCG 类迭代方法（scipy.sparse.linalg.eigsh、networkx.algebraic_connectivity、networkx.fiedler_vector），每次迭代成本 O(m)O(m)；求 μ2\mu_2 时要排除平凡的 𝟏\mathbf 1 方向，迭代收敛速度取决于 μ2\mu_2 与 μ3\mu_3 的间隔，简并时（如上面的环）收敛慢；
  • 有向网络的 LL 一般不对称，特征值可为复数，需要用一般特征值算法，并在主稳定函数中使用复平面上的稳定区。

继续阅读