大型复杂网络中的社区结构发现算法
胡 健1，董跃华1，杨炳儒2
(1. 江西理工大学信息工程学院，赣州 341000；2. 北京科技大学信息工程学院，北京 100083)
摘 要：在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现的领域。对于简单图的社区结构发现，引入边聚集系数的概念，提出基于边聚集系数的社区发现算法。将安然邮件数据集作为测试数据集，通过算法对比分析，证明该算法在时间复杂度上可以提高一个数量级。 关键词：边聚集系数；社区结构；社区发现
Community Structure Discovery Algorithm
in Large and Complex Network
HU Jian 1, DONG Yue-hua 1, YANG Bing-ru 2
(1. Faculty of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000; 2. School of Information Engineering, University of Science and Technology Beijing, Beijing 100083)
【Abstract 】The automatic search and community discovery in large and complex network has important practical applications. This paper applies the hypergraph based model and cluster algorithm in community structure discovery, introduces the concept of Edge Clustering Coefficient(ECC) to community structure discovery of simple graph and proposes an algorithm of community discovery based on ECC. Enron e-mail data sets are test data sets, through comparative analysis of algorithm, to prove that this algorithm can significantly improve the time complexity. 【Key words 】Edge Clustering Coefficient(EBB); community structure; community discovery
计 算 机 工 程Computer Engineering 第34卷 第19期
Vol.34 No.19 2008年10月
October 2008
·网络与通信·
文章编号：1000—3428(2008)19—0092—02
文献标识码：A
中图分类号：TP301.6
1 概述
复杂网络中社区发现(community finding)的研究起源于
社会学的研究工作。能够在大型复杂网络中自动搜寻或发现“社区”具有重要的实际应用价值[1]，如社会网络中的社区可能代表的是根据兴趣或背景而形成的真实的社会团体，引文网络中的社区或许代表的是针对同一主题的相关论文，万维网中的社区或许就是讨论相关主题的若干网站，而生物化学网络或者电子电路网络中的社区可能就是某一类功能单元。发现这些网络中的社区有助于更有效地理解和开发这些网络。与社区发现相关的成熟理论包括图论以及模式识别。Wu 和Huberman 的研究成果[2]以及Newman 和Girvan 的研究成果[3]使得复杂网络中的社区发现成为近几年复杂网络领域的一个研究热点并形成了复杂网络中的一个重要研究方向。Newman 和Girvan 把社区发现问题定义为将网络节点划分成若干组，使得组内的节点之间连接比较稠密而不同组节点之间的连接则比较稀少。Newman 和Girvan 在其研究中提出了基于边介数(edge betweenness)概念的分割方法，尽管该方法计算量很大，但由于其性能优越而成为社区发现研究的重要参考模型。
对于一般简单图的社区发现，也可以称之为基于图的聚类，把具有相同或者相似属性的有共性的节点聚合到一起，形成一个个的聚类[2]。这方面的方法有很多，最常用的有G-N 算法、谱二分法和层次聚类法。
尽管人们对复杂网络的社区发现问题已进行了大量的研究，但是仍然存在一些目前无法解决的基本问题[4]，如社区的概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需要的计算量却很大；更为
关键的是，很多算法不是针对异构数据集。这说明复杂网络中社区发现的研究还远没有成为体系，还有很多工作待完善。
2 边的聚集系数定义
为了刻画描述一个网络，通常有这样几个角度，一个是这个网络中点与点之间的距离以及整个网络的平均距离；另一个是每个节点的度以及整个网络的平均的度；还一个就是节点之间聚集的情况，点的聚集系数这个概念是用来体现对于某个节点A 来讲，如果B 和C 都是A 的邻接点(朋友关系)，那么B 和C 两者之间也有邻接(朋友)的可能性。
定义1 某节点n 的聚集系数(node clustering coefficient) ()C n 如下定义：
(1)假设某节点n 的度是k ，则该节点的这些邻居之间可能形成边的最大数是：
()(1)/2T n k k =−
(2)()E n 表示图中这些邻居之间实际的边的个数，则 ()()/()C n E n T n =
定义2 一个网络的聚集系数为这个网络中节点的聚集系数的平均值。
如图1所示，节点1的度为5，所以与它相连接的5个顶点之间最多存在54/210×=条边；而实际上另外5个顶点相互之间存在6条边，所以节点1的聚集系数是6/100.6=。
基金项目：国家自然科学基金资助项目(60675030)
作者简介：胡 健(1967－)，男，副教授、博士，主研方向：数据挖掘，智能信息检索；董跃华，副教授；杨炳儒，教授、博士生导师 收稿日期：2008-08-01 E-mail ：euguenehu@yahoo.com.cn
—93—
1
2
3
5
4
6
图1 求凝聚系数示例图
G-N 算法借助点介数的概念，引入了边介数的度量方法，类似的也借助顶点的聚集系数，来引入某一条边的聚集系数(Edge Clustering Coefficient, ECC)概念。假设有一条边ij E ，其顶点为i 和j ，
考虑网络中是否有以及有多少个另外的节点k 与i ,j 都相邻，即存在另外5条边jk E ,ik E 与ij E 形成三角环
(即边数为3的闭合路径)，若一个三角环包含一条连接不同
社区的边，则该三角环中的另2条边中的某一条仍然连接这2个社区的可能性将很大。但是由于连接不同社区的边非常稀少，因此包含一条给定的连接不同社区的边的三角环可能很多。因此，将一条边的边聚集系数定义为包含该边的三角环所占比例：
1min(1,1)
ij ij i j z C k k +=
−−
其中，i k ,j k 分别表示节点i 和j 的度；ij z 表示网络中实际包含该边的三角环的个数。上式中的分母表示包含该边的最大可能的三角环的个数。在图1中，边3,6E 的节点3n 和6n 的度数分别是5和4，则最多形成min(51,41)3−−=个三角环，而包含3,6E 的三角环有3个1,3,6∆,3,4,6∆,3,5,6∆，所以，3,61C =。
3 ECC 算法描述
首先给出关于简单图中社区的定义，一个社区V 实际上是整个网络G 中部分子图，即V G ⊂。对于V 中的一个节点i ，用i k 表示该节点的度数，而在计算该节点的度数时，其邻接点分为来自V 内部(即,()in j V i i j k V A ∈=∑)和V 外部(即
,()out j V i i j k V A ∉=∑)2个部分，所以有()()()in out i i i k V k V k V =+。
下面给出一个社区的紧密程度在2个级别上的定义。
定义3 如果在一个社区V 中，每个节点的()in i k V 都大于
()out i k V ，即
()()in out i i k V k V i V >∀∈
则称该社区是强连接社区。
定义4 如果在一个社区V 中，所有节点的()in i k V 之和大于()out i k V 的和，即
()()in out i i
i V
i V
k V k
V i V ∈∈>∀∈∑∑
则称该社区是弱连接社区。
在本实验中，只有满足上述2个定义的子图才作为一个社区，从开始的整个图，不断地去除边，不存在满足上述定义的社区时便停止程序。整个方法步骤与G-N 算法类似，都是基于去边，但不是根据边介数选择要去除的边，而是根据边的聚集系数这一新指标。下面是该算法步骤：
(1)计算整个图中的每一条边的聚集系数ij C ；
(2)把其中聚集系数最小的边ij E 去除掉；
(3)重新计算以i 和j 为顶点的所有边的聚集系数，其他的边不需要重新计算；
(4)返回步骤(2)，直到网络中不存在任何符合上述定义的
社区。
4 实验及算法分析
以安然公司邮件数据集[5]作为测试数据集。首先进行预处理，导入到MySql 数据库中后，分别用数据库中的几个表保存响应信息，经过统计，在网络上与安然公司150个领导人有邮件联系的共计87 474人，其中公司内部有34 885人，外部有52 5人。参照其他邮件数据集预处理的经验，对整个网络进行，规定只留下满足如下条件的人员：(1)这个人的邮件总数超过30，而如果2个人的互通邮件总数超过 6封才在2个人之间画一条边，另外同时对于任意存在边的 2个节点之间的这条线，依据两者之间的邮件数可以作为这条边的权重。显然通过每个人的至少邮件总数以及5个人的至少邮件总数，可以调整整个网络的大小。Prefuse [6]是
一个基于Java 的网络可视化工具包，
用这个软件把结果显示。 通过调整每个人互通邮件的最少数量，得到不同大小的图。然后用ECC 算法进行社区分析后，部分截图见图2。对于一个含有n 个节点m 条边的图，整个算法的运行时间为
42(/)O m n ，而G-N 算法的时间复杂度是2()O m n 。本算法与
常用的4种算法的时间复杂度进行了对比(见表1)。对于稀疏图，本算法计算速度要比G-N 算法快一个数量级。
图2 经过社区分析后的部分截图 表1 时间复杂度对比分析
算法名称参考文献 时间复杂度
N-G 算法[3] 2
()O m n G-N 算法[7] 2
()O n m BB 算法 [8] 3()O n DA 算法
[9] 2(l b )O n n ECC 算法
本文
4
2
(/)O m n
但是，ECC 算法的不足是该算法依赖于网络中的三角关
系的多少，如果网络中三角关系很少，比如对于树状的网络，那么该算法将失去意义。实证研究表明，社会网络、Web 网页数据集、科学文献引用分析等领域中三角环的数量比较大，本算法还是有很大的应用空间。
5 结束语
本文主要讨论作为超图的特殊形式——简单图的聚类，在分析研究了近年来常见的一些方法基础上，提出了根据边的凝聚系数来求得下一步将要去掉的边，因为所考虑的是局部信息，去边以后不需要讲所有的边重新计算，所以降低了时间复杂度，这种方法比较适合于三角关系较多的网络。
（下转第100页）
—100
—100 200 300 400 500 600 700
传输范围/m 90807060
50403020100统治集更新次数/次
LOWID HIGHID WM AOW
实验场景是由NS-2中的setdest 随机生成的，大小为
1000m 1000m × ，节点数为30，节点的最大速度为 15 m/s 。为了对比实验效果，设置了2组AOW 参数。其中，LOWID 表示最小节点度算法；HIGHD 表示最高节点度算法；WM 表示最低节点移动性算法。AOW 中的参数为0.6,a =
ideal 0.2,0.2,5b c D === ；AOW1中的参数为0.2a =,0.6,b = ideal 0.2,10c D == ，其中，a , b , c 分别为移动性、节点度、剩
余能量的权重因子；ideal D 为理想节点度。
网络中的簇头数不宜过多或过少，否则都将使分簇的意义减弱或消失，在极端情况下退化成平面的网络结构。由 图1可以看出，HIGHD 中的簇头数最少，WM 中的簇头数在多数情况下是最多的，而其他算法介于HIGHD 与WM 之间。在AOW 和AOW1中，权重因子与理想节点度起到了调节簇头数的作用，由于AOW1中节点度的权重因子较大，而且理想节点度较高，因此簇头数较AOW 少。在具体应用中，可以根据实际情况调节AOW 的参数。
由图2可以看出，统治集更新的次数随着节点传输范围的增大先急剧增加，然后急剧减少，到300 m 左右开始缓慢减少，最后趋于一个固定值。WM 的统治集更新次数最少，HIGHD 最多，而AOW 与LOWID 介于两者之间。HIGHD 中的统治集更新次数较多是因为HIGHD 中簇头的选举只考虑
节点度，而节点的移动使得簇头的节点度处在变化中，2个簇头也会成为相邻节点，从而导致了簇结构的变化。WM 中统治集更新次数较少是因为WM 中簇头相对簇成员的移动性较小，簇结构变化较缓慢。AOW 算法介于两者之间，说明AOW 能在节点的移动性和节点度之间作很好的折中。
另外，当把传输范围设置在300 m 附近时，根据实际需要改变AOW 算法的权值，得到的簇头数在5~7之间。此时30个节点组成的网络中，统制集的更新次数也较少。而使用DSR 协议维护5~7个簇头的路由，网络开销比较经济。
在确定本方案有较好的性能后，将其在Windows XP 系统中实现，并成功移植到WinCE 模拟器中，程序的移植性 良好。
5 结束语
本文提出了一种将源路由协议与自适应加权分簇算法相结合的设计方案。实验结果表明，DSR 路由算法能够满足簇头节点路由转发功能的需要；AOW 分簇算法在仿真中比其他典型分簇算法更具优越性，并且通过调节解权重的分配，实现了灵活性。
参考文献
[1] 王海涛. Ad hoc 网络的体系结构和分簇算法研究[D]. 南京:
军理工大学通信工程学院, 2003.
[2] Basagni S. Distributed Clustering for Ad hoc Networks[C]//Proc. of
International Symposiun on Parallel Architectures, Algorithms and Networks. Washington, USA: IEEE Computer Society, 1999. [3] 龚月荣, 林晓明. 移动自组网反应式路由协议在Linux 中的实
现[J]. 计算机工程, 2004, 30(7): 98-100.
[4] Vahid G. Analysis of Network Traffic in Ad hoc Networks Based on
DSDV Protocol with Emphasis on Mobility and Communication Patterns[C]//Proc. of the 1st IEEE and IFIP International Conference in Central Asia on Internet. [S. l.]: IEEE Press, 2005. [5] Perkins C E, Royer E M. Ad hoc On-demand Distance Vector
Routing[C]//Proc. of the 2nd IEEE Workshops on Mobile Computing Systems and Applications. [S. l.]: IEEE Press, 1999. [6] Li Jie, Pan Yi, Yang Xiao. Performance Study of Multiple Route
Dynamic Source Routing Protocols for Mobile Ad hoc Networks[J]. Journal of Parallel and Distributed Computing, 2005, 65(2): 169-177.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
（上接第93页）
参考文献
[1] 王 林, 戴冠中. 基于复杂网络社区结构的论坛热点主题发
现[J]. 计算机工程, 2008, 34(11): 214-216.
[2] Wu Fang, Huberman B A. Finding Communities in Linear Time: A
Physics Approach[J]. The European Physics Journal B, 2004, 38(2): 331-338.
[3] Newman M E J, Girvan M. Finding and Evaluating Community
Structure in Networks[EB/OL]. (2006-10-23). http://link.aps.org/ abstract/PRE/v69/e026113.
[4] 岳 训, 迟忠先, 莫宏伟, 等. 基于网络社区模块结构的特征
选择性能评价[J]. 计算机工程, 2007, 33(12): 16-18.
[5] Cohen W W. Enron Email Dataset[EB/OL]. (2005-04-04). http://
www.cs.cmu.edu/%7Eenron/.
[6] Sago Networks Data Center. The Prefuse Visual Toolkit[EB/OL].
(2007-08-23). http://prefuse.org/.
[7] Girvan M, Newman M E J. Community Structure in Social and
Biological Networks[J]. PNAS, 2002, 99(12): 7821-7826.
[8] Bagrow J P, Bollt E M. A Local Method for Detecting
Communities[EB/OL]. (2007-06-25). http://link.aps.org/abstract/ PRE/v72/e046108.
[9] Duch J, Arenas A. Community Detection in Complex Networks
Using Extremal Optimization[EB/OL]. (2007-11-25). http://link.aps. org/abstract/PRE/v72/e027104.下载本文
