【摘 要】在分析了聚类方法中的相似度的基础上，本文给出了相异性系数的定义，提出了基于相异性系数和谱分析的社团发现算法（DSC算法），用改进的谱方法把网络映射到特征向量空间上，计算各个节点对的相异性系数，然后用层次聚类方法得出网络的社团结构。经计算机模拟网络、Zachary空手道俱乐部网络验证，该算法获得网络的社团结构准确率较高，运行速度是Luca Donetti方法的近10倍（Luca Donetti. Stat. Mech. Theor. Exp.， 2004， P10012）。
【关键词】聚类；相似度；相异系数；谱分析；社团发现
0 引言
真实世界中的许多复杂系统都可以通过网络来描述，例如社会关系网络、科学家合作网络、Internet、万维网、食物链网络、新陈代谢网络等[1-2]。网络中的节点代表真实系统中不同的个体，边则表示个体之间的关系。
在复杂网络的研究中，人们已经发现了它的小世界、无标度、聚集性、社团结构等重要统计特征。其中，社团结构是指每个社团内部的节点之间的连接比较紧密，而社团之间的连接则比较稀疏[1]。复杂网络中社团结构的研究起源于社会学，文献[1]中的研究成果，使得复杂网络中的社团发现成为近几年复杂网络领域的一个研究热点，并形成了复杂网络中一个重要的研究方向。
目前，已经有多种社团发现方法提出，其中最经典的是图形分割中的Kernighan-Lin算法[3]和分级聚类中的GN算法[1]，Kernighan-Lin算法是根据使社团内部及社团间的边最优化的原则对原始的网络进行分类，GN算法是基于边介数的分裂算法。其它的算法还有基于连边密度、相异性、信息中心度、随机游走、谱方法、最优化某个目标函数等等。在所有社团发现算法中时间复杂度和查找准确性仍是最为关键的两个问题。
本文在聚类分析和传统谱方法的基础上，提出了一种基于相异性系数和谱分析的社团发现算法（DSC算法），用改进的谱方法把网络映射到特征向量空间上，通过计算各个节点对的相异性系数，用层次聚类方法得出网络的社团结构。该算法具有较高的社团查找准确率，且较好的改善了运行时间，运行速度是Luca Donetti方法[4]的近10倍。
1 算法介绍
网络中的社团发现与数据的聚类很相似，把聚类方法应用到网络中就可以发现网络的社团结构。用聚类方法来发现网络的社团结构，首先要把网络中节点的拓扑性质转化到欧式空间上或特征向量空间上，然后根据转化后的数据之间的相似性来进行聚类。本文采用了改进的谱方法把网络映射到特征向量空间上，在分析了聚类方法中常用的相似性度量方法后，提出了相异性系数的概念，基于异性系数用层次聚类来实现网络的社团结构划分。
1.1 聚类算法中数据的相似性度量
使用聚类方法对数据进行聚类，数据之间相似性的度量方法在很大程度上影响聚类的效果，因此，用聚类方法来发现网络中的社团结构，定义网络中节点之间的相似性也至关重要。在聚类分析中应用广泛的相似性度量方法有两种，分别是欧式距离和夹角余弦。
1.2 相异性系数
2 实验结果与分析
2.1 计算机生成的网络
用计算机生成一个具有128个节点的网络，网络分为4个社团，每个社团的节点数均为32个。图1是该网络的邻接矩阵图。
从图1可以看出，该网络的社团结构很明显，用DSC算法对该网络进行社团划分，并将划分结果与Luca Donetti方法[4]进行比较，表1显示了两种方法的比较结果：
从表1可以看出，两种方法社团划分准确率都比较高，最佳划分时的模块度也相等，但DSC算法在运行时间上大概是Luca Donetti方法的1/10，提高了算法的运行速度。
2.2 Zachary空手道俱乐部网络
在层次图中，计算每一层划分的模块度Q值，我们计算得到网络分为两个社团时Q为最大值0.402。节点15、16、19、21、23和节点33的相异性系数相等（精确到小数点后四位），因此处于同一层上。和网络的实际划分相比，节点3和14没有被正确归类，因为节点3和14与两个社团的联系都很紧密。图3是用DSC算法得到的Zachary空手道俱乐部图，方形和圆形分别代表两个社团，为最佳划分结果，不同颜色表示的是进一步的子图划分。
3 总结
本文给出了相异性系数的概念，提出了一种基于相异性系数和谱分析的社团发现算法（DSC算法），用改进的谱方法把网络映射到特征向量空间上，通过计算各个节点对的相异性系数，用层次聚类方法来探测网络的社团结构。并将DSC算法与Luca Donetti的方法作了比较，在划分结果相同的情况下，DSC算法在运行时间上优于Luca Donetti的方法。DSC算法不足之处是：用了层次聚类的方法，由于层次聚类在中小数据规模上能取得很好的效果，但在大规模数据上受到噪声的干扰会降低层次聚类的效果，因此本文提出的DSC算法适合于中小规模网络的社团发现，在大规模网络上进行社团探测将是今后要做的主要工作。
【参考文献】
[1]Girvan M， Newman M E J. Community structure in social and biological networks[J]. Proc. Natl. Acad. Sci， 2002，99：7821-7826.
[2]汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].北京，清华大学出版社，2006：162-198.
[3]Garey M R， Johnson D S. Computers and Intractability： A Guide to the Theory of NP-Completeness[M]. San Francisco： W. H. Freeman Publishers， 1979.
[5]Zhou H. Distance， dissimilarity index and network community structure[J]. Phys. Rev. E，2003，67：061901.
[责任编辑：陈双芹]
