- 1 -
中国科技论文在线
一种相似度矩阵的社团挖掘算法#
李琳1，陆松年1，陈秀真2，李生红1**
基金项目：教育部博士点基金（20070248002）
作者简介：李琳（1983 年-），男，博士研究生，复杂网络方向
通信联系人：（1947-），男，教授 博士生导师， 计算机网络
（1. 上海交通大学 电子与电气工程系学院，上海 200240；
2. 上海交通大学 信息安全学院，上海 200240） 5
摘要：近来，科研人员发现很多现实实例可以看作是复杂网络系统，因此，复杂网络的很多
特点成为了当今的研究热点。社团结构是复杂网络的一个重要的性质，通过该性质可以分析
网络节点之间的联系等特点，因此在社会学、计算机科学、生物学等领域都有很重要的应用。
通过分析社会学中人际关系的特点，抽象出了一种名为相似度的参数，并用此参数组成的相
似度矩阵分析复杂网络，将网络划分为多个网络社团。将该相似度矩阵应用于社会学中经典10
的 Zachary网络表明了该方法的可行性。
关键词：复杂网络；社团结构；相似度矩阵
中图分类号：TP391
Detecting communities of complex network based on the 15
similarity matrix
Li Lin1, Lu Songnian1, Chen Xiuzhen2, Li Shenghong1
(1. Dept. of Electronic Eng., Shanghai Jiaotong Univ., Shanghai 200240;
2. School of Information Security Engineering, Shanghai Jiaotong Univ., Shanghai 200240)
Abstract: Recent years, researchers noticed that many applications could be treated as complex 20
networks, so the basic features of complex network draw much attention in many fields. Some
applications could be used in many fields including social network, computer network, and biology
network and so on by analyzing the community structure of complex networks. Based on the analysis
of social network's feature, a kind of parameter called similarity can be got. The complex network was
divided into several communities by using the similarity matrix. Experimental result in Zachary 25
networks shows that the algorithm proposed is feasible in many real examples.
Key words: Complex network; Community structure; Similarity matrix
0 引言
近年来，越来越多的科研工作者发现复杂网络系统是很多实际系统的模型抽象，因此，30
复杂网络的很多特点和性质成为了研究的热点。人们发现，很多的复杂网络都存在一个共同
的特性——社团结构，即一个网络被人为的划分为几个子部分，每个单独的子部分内部的点
之间相互连接较为紧密，而子部分之间的连接则较为稀疏。
近年来，很多学者通过研究复杂网络的拓扑结构和数学特性，提出了社团挖掘和检测算
法。从研究手段来讲可以分为两大类。第一类算法利用了网络拓扑结构特点。这类算法从复35
杂网络边与点之间的关系出发，通过分析社团内部节点和连边的特点，发现这些节点并逐步
的寻找社团结构节点。Girvan 和 Newman 等人针对复杂网络中的社团结构特点，提出以经
过一条边的最短路径的数目作为边的权值，从而划分社团的算法[1]。文献[2]对文献[1]中的
内容进行改进，通过分析网络中的几何图形结构，根据一条边从属于的三角形的个数作为该
边的聚集系数，从而将边区分为社团内部的边和社团之间的边，进而达到社团划分的效果。40
- 2 -
中国科技论文在线
文献[3]中作者将文献[2]和文献[1]中的内容结合，将边的聚集系数引入到边的 betweenness
上面，通过每次去掉边的 betweenness 和聚集系数的比值，从而更准确的检测网络社团结构。
文献[4]就是一篇基于 Web 网络社团结构挖掘的文章。该文献中运用图论中的最大流最小割
定理，通过计算两个节点间的最小割，从而获得两个社团间的边的信息，进而找出社团间的
边。第二类社团挖掘算法是通过数学的手段，利用矩阵分析等数学工具作为社团挖掘算法手45
段[5]。文献[5]中，作者在谱分析算法的基础上，将谱分析的方法做了延拓，从而可以划分多
个社团结构。模仿文献[5]中作者的思路，通过分析网络的拓扑几何结构，从而构造了另外
一种划分矩阵，并利用谱优化的方法，可以很好的实现社团划分的目的，但是该方法只对网
络中三角形多的网络效果较好，如果网络过于稀疏，该算法的效果并不突出[6]。
1 相似度矩阵 50
现有的很多复杂网络实例都是现实社会中人与人之间关系的抽象，而当今的互联网的快
速发展，是的越来越多的人通过网络表达他们的观点，各种网络论坛应运而生。人们利用论
坛作为平台相互交流，实际上是人与人之间的社会关系在互联网这个虚拟社会上面的映射和
模拟。因此，互联网络和社会网络在很多特点上有着很大的相似性。基于以上的思想，很多
的学者提出利用社会网络的特点，来划分复杂网络中的社团结构。很多算法都利用共同最近55
邻居的方法来表示复杂网络中的两个节点的相似度。文献[2]把整个复杂网络中的节点看做
是现实中的人，连边是现实中人与人直接的关系，在社会生活中，若有一个人同时是两个人
的好友，则这两个人相互也为好友的可能性是很大的。用网络图来表示这个特点就是该网络
中含有相当大量的三角形。文献[8]都是利用直接邻居节点来计算两个节点之间的相似度。
但是在社会网络中，这种方法有时精确度不是很高，因此将这种关系推广改进，从而在一定60
程度上提高其精确度的方法是可行的。
基于以上思想，通过对社会网络中人际关系的探求，以两个节点的直接邻居节点之间的
联系强弱来表明这两个节点之间的相似度，即如果两个节点他们的直接邻居节点间的联系密
切到一定程度，那么这两个点之间的相似度也就相对较高，那么他们属于同一个社团的可能
性也就更大。在现实生活中，如果每个人都用网络图中的节点表示，朋友关系用网络图中的65
连边代替，如果两个人关系很亲密的话，那么他们朋友之间的关系一定也很密切。表现到图
里面，就是指如果两个节点其直接邻居节点之间关系紧密，则这两个节点属于一个社团的可
能性很大。
公式化表述上述思想，令 G=(V, E) 是一个无权无向图，其中，V 表示所有网络图中的
所有节点的集合，而 E 代表该图中所有边的集合。一个对称的矩阵 A 称为邻接矩阵，其元70
素 ijA 满足以下条件：
1 ij E
0 ij Eij
A
∈⎧= ⎨ ∉⎩
令 { }| 1i j ijN v A= = ，即与节点 i直接相邻的所有节点的集合，对于每一个节点 i，
i V∈ ，设 ik 表示节点 i的度。根据以上思想，我们可以发现，两个节点间的公共直接邻居
节点的数目，实际上就是从这两个节点中的一个节点出发，路径长为 2 的最短路径条数；而75
两个节点的直接邻居节点间的连接数目，即为从这两个节点中的一个节点出发，路径长为 3
的最短路径的数目。因此，相似度矩阵中的各个元素可以表示为公式 1：
- 3 -
中国科技论文在线
2 3
( , )
0 ( , )
ij ij
ij i j
A A
i j E
S k k
i j E
⎧ + ∈⎪= ⎨⎪ ∉⎩
(1)
其中，分母上的 i jk k 表示将节点 i和节点 j的直接邻居节点看做完全二分图时边的条数。
对于公共直接邻居节点可以认为的看做两个节点，即如果 1ik kjA A = ，则可以将节点k看做80
是两个节点：k′和 k′′，其中k′为节点 i的直接邻居，节点 k′′为节点 j的直接邻居。则完全
二分图的两部分之间的边数即为 i jk k 。
文献[1]中，作者总结了基于网络边权值的社团查找分裂算法。分裂算法共分四步：1)
计算网络中各个节点间的 betweenness；2）移除 betweenness 最大的边；3）重新计算该边移
除后受到影响的各边的 betweenness；4）重复第二步，直到所有的边都被移除。但是这种算85
法的存在着时间复杂度高，并且不知道应该把整个网络划分为几个社团的弊病。因此本文采
用文献[2]中提出的强弱社团的定义和方法来作为社团划分停止的条件。具体的算法步骤如
下：
输入：一个具有 n 个节点的复杂网络图
输出：该网络的一个社团划分结果 90
第一步：初始化整个网络，并对网络节点数据做预处理
第二步：利用公式 1 计算各个节点间的相似度，并寻找相似度最小的一对节点
第三步：去掉相似度最小的一对节点之间的连边
第四步：判断社团结构划分是否完成，如果没有则转到底 2 步继续计算，如果完成了，
则退出。 95
需要说明的是，上面的算法中，网络节点的预处理过程主要是将一些度为 1 的节点删掉，
因为这些节点只可能属于和它相连的那个节点所在的社团。
2 仿真实验
为了检测上述算法的可行性和效果，将该算法在一个很著名的社会学实例 Zachary 上进
行测试。在 20 世纪 70 年代初期，Zachary 用了多年来观察美国一所高校中的一个空手道俱100
乐部中成员之间的关系，并且，基于此关系构造了一张关系图[13]。
图 1 文献[13]中的社团划分结果
The result obtained from Ref[13] 105
- 4 -
中国科技论文在线
在这张关系图中，每个节点代表了俱乐部中的一个成员，连边代表了两个成员之间的关
系，如图 1 所示。事有凑巧，在这两年间，该俱乐部的主管与校长之间就是否提高俱乐部收
费的问题产生了摩擦，而俱乐部中的成员也根据意见的不同分成了两派，一派以俱乐部主管
为核心构成了一个小俱乐部，另一派以校长为核心形成了一个小团体。图中节点 33 和节点110
1 分别代表了俱乐部的主管和校长，以他们为核心，黑色的圆点和白色的方格两种节点分别
代表了该俱乐部中的两派成员。以上的例子为复杂网络社团挖掘提供了很好的实际例子。将
该数据输入上文提出的方法，得到的计算结果如图 2 所示：
图 2 本文算法的社团划分结果 115
the result obtained from the algorithm proposed in this paper
通过两个图的对比，可以发现除了节点 10 外，其他的节点都被正确的划分了出来。分
析节点 10 的特点，可以发现该节点的度为 2，并且与两个社团都有联系，因此节点 10 的社
团归属本身就是有歧义的，文献[1]也在一定程度上支持了本文的结果。该结果表明本方法120
在社会网络中具有较好的效果。
3 结论
本文针对复杂网络中社团挖掘和检测问题，通过分析社会网络中各个节点之间的关系和
复杂网络的特点，提出了一种基于相似度矩阵的社团检测算法。该算法通过两个节点间的直
接邻居之间联系的紧密程度，来表征两个节点的相似度，利用分裂算法，实现复杂网络社团125
的发掘。由于该算法综合考虑了两节点的直接邻居以及他们之间的关系，因此准确性得到了
一定程度的提升。将该算法应用于经典的 Zachary 网络，得到了很好的结果。但是本文的算
法时间复杂度偏高，因此下一步的重点工作将是寻找如何降低时间复杂度的算法。
[参考文献] (References) 130
[1] Filippo Radicchi, Claudio Castellano, et al. Defining and identifying communities in networks [J]. Proc Natl
Acad Sci USA, 2004, 101:2658-2663
[2] Ju Xiang, Ke Hu, Yi tang. A class of improved algorithms for detecting communities in complex networks [J].
Physica A, 2008, 387 : 3327-3334
[3] Gary Flake, Steve Lawrence. Self-organization and identification of web communities [J]. Computer, 2002, vol. 135
35 No. 3: 66-71
[4] , . Finding and evaluating community structure in networks [J]. Phys. Rev. E , 2004,
69: 026113
[5] . Finding community structure in networks using the eigenvectors of matrices [J]. Phys. Rev. E,
2006, 74, 036104 140
[6] Belkacem Serrour, Alex Arenas, et al. Detecting communities of triangles in complex networks using spectral
- 5 -
中国科技论文在线
optimization [J]. Computer Communications. 2010，in press
[7] YanQing Niu, BaoQing Hu, et al. Detecting the community structure in complex networks based on quantum
mechanics [J]. Physica A, 2008, 387:6215-6224
[8] Fuding Xie, Min Ji, et al. The detection of community structure in network via an improved spectral method [J]. 145
Physica A, 2009, 388: 3268-3272
[9] , Petter Holme, et al. Vertex similarity in networks [J]. Phys. Rev. E, 2006, 73, 026120
[10] Ying Pan, De Hua Li, et al. Detecting community structure in complex networks via node similarity [J].
Physica A, 2010, 389: 2849-2857
[11] Gaoxia Wang, Yi Shen, et al. A vector partitioning approach to detecting community structure in complex 150
networks [J]. Computers and Mathematics with Applications, 2008, 55: 2746-2752
[12] Zachary W W. An information flow model for conflict and fission in small group [J]. Journal of
Anthropological Research, 1977, vol 33 No. 4: 452-473
[13] Francesc Comellas, Alicia Miralles. A fast and efficient algorithm to identify clusters in networks [J]. Applied
Mathematics and Computation. 2010, 217:2007-2014 155
