第5期 李建元，等：谱图聚类算法研究进展 ·407· 证的角度上，文献[3,5,43]提供了归一化拉氏矩阵 最小生成树(MST)聚类法是Zahn(]提出的， 更适用于谱聚类的证据，即意味着归一化谱聚类性 该算法首先由图的邻接矩阵得到最小生成树，然后 能比非归一化谱聚类好.文献[44]指出在某种特定 从最小生成树中去除掉若干权值较大的边从而产生 的条件下采用非归一化谱聚类较好.而文献[26]从 一个连通分量集，以此达到聚类的目的.该方法在探 统计一致性的理论高度，证明了归一化拉氏矩阵优 测明显分离的簇时是成功的，但若改变节点密度，其 于非归一化拉氏矩阵的事实 性能会变差.另一个缺点是，Zahn的研究是在事先 另一种可选的矩阵是概率转移矩阵（记作P), 知道簇结构（如分离簇、接触簇、密度簇等）的前提 概率转移矩阵实质上就是相似矩阵的归一化形式， 下进行的. 其表达式如下： 图的割是指去除一定的边将一个图分割为多个 P=DA 连通分量，其中被去除的边权的总和称为割（如式 由于归一化后的相似矩阵的行和为1，因此P (1)所示).Bames32]最早提出了最小割聚类准则， 中的元素可以理解为马尔可夫转移概率，2个节点 即在把一个图分割成k个连通子图时，寻求割的最 间的转移概率越大，则同簇的可能性也越大.概率转 小化.Alpert和YaoI8]较早提出了基于谱方法来解 移矩阵的谱也包含了分割图所需的必要信息，只不 决最小割准则的方法，为后来的谱聚类的发展奠定 过与拉氏矩阵谱稍有区别，例如，次大特征值的特征 了重要基础.Wu和Leahy(s6将最小割运用到图像 向量可以指示图的二分，多个主特征值的特征向量 分割领域，并基于网络最大流理论「2]来求解最小 可以指示图的k分割.有趣的是，如果入是Px=入x 割.该准则在图像分割方面有些许成功的应用，但其 的解，则1-入是方程Lx=Dx的解. 最大的问题是可能会导致分割的严重不均衡，如分 值得一提的另一种新颖矩阵是模块度矩阵（记 割出“孤点”及“小簇”.能够产生较均衡的分割的研 作B).其相关研究主要出自复杂网络社区649，它 究有Wei和Cheng提出的比率割、Shi和Malik[sI 具有明显物理意义，其表达式如下： 提出的规范割、Dig等人]提出的最小最大割和 B=A-dd Sarkar等人[s9]提出的平均割，其目标函数分别为 2m 式(2)~(5).这些优化目标能够较好地避免最小割 式中：d代表列向量，其元素为节点的度；m表示图 造成的分割严重不均衡的问题， 的总边权；B中的元素表示的是成对节点间实际的 以图的二分割为例，令V为一个给定的点集，N 边数与期望的边数之差，或者说是实际的边数超出 表示V的一个子集，用M代表八N,w(·,·)表示 期望边数的程度.因此，此类矩阵也直接促成了一个 2个点集之间边的总边权，则有： 目标函数，即最优分割应使得各社区中（与“簇”相 C (N,M)w(N,M), (1) 对应)边的稠密程度尽量超出预期。就矩阵特性而 C (N,M) 言，模块度矩阵与拉氏矩阵具有相似之处，例如：行 R(N.M)=I NII MT' (2) 和（列和）为0,0是其特征值；但又具有明显区别， N(N,M) C.(N,M)C(N,M) (3) 模块度矩阵不是一个半正定矩阵，也就是说其部分 w(N,) (M,, 特征值可能为负，就分割图方面，基于其最大特征值 Mon(N,M)= C(N,M)C(N,M) w(N,N) +(M,M)' (4) 的特征向量可以进行网络二分，基于多个主特征向 C(N,M)C(N,M) 量可以进行网络飞分， A(N.M)=NIM (5) 2主要的图割目标函数 近l0年来复杂网络的研究快速崛起，Newman 系统地研究了无权网络、加权网络乃至有向网络中 图割聚类的雏形是最小生成树方法(minimum 的网络社团结构谱算法，运用了模块度(modularity) spanning tree,,MST)0s).之后出现的目标函数有 函数进行社团发现[649]，模块度准则的思想较为新 最小割(minimum cut,Mincut)[32,s2s3)、比率割(ratio 颖：以无权图为例，当各社团中的边的比例尽可能地 cut,Rcut)[o,4s6、规范割(normalized cut, 超出“期望”的边的比例时，才认为是合理的分割. Ncut)5,]、最小最大割（max flow/min cut, 其中“期望”的边数指的是根据配置模型得到的一 MMCut)[s1和平均割(average cut,.Acut)9等.除此 种随机图模型.这显然与传统的图割聚类方法的出 以外，还有一些其他的优化目标，如用谱宽松来解决 发点不同，其目标函数为 K-means目标函数的方法I6oj,以及文献[23]提出的 (6) 双准则方法， 0=(4,-2