摘要：现有的复杂网络社团挖掘算法大多无法处理具有重叠性的社团结构，该文提出一种度量节点间关系的边向量，通过对边向量的聚类计算来得到网络中节点的社团结构。对简单的重叠性网络计算验证，该方法能够得到较好的社团划分，可以处理具有重叠性的网络划分。
关键词：复杂网络；社团挖掘；边向量；边聚类
中图分类号：TP18文献标识码：A文章编号：1009-3044(2012)10-2169-03
Community Structure Detection Algorithm Based on Edge Vector Clustering
LI Xiang，LI Shi-qiang，ZHAO Qing-hu
(Network Information Center，Nanjing University of Information Engineering，Nanjing 210044, China)
Abstract: Most of the existing complex network of associations mining algorithms can not handle overlapping community structure .In this paper,the edge vector of the relationship between a measure of the node, cluster computing to the edge vector to get the community structure of the nodes in the network .Overlapping network computing authentication, this method can get a better division of societies and can deal with overlapping network.
Key words: complex networks; community detection; edge vector; edge clustering
复杂网络近年来受到来自科学与工程各个领域研究者越来越多的关注，已经逐渐成为研究的一个热点。复杂网络是对现实世界中各种复杂系统的抽象表示，如万维网、人类社会关系网等。越来越多的研究表明，复杂网络有一些显著特征，社团结构就是其中之一。
社团结构是指内部节点连接相对紧密，而节点之间连接比较稀疏的群落[1]。人们常说的“物以类聚人以群分”，就是根据社团结构的这个特性而言的。寻找网络中的社团结构，对于分析和了解现实网络都有着非常重要的意义。
现阶段，研究者们已经提出了许多社团发现算法。较早社团发现算法包括Kernighan-Lin算法[2]和基于Laplace图特征值的谱平分法[2]。Newman和Girvan提出的GN算法[1]是一种基于边界数（Edge Betweenness）的分割方法，将网络划分成越来越小的部分。该算法计算量大，并且划分出的社区没有一个定量描述。Radicchi等人在GN算法基础上作了进一步改进，提出了快速分裂算法[3]。
但是，目前的大多算法将一个节点仅归属于一个社区。然而在现实自然界中，事物具有多样性的特点，一种事物往往可归属到不同的类别中，社团间存在大量重叠的现象，一个节点可属于多个社团。
于是，近年来研究者们开始转向重叠社团挖掘方向，并完成了一些初步的研究，如Gergely Palla提出的k-clique算法[4]等，但研究者的重心仍然放在节点上。
考虑到现实中的节点往往具有多种身份属性，它们会根据不同的身份聚集在相应的社团中。就是说，节点之间的联系是基于边的[5]。
该文结合这种发现，将研究重点放在联系节点的边上，提出了一种边的定义，利用边对复杂网络的节点进行扩展得到边向量的矩阵，通过对该边向量矩阵进行聚类划分得到具有共性的边的划分，进而来得到节点集的不同社团划分。
实验证明，该方法可挖掘出具有相似边特性的节点，能有效地将网络划分成若干社区。
且各个社区内部的节点集是具有相似属性的。
1基本概念和相关定义
1.1复杂网络数据的表示
在复杂网络的研究中，我们得到的数据是表征节点们彼此联系的数据。设节点集为D。
一个节点用它的邻接节点集来表示。
如节点1和节点2，节点3，节点4相连，{节点2，节点3，节点4}称为节点1的邻接节点集。
D1=[D2,D3,D4]
所有节点的向量构成一个邻接矩阵。
用图来表示，复杂网络对应一个无向图G=
1.2边向量的定义
虽然一个节点蕴含多种身份属性，但连接两个节点之间的边却是有明确含义的，这条边体现的是连接的2个节点所共同具有的属性。
定义边向量为：
即2个节点的边向量由这2个节点向量的公共部分构成。
设D1=[D2,D3,D4,D5,D7]和D2=[D2,D3,D4,D6]。则D1,2=[D2,D3,D4]。
一个复杂网络有N个节点，通过彼此计算边向量可以扩展为一个N*N的边向量矩阵。通常，这是一个稀疏矩阵。如Di和Dj没有共同邻接节点，则Di,j =0。
如Di和Dj有共同邻接节点Dm1,Dm2,..Dmk，则Di,j=[Dm1,Dm2,..Dmk,0,...0]。
边向量矩阵的特殊性：向量矩阵的元素不是一个数值，而是一个向量。
2聚类算法和实验分析
2.1数据准备
以19个节点构成的网络为例，该网络包含19个节点，37条边。图1 19个节点组成的网络
对数据集矩阵化得：可以得到边向量矩阵D=[]
Di,j,1≤i≤n,1≤j≤n。n=19。（5）
2.2边向量的相似计算
复杂网络是离散型多维度向量的数据，研究者们已经提出很多种针对此类数据计算相似度的方法，最经典的是Simrank共享最大邻法和离散余弦相似度法[6]。
分别是基于图划分和向量余弦夹角的方法，可以证明，它们是等价的。
该文采用离散余弦法来计算边向量的相似度。
计算公式：
cos(θ)=
2.3边向量的聚类分析
研究发现，同一社区内的点集倾向于拥有相似的属性，对社区内的点而言，就是要拥有相似的边向量。因此，对边向量进行聚类计算。可以得到边向量的划分集。而一个划分内的边向量所涉及的节点集合就是一个社团划分。
为使分析更简明，该文采用离散化的经典K-means聚类[6][7]，
K-means算法是将样本聚类成k个簇（cluster），具体算法简述如下：步骤1：任意选取k个聚类质心点为μ1,μ2,....μk∈Rn作为初始中心，步骤2：对于每一个边向量Di,j，计算其应该属于的类Cn。
Cn= argmin这里，边向量之间的距离计算采用边向量离散相似度的倒数。步骤3：对于每一个类Cm，计算该类的质心
，如果J>=给定的ε，返回步骤2，继续迭代。步骤5:：J<给定的ε，输出此时的划分Cn。
对上述D=[] Di,j进行计算，最终结果为
3结束语
基于边向量的聚类划分方法能够有效的挖掘复杂网络中的社团，并且能处理重叠型社团挖掘。但是，现阶段算法的复杂度太高，只能适用于节点数不是太多的数据。有效地降低算法的复杂度将是下一步研究的方向和重点。
参考文献：
[1]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006:162-191.
[2]杨博,刘大有,Liu Jiming,等.复杂网络聚类算法[J].软件学报,2009,20(1):54-56.
[3] Chen Duanbing，Fu Yan，Shang Mingsheng. A Fast and Efficient Heuristic Algorithm for Detecting Community Structures in Complex Networks[J].Physica A,2009,388(13):2741-2749.
[4] Fortunato S,Latora V,Marchiori M.A method to find community structures based on informaton centrality.Phys.Rev.E,2004,70:056104.
[5] Clauset A. Finding local community structure in networks[J].Physical Review E，2005，72.
Newman MEJ.Modularity and community structure in networks[J].Proc Natl Acad Sci USA，2006，103(23):8577-8582.
[6]赵凤霞,谢福鼎.基于K-means聚类算法的复杂网络社团发现新方法[J].计算机应用研究,2009，26(6):2041-2043.
[7]蔡晓妍,戴冠中,杨黎斌.基于谱聚类的复杂网络社团发现算法[J].计算机科学,2009,36(9):49-50.