—92—
大型复杂网络中的社区结构发现算法
胡 健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@https://www.doczj.com/doc/2710470892.html,
—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 589人。参照其他邮件数据集预处理的经验，对整个网络进行限制，规定只留下满足如下条件的人员：(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). https://www.doczj.com/doc/2710470892.html,/ abstract/PRE/v69/e026113.
[4] 岳 训, 迟忠先, 莫宏伟, 等. 基于网络社区模块结构的特征
选择性能评价[J]. 计算机工程, 2007, 33(12): 16-18.
[5] Cohen W W. Enron Email Dataset[EB/OL]. (2005-04-04). http://
https://www.doczj.com/doc/2710470892.html,/%7Eenron/.
[6] Sago Networks Data Center. The Prefuse Visual Toolkit[EB/OL].
(2007-08-23). https://www.doczj.com/doc/2710470892.html,/.
[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). https://www.doczj.com/doc/2710470892.html,/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.
—92— 大型复杂网络中的社区结构发现算法 胡 健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@https://www.doczj.com/doc/2710470892.html,
技术与市场 第16卷第12期2009年 1.引言 目前，国内对虚拟论坛的社区结构有一定的研究，张瑜通过实证分析证实了公社社会类型、科层社会类型和广场社会类型这三种类型的交往场域在BBS网络空间中的存在性，并分析了各类交往场域的特点,探讨了不同类型交往场域的形成机制。宫辉和徐渝利用社会网络矩阵分析法对网络虚拟社区中信息传播模式进行分析，概括出网络虚拟社区群体的基本特征。余兰则对大学生在BBS交往中的网络角色进行了研究。彭小川和毛晓丹运用社群图和矩阵法对网络社会群体进行了分析，概括出BBS群体的基本特征，并对群体中成员地位的形成、意见领袖的特点和群体内部人际交往的特征进行了探讨。王海明和韩瑞霞则在2004年发表了对国内BBS研究现状的述评文章。 从目前国内研究的情况看来，许多的研究已经开始使用社会网络的方法对论坛数据进行分析。尽管国内外学者作了大量研究，但是大部分都是从传播学、社会学以及心理学的某一角度进行研究，分析手段的限制使得大部分研究仍停留在定性阶段，所得到的结论说服力不强。因此，我们将采用复杂网络的方法，通过对蓝色星空数据进行研究和分析，包括两个阶段：1)建立复杂网络模型；2)对该模型进行分析，找出该网络的基本统计数据，包括度分布、聚集系数和平均路径长度等。 2.复杂网络 2.1网络定义 网络已成为各学科领域重要的分析工具和研究手段。网络是由许多节点与连接节点的边组成，其中节点代表系统中不同的个体，边则表示个体间的关系；两个节点之间具有特定的关系则连一条边，有边相连的两个节点被看作是相邻的。比如计算机网络可以看作是自主工作的计算机通过各种物理介质与通信协议相互连接得到的网络。 2.2复杂网络 网络模型包括规则网络、随机网络和复杂网络。随机网络首先由Erdos和Rényi引入，是概率方法与传统图论相结合的网络，着重于网络的随机性。而科学家们发现大量的真实系统的网络模型既不是随机网络，也不是规则网络，却是介于随机网络和规则网络之间的复杂网络。1998年Watts和Strogatz表明大量真实网络都具有小世界效应；1999年Barabasi和Albert指出许多现实世界中的大量网络具有无标度网络(scale-free)的特性—— —无尺度特征、脆弱性和抗毁性。无尺度特性刻画了复杂网络的不均匀复杂性，即大部分结点只有少数连接，少数结点拥有大量连接。脆弱性与抗毁性并存从另一方面反映无尺度特性。Albert等人的研究表明，无标度网络比随机网络具有更强的抗毁性，但是对于选择性攻击抗攻击能力较差，5%的核心结点被攻击，网络就基本瘫痪。 复杂网络的研究可以简单概括为三方面密切相关却又依次深入的内容：通过实证方法度量网络的统计性质；构建相应的网络模型来理解这些统计性质何以如此；在已知网络结构特征及其形成规则的基础上，预测网络系统的行为。 2.3复杂网络的主要统计参数 2.3.1度和度的分布 一个节点与其它节点相连的边数称为该节点的度,度是描述网络局部特性的基本参数。节点度分布是指网络中度为k的节点的概率p(k)随节点度k的变化规律。节点度的分布函数反映了网络系统的宏观统计特征,理论上利用度的分布可以计算出其它表征全局特征参数的量化行为。 2.3.2平均路径长度 网络中两个节点i和j之间的距离dij定义为连接这两个节点的最短路径上的边数。网络中任意两个节点之间的距离的最大值称为网络的直径，记为D，即 D=max i,j d ij 网络的平均路径长度L定义为任意两个节点之间的距离的平均值，即 L=1 1 2 N(N-1) ∑i≥j d ij其中，N为网络节点数。 2.3.3聚集系数C 在有N个节点的网络中,若第i个节点的度为k i ,由这k i个邻 基于复杂网络的社团结构分析 —— —以四川大学蓝色星空为例 陈志翔 四川大学计算机学院成都610041 摘要：随着我国计算机和网络的普及，网络社团、尤其是BBS，在人们日常生活中发挥着巨大的作用，国内目前对BBS 的社团结构进行定量分析的研究不多。本文通过对基于四川大学蓝色星空ID间相互回帖关系所构建的复杂网络模型的 研究，构造仿真实验，找出该网络的基本统计数据。 关键词：复杂网络社团结构BBS网络建模 doi:10.3969/j.issn.1006-8554.2009.12.029 专题研究 41
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用２０１０，４６（９）５１ 基于信号传递与层次聚类的社团发现算法 黄浩英，马英红 ＨＵＡＮＧＨａｏ－ｙｉｎｇ，ＭＡＹｉｎｇ－ｈｏｎｇ 山东师范大学管理与经济学院，济南２５００１４ ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ＆Ｅｃｏｎｏｍｙ，ＳｈａｎｄｏｎｇＮｏｒｍａｌＵｌｌｉｖｅ玛ｉｔｙ，Ｊｉｎａｎ２５００１４，Ｃｈｉｎａ Ｅ—ｍａｉｌ：ｈｕａｎｇｈａｏｙｉｎ９２０００＠１２６．ｃｏｍ ＨＵＡＮＧＨａｏ－ｙｉｎｇ。ＭＡＹｉｎｇ－ｈｏｎｇ．ＤｅｔｅｃｔｉｎｇｃｏｍｍｕｎｉｔｙａｌｇｏｒｔｔｌｕｎｂａｓｅｄＯｎａｇｕａｌｐｒｏｃｅｓｓａｎｄｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｔｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ．２０１０。４６（９）：５１－５４． Ａｂｓｔｒａｃｔ：Ｃｏｍｍｕｎｉｔｙｉｓｏｎｅｏｆｉｍｐｏｒｔａｎｔｃｈａｒａｃｔｅｒｓｉｎｓｏｃｉａｌｎｅｔｗｏｒｋｓａｎｄｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｎｇｉｓａｌｓｏａｆａｓｈｉｏｎａｂｌｅｓｔａｔｅｍｅｎｔｒｅｃｅｎｔｌｙ．Ｉｎｔｈｉｓｐａｐｅｒ，ｂａｓｅｄｏｎｓｉｇｎａｌｉｎｇｐｒｏｃｅｓｓｏｎｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ，ｉｎｆｌｕｅｎｃｅｖｅｃｔｏｒｓｏｆｅａｃｈｎｏｄｅａｔｅｇｏｔ，ｔｏｐｏｌｏｇｉｃａｌＳｔｌｔｌｌＣ－－ｔｕｒｅｏｆｅａｃｈｎｏｄｅｉｓｔｒａｎｓｌａｔｅｄｉｎｔｏｇｅｏｍｅｔｒｉｃａｌｒｅｌａｔｉｏｎｓｈｉｐｓｏｆｖｅｃｔｏｒ８ｉｎａｌｇｅｂｒａｓｐａｃｅｓ．ａｎｄｂｙｔｈｅａｉｄｏｆｈｉｅｒａｒｃｈｉｃａｌｃｈ吼ｅ卜ｉｎｇｍｏｄｕｌａｒｉｔｙｈｉｅｔｌＩｏｄ，ｃｏｍｍｕｎｉｔｉｅｓａｒｅｄｅｔｅｃｔｅｄｅｆｆｅｃｔｉｖｅｌｙ．ＷｉｔｈｄａｔａｓｉｍｕｌａｔｉｏｎｓｏｎｔｈｅＺａｃｈａｒｙＫａｒａｔｅＣｌｕｂｎｅｔｗｏｒｋ，ＣｏＨｅｇｅＦｏｏｔｂａｌｌｎｅｔｗｏｒｋａｎｄＤｏｌｐｈｉｎｓｏｃｉａｌｎｅｔｗｏｒｋ，ｉｔｓｈｏｗｓｔｈａｔｔｈｅｐｒｏｐｏ窨ｅｄａｌｇｏｒｉｔｈｍｉｎｔｈｉｓｔｏｐｉｃｉｓｍｏｌｅａｃｃｕｒａｔｅｔｈａｎＮｅｗｍａｎ’８．Ｋｅｙｗｏｒｄｓ：ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ；ｓｉｇｎａｌｐｒｏｃｅｓｓ；ｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ；ｍｏｄｕｌａｒｉｔｙ 摘要：社团是社会网络的一个重要特征，社团发现是近年来研究的热点问题之一。通过在复杂网络上传递信号，获得各节点对网络的影响向量，从而把网络中节点的拓扑性质转化为代数空间上向量的几何关系，然后用结合模块度的层次聚类挖掘社会网络中的社团结构。该算法优点是不需要预先知道社团的数量或社团内节点的数量，用Ｚａｃｈａｒｙ空手道俱乐部网络、大学足球赛网络以及海豚关系网络的数据进行验证，该算法划分的社团准确性超过了Ｎｅｗｍａｎ的结论。 关键词：社团结构；信号传递；层次聚类；模块度 Ｉ）ＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２－８３３１．２０１０．０９．０１６文章编号：ｌ００２＿８３３ｌ（２０ｌＯ）０９－００５ｌ—０４文献标识码：Ａ中图分类号：Ｎ９４；ＴＰ３９３ １引言 复杂网络是复杂系统的抽象，网络中的节点代表复杂系统中的个体，节点之间的边则代表系统中个体之问某一种关系。现实世界中复杂网络无处不在，如人际关系网、科学家合作网络、万维网、食物链网络等等。大量的研究表明，许多实际网络都呈现具有社团的性质，即整个网络是由若干个社团构成，在每个社团内部节点之间的连接相对紧密，而在各个社团之间却相对稀疏１１１。例如，在以人为主体的社交网络模型中，网络中的连线是根据兴趣或某种关系而形成的，—个人连接线越多，则表示他拥有的关系越多、影响也越大，并且可以控制的资源也越多，此时他与所连接的人就构成了—个社团。在科学引文网络中的社团代表针对同一主题的相关论文，而生物化学网络中的社团则代表具有相近功能的单元嘲，发现网络中的社团有助于更加有效地理解网络结构以及网络特性。 社团的研究中—个重要的课题是网络社团的划分，与此相关的理论包括图论以及模式识别等。社团的发现最早起源于社会学研究工作，较早的算法是在社会学研究中的分级聚类算法，它与计算机科学中的图形分割研究有着密切的关系嗍，其中分级聚类中最著名的是ＧＮ算ｉ去ｆｕ，Ｋｅｍｉｇｈａｒｔ—Ｌｉｎ算法哪谱平分嗣法是图形分割在处理社团划分中最具代表性的方法。此外，还有许多有效的算法如Ｒａｄｉｃｃｈｉ算法、极值优化算法、Ｎｅｗｍａｎ快速算法等Ｍ。在所有的社团的搜索算法中时间复杂度和查找的准确性是最为关键的两个问题。 基于上述问题，用在复杂网络传递信号的方法，得到网络中每个节点对网络的影响向量，通过每个节点的影响向量把网络的拓扑关系转换到ｎ维代数空问上，将ＧＮ算法中提出的模块度函数与层次聚类方法结合进行社团结构的探测，用Ｚａｃｈａｒｙ空手道俱乐部网络、大学足球赛网络以及海豚关系网络的数据进行验证，该算法划分的社团准确性超过了Ｎｅｗｍａｎ的结论研。该算法优点是不需要预先知道社团的数量或社团内节点的数量，算法较好地改善了运行时间，提高了社团搜索的准确率。 ２算法准备 ＨｕＹａｎｑｉｎｇ等人提出了在复杂网络中传递信号的方ｊ去Ｉ嘲，是将—个具有ｎ个节点的网络视为—个系统，系统中的每个节点被认为具有发送、接受和记录信号的功能。信号传递基本思 基金项目：国家自然科学基金（ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．６０６７３０４７）；山东省自然科学基金（ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＳｈａｎｄｏｎｇＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ）；山东省教育厅科技项目（ＮｏＪ０７ＹＪ０２）。 作者筒介：黄浩英（１９８３一）。女。研究生。主要研究方向：复杂网络与复杂系统；马英红（１９７１一），女，副教授，主要研究方向：复杂网络与复杂系统，图论，粗糙集应用等。 收稽日期：２００９一ｌｏ－１２修回日期：２０１０－０１－０８ 万方数据
复杂网络社区发现若干问题研究 近年来,复杂网络逐渐成为信息科学、社会学、物理学、乃至生命科学等学科研究的热点。所谓复杂网络,是指将自然界中的各个实体抽象为网络中的节点,实体与实体之间的关系抽象为网络中的边。 这使得自然界中的很多系统都可以表示为复杂网络的形式,例如社会关系网、科学家合作网、通信网、互联网、人类疾病基因网等等。研究发现,复杂网络具有复杂的内部结构和多样的结构特征,其中,模块性(即社区结构)是复杂网络的 一个重要特征,它表现出网络中的节点具有聚集化的特性,即社区内部节点之间 连接稠密、社区之间的节点连接稀疏。 此外,社区结构在现实世界中往往是“重叠”的。复杂网络(重叠)社区结构的发现对于分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律以及预测复杂网络的行为具有十分重要的意义。 目前,研究者提出了众多网络(重叠)社区发现方法,并将之成功应用于现实 系统的分析中,然而社区发现方法存在的问题还有很多,如复杂网络社区发现问 题与聚类分析问题两者之间的关系还有待研究；网络社区发现算法尤其是重叠社区发现算法的精度和效率还有待提高；传统的划分评价函数模块化Q函数存在分辨率的限制等等。鉴于复杂网络社区发现问题与传统机器学习中的聚类分析问题都是对数据进行划分,并且机器学习中的聚类分析研究日趋成熟,本文结合机器 学习相关的技术和方法,改进并提出了若干发现网络(重叠)社区的算法,主要贡 献如下：(1)揭示了社区发现问题和聚类分析问题之间的区别和联系,利用聚类分析中定义的相似度概念对GN (Girvan and Newman)算法进行改进,给出了快速的SGN (GN based on similarity)算法。
第８卷第１期 复杂系统与复杂性科学ｖ０１．８Ｎｏ．１２０１１年３月ＣＯＭ呻ＬＥＸＳＹＳＴＥＭＳＡＮＤＣＯＭＰＬＥＸＩＴＹＳＣＩＥＮＣＥＭａｒ．２０１１文章编号：１６７２—３８１３（２０１１）０１一００５７—１４ 复杂网络的社区结构 程学旗，沈华伟 （中国科学院计算技术研究所，北京１００１９０） 摘要：社区结构作为真实复杂网络所普遍具有的一个重要拓扑特性，在最近１０ 内得到了广泛而深入的研究。回顾了近几年国内外社区结构研究的主要进展， 点介绍社区发现的研究历程和研究成果，并结合社会计算的背景展望了社区结研究的未来发展方向和潜在的应用价值。 关键词：社区结构；社区发现；模块度；社会计算 中图分类号：Ｎ９４文献标识码：Ａ ＣｏｍｍｕｎｉｔｙＳｔｒｕｃｔｕｒｅｏｆＣｏｍｐｌｅｘＮｅｔｗｏｒｋｓ ＣＨＥＮＧＸｕｅ－ｑｉ，（ＩｎｓｔｉｔｕｔｅｏｆＣｏｍｐｕｔｉｎｇＴｅｃｈｎ０１０９ｙ，ＣｈｉｎｅｓｅＳＨＥＮＨｕａ—ｗｅｉ ＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅ巧ｉｎｇ１００１９０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｓａｃｏｍｍｏｎａｎｄｉｍｐｏｒｔａｎｔｔｏｐｏｌｏｇｉｃａｌｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｒｅａｌｗｏｒｌｄｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ， ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｈａｓｂｅｅｎｅｘｔｅｎｓｉＶｅｌｙｓｔｕｄｉｅｄｉｎｔｈｅｌａｓｔｄｅｃａｄｅ． Ｔｈｉｓｐａｐｅｒｒｅｖｉｅｗｓｔｈｅｍａｉｎｐｒｏｇｒｅｓｓｅｓｉｎｔｈｅｓｃｉｅｎｔｉｆｉｃｒｅｓｅａｒｃｈ ｏｎｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ．Ｅｓｐｅｃｉａｌｌｙ，ｔｈｉｓｐａｐｅｒｄｅｓｃｒｉｂｅｓｔｈｅｄｅＶｅｌｏｐｍｅｎｔａｔｔｈｅｄｅｔｅｃｔｉｏｎｏｆｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅｆｒｏｍｖａｒｉｏｕｓｄｉｓｃｉｐｌｉｎｅｓ． Ｆｉｎａｌｌｙ，ｔｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｓｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎｓｏｆｔｈｅｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅａｎｄｔｈｅｐｏｔｅｎｔｉａｌａｐｐｌｉｃａｔｉｏｎｓ ｉｎｓｏｃｉａＩｃｏｍｐｕｔｉｎｇ．Ｋｅｙｗｏｒｄｓ：ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ；ｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｏｎ；ｍｏｄｕｌａｒｉｔｙ；ｓｏｃｉａｌｃｏｍｐｕｔｉｎｇ ０引言 真实世界中的许多复杂系统可以表示成图或网络，包括社会网络、信息网络、生物网络和技术网络等［１剖。经验分析表明，这些复杂网络可以自然地分成一些节点组，使同一个节点组内的两个节点之间比不同节点组的两个节点之间更倾向于有边相连，网络的这种拓扑特性被称为社区结构，相应地，每个节点组被称为一个社区‘６’。 社区结构刻画了网络中连边关系的局部聚集特性，也体现了网络中连边的分布不均匀性。进一步，网络中的社区通常由功能相近或性质相似的网络节点组成，因此，社区被认为有助于揭示网络结构和功能之间的关系。卜引。以万维网（ＷｏｒｌｄｗｉｄｅＷｅｂ）为例，通过超链接紧密关联的网页形成一个个的社区，同一个社区的网页具有相近的话题［３刮。社区结构的示例如图１所示。 收稿日期：２０１０一】Ｏ一２９ 墓金项目：国家自然科学基金（６０８７３２４５，６０９３３００５） 作者简介：程学旗（１９７ｌ一），男，研究员，博导，主要研究方向为网络科学、海量信息检索和数据挖掘、社会计算、分布式计算和网络模拟仿真。 年重构
复杂网络社区结构划分方法 已有 3661 次阅读2009-4-30 08:38|个人分类:科研笔记|系统分类:科研笔记|关键词:网络，系统，复杂网络，社区结构，聚类，划分方法 随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个“社区”或“组”构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏[1][2]。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站[3]；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元[4][5]。发现这些网络中的社区有助于我们更加有效的理解和开发这些网络。 在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如K-L算法[6]、谱平分法[7][8]、随机游走算法[9]和派系过滤算法[10][11]等；第二类是层次聚类算法，比如基于相似度度量
的凝聚算法[2]和基于边介数度量的分裂算法[1][12][13]等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下：基于电阻网络性质的算法[14]、基于信息论的算法[15]、基于PCA的算法[16]和最大化模块度[17]的算法[18-23]等。对于符号网络，Doreian和Mrvar提出了一种利用局部搜索划分符号网络社区结构的算法[24]，且Bo Yang等提出一种基于代理的启发式划分符号网络社区结构的算法(FEC)[25]。 尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努力。 关于复杂网络社区发现问题更加系统深入的最新进展情况请看2009长篇综述文章Community Detection in graphs by Santo Fortunato (arXiv:0906.0612) 参考文献 [1] Girvan M, Newman M E J. Community structure in social and biological networks[J]. PNAS, 2001, 99(12): 7821-7826. [2] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.
社团发现的算法 1.非重叠社团发现算法 1.1基于模块度优化的社团发现算法 （1）Newman M E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Phys Rev E, 2004, 69(6): 066133. （2）Clauset A. Finding Local Community Structure in Networks[J].Phys Rev E, 2005, 72(2): 026132 （3）SchuetzP,CaflischA.MultistepGreedyAlgorithmIdentifiesCommunity Structure in Real-world and Computer-generatedNetworks[J]. PhysRev E, 2008, 78(2): 026112. 1.2基于谱分析的社团发现算法 （1）Donetti L, Munoz M. Detecting Network Communities: A New Systematic and Efficient Algorithm[J]. Journal of Statistical Mechanics, 2004, P10012 （2）Capocci A, Servedio V D P, Caldarelli G, et al. Detecting Communities in Large Networks [J]. Physica A: Statistical Mechanics and Its Applications, 2005, 352(2-4): 669-676. 1.3 基于信息论的社团发现算法 （1）Rosvall M, Bergstrom C T. An Information-theoretic Framework for Resolving Community Structure in Complex Networks[J]. P Natl Acad Sci USA, 2007, 104(18): 7327-7331. 1.4 基于标号传播的社团发现算法 Raghavan UN, Albert R, Kumara S. NearLinearTime Algorithmto Detect CommunityStructures inLarge-scaleNetworks[J]. Phys RevE, 2007, 76(3): 036106. 1.5 迭代层次社团发现算法 一种新的复杂网络层次社团发现算法 2．重叠社团发现算法 2.1 基于团渗透改进的重叠社团发现算法 Palla G, Derenyi I, Farkas I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society [J]. Nature, 2005, 435(7043): 814-818. 2.2 基于模糊聚类的重叠社团发现算法 Zhang S, Wang R, Zhang X. Identification of Overlapping Community Structure in Complex Networks Using Fuzzy C-means Clustering [ J]. Physica A: Statistical Mechanics and its Applications, 2007, 374(1): 483-490. 2.3 基于非负矩阵分解的重叠社团发现算法 Zhang S, Wang R S, Zhang X S. Uncovering Fuzzy Community Structure in Complex Networks[J]. Phys Rev E, 2007, 76(4):046103. 2.4 基于种子扩展思想的重叠社团发现算法 Lancichinetti A, Fortunato S, Kertesz J. Detecting the Overlapping andHierarchical Community Structure in Complex Networks[J]. New Journal of Physics, 2009, 11:033015. 2.5 基于混合概率模型的重叠社团发现 NewmanME, Leicht EA. MixtureModels and ExploratoryAnalysis in Networks[J]. Proc Natl Acad Sci USA, 2007, 104(23): 9564-9569. 2.6 基于边聚类的重叠社团发现 （1）EvansT,Lambiotte R.Line Graphs,LinkPartitions, and Overlapping Communities[J]. Physical Review E, 2009, 80(1): 16105. （2）Ahn Y Y, Bagrow J P, Lehmann S. Link Communities Reveal Multiscale Complexity in Networks[J]. Nature, 2010, 466: 761-764. CNM算法