谱方法与层次聚类

模块度谱方法

把模块度写成矩阵形式。定义模块度矩阵 $B_{ij} = A_{ij} - \dfrac{k_ik_j}{2m}$。若把网络一分为二，用 $s_i = \pm 1$ 表示节点 $i$ 属于哪一侧，则

$$Q = \frac{1}{4m}\, \mathbf{s}^\top B\, \mathbf{s}.$$

在 $s_i$ 只能取 $\pm1$ 的约束下精确最大化很困难；放松为实数后，最优解就是 $B$ 的最大特征值对应的特征向量。按其分量的正负号把节点分为两组，就得到谱二分（Newman，2006）。对每一组可以继续二分，直到 $Q$ 不再增加。特征向量分量的绝对值还给出了一种“归属强度”：$|u_i|$ 接近 0 的节点处于两组之间，归属最不确定。

拉普拉斯谱聚类

另一类谱方法基于图拉普拉斯矩阵 $L = D - A$。最小割问题 $\min \frac14\mathbf s^\top L\mathbf s$ 放松后的解是 $L$ 的第二小特征值（代数连通度）对应的特征向量，即 Fiedler 向量。为避免切下孤立的小块，常改用比率割或归一化割，对应 $D^{-1}L$ 或对称归一化拉普拉斯 $D^{-1/2}LD^{-1/2}$ 的特征向量。分成 $K$ 组时，取前 $K$ 个特征向量作为节点坐标，再用 k 均值聚类，这就是机器学习中常用的谱聚类。它需要预先给定 $K$，可用“特征值间隙”（eigengap）粗略估计。

稀疏网络中的谱方法

在平均度很低的稀疏网络中，邻接矩阵和拉普拉斯矩阵的主特征向量容易局域化在少数高度节点或悬挂树上，不再携带社团信息。Krzakala 等（2013）提出基于非回溯矩阵（non-backtracking matrix，描述“不立即原路返回”的游走）的谱方法；Saade、Krzakala 与 Zdeborová（2014）给出等价但更易计算的 Bethe Hessian $H(r)=(r^2-1)I-rA+D$（$r$ 取平均超额度的平方根，近似为 $\sqrt{\langle k\rangle}$），其负特征值的个数可估计社团数，对应特征向量用于划分。这类方法在稀疏随机块模型上一直有效到理论可检测阈值（见可检测性阈值）。

层次聚类与 Ravasz 算法

层次聚类（hierarchical clustering）先定义节点之间的相似度，再自底向上逐步合并最相似的节点或簇，形成树状图。Ravasz 等（2002）为识别代谢网络中的功能模块提出的算法是一个典型例子：

1. 拓扑重叠相似度： $$x_{ij}=\frac{J(i,j)}{\min(k_i,k_j)+1-\Theta(A_{ij})},$$ 其中 $J(i,j)$ 是 $i,j$ 的共同邻居数，若 $i,j$ 直接相连则 $J$ 再加 1；$\Theta(A_{ij})$ 在 $i,j$ 相连时为 1、否则为 0。$x_{ij}=1$ 表示两点的邻居完全重叠，$x_{ij}=0$ 表示没有共同邻居且不相连。
2. 簇间相似度：合并时如何衡量两个簇之间的相似度有三种常见选择——单连接（取簇间最相似的一对）、全连接（取最不相似的一对）、平均连接（取所有跨簇节点对的平均）。Ravasz 算法采用平均连接。
3. 逐步合并：每次合并相似度最高的两个簇，更新簇间相似度，直到所有节点合为一个簇；得到的树状图可在不同高度切割，或用模块度选择切割高度。

计算量的主要部分是相似度矩阵（$O(n^2)$）与合并过程（朴素实现 $O(n^2\log n)$ 级），适用于数千到数万节点的网络。基因共表达网络分析中的 WGCNA 方法就是“拓扑重叠相似度 + 平均连接层次聚类 + 动态剪枝”的一个变体（见基因调控网络推断与共表达分析）。

层次模块性

在许多真实网络中，小而紧密的模块组合成较大、较松散的模块，再逐级组合，形成层次模块化结构。Ravasz 与 Barabási 的确定性层次模型给出了一个可解析的例子：从一个 5 节点完全图开始，每一步复制 4 份并把复制品的外围节点连到原来的中心节点。这一构造产生度指数 $\gamma=1+\ln5/\ln4\approx2.16$ 的无标度网络，而且聚集系数随度按 $C(k)\sim k^{-1}$ 递减——高度节点连接不同模块，邻居之间很少相连。$C(k)$ 随 $k$ 递减常被当作层次模块性的一个经验特征（但并非充分条件）。