第33卷第6期2013年12月南京邮电大学学报（自然科学版）
Journal of Nanjing University of Posts and Telecommunications （Natural Science ）Vol．33No．6Dec．2013
基于虚拟力牵引的社团划分算法
顾亦然，戴晓罡
(南京邮电大学自动化学院，江苏南京210023)
摘要：文中基于虚拟引力的思想，提出了一种新的社团划分算法。其基本思想是将相连节点之间看作是引力，不
相连节点看作是斥力，让节点之间进行相互作用，直到节点以社团的形式聚集起来，从而达到划分社团的目的。通过在计算机生成网络和已知社团结构的现实网络中对本算法进行仿真，发现算法具有较高可靠性和接近线性的时间复杂度。
关键词：复杂网络；社团结构；虚拟力中图分类号：TP391. 7
文献标志码：A
5439（2013）06-0106-06文章编号：1673-
Community Partitioning Algorithm Based on Virtual Force
GU Yi-ran ，DAI Xiao-gang
Nanjing University of Posts and Telecommunications ，Nanjing 210023，China )(College of Automation ，
Abstract ：Investigating the inner community structure is supposed to be one of the best approaches to study an unknown complex network．Based on the object oriented methodology ，here we propose a novel in which the relation between the adjacent vertices is considered as at-community partitioning algorithm ，
traction while the relation between the non-adjacent vertices is repulsion．The community structure is formed by the self-organization of vertices which are influenced by the virtual force of their neighbors．This algorithm is based on a new network structure and its operation efficiency is significantly improved．The reliability of this algorithm is tested by applying it in a computer-generated network and a real-world net-work with known structure．Finally ，an improvement of the algorithm is also discussed ，with the purpose to enhance the efficiency and accuracy of the algorithm．
Key words ：complex network ；community structure ；virtual force
0引言
关系（网页链接、人际交往、捕食关系等）。越来越多的学者倾向于使用复杂网络的观点来解释大规模
系统，相对于旧有方法而言，复杂网络能够帮助他们从整体上研究网络的结构与功能。
多数的现实网络都具有一个共同的特性：社团结构，即网络中的部分节点之间的联系十分紧密，组成类似群体的结构，但是群体之间的联系却十分稀疏。社交网络中的社团结构可以用来表示
近年来，复杂网络成为了越来越多学者关注的研究领域。现实世界的许多系统都可以用复杂网络
［2］［3］
、万维网、社交网络、引用
［4］［5］
网络和食物链。这些网络都是由一系列的节
如因特网来描述，
［1］
点和连边组成，节点通常代表网络中的实体（主机、
网页、个人等）。而连边通常表示实体之间的某种
07-19收稿日期：2013-：基金项目教育部人文社会科学研究规划基金（12YJAZH120）资助项目
mail ：dainternational@sina．com 通讯作者：顾亦然电话：[1**********]E-
第6期顾亦然等：基于虚拟力牵引的社团划分算法107
现实社会的结构；文献引用网络中的社团往往就是文献的主题；食物链中的社团结构通常就表示了物种的地缘分布。如果能够对许多未知的网络进行社团结构检测，无疑能够更进一步加深对网络的理解和研究。
Kernighan 和Lin ［6］就提出了一种早在1970年，贪婪算法，它是根据社团内部及社团间边最优化的
Fiedler ［7］提出了另原则对社团进行划分。1973年，
一种经典算法-谱平分法，谱平分法是基于Laplace
矩阵的性质而进行社团划分的方法。另外还有一系CNM 算列传统算法：凝聚（分裂）算法，如GN 算法、
法、快速Newman 算法和连边社团检测算法等。凝它们对于聚算法能够很好地发现社团的核心节点，
但特定的问题得到了很好的结果（特别是二分图），
［8］
在一般性的情况下表现不佳，而且对于边缘的节点会产生遗漏。早期算法运算时间复杂度大多在O
a 为与用户设置有关的常量，数，已经接近线性复杂度，远低于目前常用的社团划分算法，后者的复杂度
23
介于O （n ） O （n ）之间。本算法可以用于分析较大规模的网络。
1
1．1
算法介绍与复杂度分析
虚拟力
早在17世纪，牛顿就提出了著名的“万有引力”定律，成为了解开天体运行秘密的金钥匙。万有引力的定义为：宇宙中每个质点都以一种力吸引其他各个质点。这种力与各质点的质量的乘积成正比，与它们之间距离的平方成反比。仿照这个定义，
j 之间的“虚拟引力”F Gij 可以给出两个相连节点i ，
公式如下：
F Gij =G
d i d j d i d j 2
=G 22=Gd i d j c r 1/c
（1）
（m n ）到O （n ）之间，n 为网其中m 为网络的边数，
只能络中的节点数。受制于物理设备的运算能力，处理小规模的网络，对于大规模网络无法得到有效
的结果。
“物以类聚，，人以群分”具有某些共同点的人往往会处于相同社团之中，就好像人与人之间存将人们聚集到一起。由此想在看不见的“吸引力”到，可以通过节点之间相互作用的方法，将从属于同一个社团的节点聚集到一起，将没有关系的节点分隔开来，从而找出网络的社团结构。每一个节点受到来自邻居的引力和斥力，度小的节点易受到度大节点的吸引而聚集到度大节点周围，靠近但不相连的节点也会因为斥力而拉开距离。在不断的作用下，整个网络就会形成一个个的聚类，从而完成了社团的划分。演化完成后，整个网络形成了多个聚集在一起的组团，最后在一个具有良好社团结构的网络中，利用凝聚算法可以简单地完成社团的划分。
传统的凝聚（分裂）算法往往基于某种固定的
［9］［10］
社团评判因子，如模块度、边介数等，但这些评判因子具有其局限性，很难准确描述社团的特性。本文提出的算法究其根源属于凝聚算法一类，但与以往不同，该算法利用网络节点之间相互作用的关系，让节点在复杂的网络环境中“自主”选择社团。对于处于社团边缘的节点，节点能够根据受力的不同，自然地靠近具有较强吸引力的社团，解决了边缘节点难以划分的问题。
m 为网络的边本算法的复杂度仅为O （am ），
23
G 为引力常量，d i 和d j 分别为节点i ，j 的度，r 其中，
为节点之间的距离，由于这里表示逻辑上的而非现
采用节点亲密度c 的倒数来表示，亲密度实的距离，
越高，距离越小。节点亲密度c 的定义如下：
d i ∩d j c =（2）d i ∪d j
d i 和d j 分别为节点i ，j 的度，其中，节点亲密度c 就
j 的共同好友数占它们总好友数的比例，是节点i ，
c ∈［0，1］。即拥有的共同好友数越多，节点亲密度越高。
为了实现节点之间的受力平衡，避免所有节点
聚集到一起，在不相连的节点之间引入“虚拟斥，力”可以让接近但不相连的节点自动拉开距离。式（3）给出了虚拟斥力的公式。
F Ｒij=G Ｒ
d i d j r 2
（3）
G Ｒ为斥力常量，d i 和d j 分别为节点i ，j 的度，r 其中，
为节点之间的距离，此处的距离为二维映射平面上的实际坐标距离，距离越小，节点之间的斥力越大。在每个时间步的最后一个过程就是计算节点的合力向量，并根据此向量移动节点。节点的合力就是所有引力和斥力的向量和，式（4）给出了合力向量的计算公式。
F c =
∑F G +∑F Ｒ
（4）
节点之间的相互作用力如图1所示。
108南京邮电大学学报（自然科学版）2013年
以及合力；拟斥力”
Step3：计算运动向量，牵引未锁定节点；
Step4：判断节点是否到达稳定状态，到达则锁定节点；
Step5：所有节点均锁定则继续Step6，否则返回Step2；
Step6：寻找社团，建立新社团或将节点并入已有社团；
Step7：输出社团划分结果、绘制树状图，算法终止。
图2为算法的整体流程图。
图1
节点间的相互作用力示意图（实线为引力，虚线为斥力，点划线为合力）
开始
1．2算法描述
节点全部锁定？
本算法由两个主要环节组成：牵引演化和社团
划分。首先对网络进行初始化，完成二维映射，随后进行若干步的牵引演化，直到所有节点找到合适的位置。对于不断演化的节点，它每个时间步所受到的合力可能都不同，整个网络要达到完全的动态稳定是极为困难的。算法在每个演化时间步结束前会根据节点的轨迹判断节点是否进入动态稳定状态，锁定那些动态稳定的节点，直到完成整个网络的锁定。完成演化后就进入到最后的社团划分阶段，根据预设的网络分辨率寻找密集的区域，对节点进行逐个遍历，新建社团或并入已存在社团，最后输出社团划分结果。
算法具体的步骤如下所述：
Step1：初始化，在二维平面上随机分布网络节点；
Step2：遍历未锁定节点，“虚拟引力”、“虚计算
开始
N 计算虚拟力计算运动向量牵引移动节点
到达稳定状态？
N
Y 锁定节点
社团划分结束
图2算法的整体流程图
图3为社团划分阶段的算法流程图。
Y
遍历完成？
N
Y 度=1？
N
Y N ？
新建社团
加入相连社团
加入最近社团
N 新建社团
结束
图3社团划分阶段算法流程图
第6期顾亦然等：基于虚拟力牵引的社团划分算法109
1．3网络的二维映射
本算法的基本思想是在网络在虚拟力作用下的节点自组织。在演化开始之前，首先要对网络进行就是对每个节点赋予坐标二维坐标平面上的映射，
值。由于初始时并不知道网络的结构，最简单的方法就是随机分布，将所有节点均匀分布在二维平面
缺点是会使节上。这种方法的优点是简单易操作，
点分布杂乱无章，造成演化步骤大幅增加。在后面，
将提出一种方法对节点的二维映射加以改进，由此获得更加优化的结果。
牵引演化，节点自动地组织成了社团结构，社团内部
的连接十分紧密，而社团之间的联系则非常稀疏。算法在计算机生成网络中得到了很好的结果
。
1．4算法复杂度分析
图4
计算机生成网络图
本算法采用了计算机系统中广泛应用的索引式
结构来存储复杂网络，仅记录该当前节点的邻居，其余忽略。包含n 个节点和m 条边的网络，按照原有
2
的邻接矩阵结构，需要使用n 个存储单元来存放。而索引式网络仅仅存储网络中相连的边，而索引式结构仅需要m 个单元，因此遍历该网络的时间复杂度为O （m ），其中m 为网络中的连边数量。不仅大大节省了存储空间，还极大地提高了算法的效率。算法分为两个阶段：牵引演化和社团划分。其中牵引演化又可以细分为若干个相同的子过程，每个子过程由三部分组成：引力计算，时间复杂度为O （m ）；斥力计算，时间复杂度为O （m ）；节点牵引，时间复杂度为O （n ）。由于n 远小于m ，每个子过程
因的时间复杂度为O （m ）+O （m ）+O （n ）=O （m ），a 与设定的社团分辨为算法结束需经过约次演化，
率成正比。该阶段的时间复杂度为O （am ）。对于社团划分阶段，其时间复杂度仅为O （n ），几乎可以忽略。整个算法的时间复杂度为O （am ），已经接近线性复杂度。尤其是在稀疏网络的情况下，效率明
2［9］
显高于时间复杂度为O （n ）的CNM 算法。
图5社团划分结果图
2．2Zachary 的空手道俱乐部
尽管通过计算机生成网络可以得到大量的测试案在现实世界网络的数据中测试本算法也是必要的。例，
这样，我们选择了众所周知的Zachary 空手道俱乐部网
［11］
络。Zachary 在两年的时间内观察了空手道俱乐部中的34位成员。在研究过程中，俱乐部的老板和教练产生了不和，最终导致了教练的离职并建立了新的俱乐部，他带走了原来俱乐部半数的成员。
我们在Zachary 网络上采用本算法进行社团划分，图6为在Zachary 网络进行社团划分的最终结构图，图7为社团划分的结果树状图
。
2仿真测试和结果分析
本节将给出算法在计算机生成网络和已知社团
结构的现实世界网络上的部分测试案例。在这些案例中，本算法均能可靠地发现社团结构。
2．1计算机生成网络
为了测试算法的性能，我们利用计算机生成大量的虚拟案例来进行测试，计算机生成网络类似于825条边。图4中的网络。该网络包括240个节点，利用虚拟力牵引算法对计算机生成网络进行社团划分，结果如图5所示。可以明显看出经过若干步的
图6Zachary 网络社团划分结构图
110南京邮电大学学报（
2
3
4
5
自然科学版）
6
7
2013年
[***********][***********][**************]32
图7Zachary 网络社团划分树状图
Lin 算法［6］作为Za-研究者们往往将Kernighan-chary 网络的标准算法，为了进行比较，我们也同时实Lin 算法的划分结果现了该算法，图8为Kernighan-图。从图8中可以看到网络最终划分为两大社团，分2，3｝和｛33，34｝两个强连同核为中心。从整别以｛1，
KL 算法得出的两个社团的模块度分别为8体上看，
和11，而虚拟力算法结果社团的度分别为8和9，虚
拟力算法得到的社团更为紧凑。仔细比较二者结果10，13，25，28，32｝上存在分可以发现算法在节点｛9，
13｝的度仅歧。根据具体的网络信息分析，节点｛10，为2，它们与两个社团的核心节点均有联系，无法确
25，28，32｝的度虽然大于2，切划分；节点｛9，但与两个无明显偏向。除此之外强联通核的联系强度也相近，
本算法的结果与KL 算法高度吻合。Bagrow 和Bollt ［12］也曾指出，Zachary 网络在不同的社会条件下，的分裂存在多种可能性。可以说，在一定的误差范围内，本算法具有较高的可靠性
。
本算法的结果进行横向比较。包括前述的Ker-［9］
nighan-Lin 算法［6］、基于模块度的CNM 算法和基
于相似度的连边社团检测算法
［13］
。分别从结果的
模块度、正确率和算法复杂度几个方面进社团数量、
行比较。表1给出了四种算法的比较结果。其中模用来衡块度是2004年由Newman 和Girvan 提出的，量网络社团划分的质量
［10］
。虽然后来Fortunato 和
Barthelemy ［14］发现模块度具有一定的局限性，但在它仍被多数研究者作为评价算法正确性的重要
参考。
表1
比较算法KL 算法CNM 算法虚拟力算法连边社团检测
四种算法的比较结果
时间复杂度O （n 3）O （n log 2n ）O （am ）O （an 2）
社团数量模块度正确率
20．330288%
332
0．42110．64190．4211
82%88%79%
通过比较可以看出，虚拟力算法得出的结果拥
算法的运行时间却大有和KL 算法相当的正确率，
大缩短。虽然在速度上还是比不上接近线性复杂度
的CNM 算法，但较高的正确率弥补了这一点。同时虚拟力算法还拥有同连边社团检测算法一样的检测不同规模社团的能力。可以说本算法在实际应用中拥有广泛的前景。
3
图8
Kernighan-Lin 算法结果图
算法改进
树状二维映射
如前所述，我们在将网络映射到二维坐标平面
3．1
我们同时实现了几种不同类型的算法，在此与
第6期顾亦然等：基于虚拟力牵引的社团划分算法111
上采用的是随机映射，虽然这样做较为简便，但为后续处理带来了障碍。在极端情况下，节点的分布极为散乱，节点所受的合力也极不稳定，使得虚拟力牵引要花费较长时间。改进的方法是在映射之前对网络进行树状化，粗略的地找出处于网络“中心”的节
作为根节点，其余节点依照树状结构分层向外铺点，
开。这样生成的映射图在演化开始之前就拥有较好的结构，可以为后续的牵引节约大量的时间。
［2］JEONG H ，TOMBOＲB ，ALBEＲTＲ，et al．The large-scale organiza-tion of metabolic networks ［J ］．Nature ，2000，407：651－654．［3］WASSEＲMANS．Social network analysis ：Methods and applications
［M ］．Cambridge ：Cambridge University Press ，1994．
［4］ＲEDNEＲS．How popular is your paper ？An empirical study of the
．The European Physical Journal B ：Con-citation distribution ［J ］
densed Matter and Complex Systems ，1998，4：131－134．
［5］DUNNE J A ，WILLIAMS ＲJ ，MAＲTINEZN D．Network structure
and biodiversity loss in food webs ：Ｒobustnessincreases with con-nectance ［J ］．Ecology Letters ，2002，5：558－567．
［6］KEＲNIGHANB ，LIN S．An eflicient heuristic procedure for partitio-ning graphs ［J ］．Bell System Technical Journal ，1970，49：291－307．
［7］FIEDLEＲM．Algebraic connectivity of graphs ［J ］．Czechoslovak
Mathematical Journal ，1973，23：298－305．
［8］NEWMAN M E J．Detecting community structure in networks ［J ］．
The European Physical Journal B ：Condensed Matter and Complex Systems ，2004，38：321－330．
［9］CLAUSET A ，NEWMAN M E J ，MOOＲEC．Finding community
structure in very large networks ［J ］．Physical ＲeviewE ，2004，70：066111．
［10］NEWMAN M E J ，GIＲVANM．Finding and evaluating community
structure in networks ［J ］．Physical ＲeviewE ，2004，69：026113．［11］ZACHAＲYW W．An information flow model for conflict and fis-sion in small groups ［J ］．Journal of Anthropological Ｒesearch，1977，33：452－473．
［12］BAGＲOWJ P ，BOLLT E M．Local method for detecting communi-ties ［J ］．Physical ＲeviewE ，2005，72：046108．
［13］YONG-YEOL A ，BAGＲOWJ P ，LEHMANN S．Link communities
2010，466：reveal multiscale complexity in networks ［J ］．Nature ，761－764．
［14］FOＲTUNATOS ，BAＲTH LEMY M．Ｒesolutionlimit in community
detection ［J ］．Proceedings of the National Academy of Sciences ，2007，104：36－41．
3．2合力向量的改进
在演化过程中，还会出现一种极端情况，度极大的节点对度极小的节点形成很大的引力，使得小节“过头”，点被牵引即小节点在大节点周围大幅度跳动。我们对计算得出合力向量进行一个后期处理，根据两节点所处的相对距离对合力向量进行缩放。如果两点间距离较远则合力加倍，如果较近则合力减弱。这样距离较远的两节点会加速靠近，而距离较近的节点则保持稳定距离。经过这样的改进，整个网络的稳定性大幅提高，避免了原来“牵一发而动全身”的情况。
4结束语
本文引入了节点之间“虚拟力”的思想，假设每
“引力”，和“斥力”首先将个节点都受到相邻节点的
整张网络映射在二维平面上，让节点在各自的合力，实现自组织，最终形成合理的作用下自由“拖拽”
网络社团结构。本算法在包含n 个节点和m 条边
的网络中的时间复杂度为O （am ），接近于线性复杂度，使得算法可以应用于规模较大的网络，并能得到合理的结果。将算法应用于计算机生成网络和现实世界的Zachary 网络，并将结果与经典算法进行比较，发现本算法的正确率与KL 算法相当，而在社团模块度上要高于多数算法。
下一步，我们考虑将算法一般化，使其可以适用于有向网络和加权网络。参考文献：
［1］FALOUTSOS M ，FALOUTSOS P ，FALOUTSOS C．On power-law re-lationships of the internet topology ［C ］∥ACM SIGCOMM Computer Communication Ｒeview．1999．
作者简介
：
顾亦然（1972－），女，江苏金坛人。南京邮电大学自动化学院教授，博士。主要研究方向为复杂网络理论与应用、嵌入式系统、通信网络等。
戴晓罡（1989－），男，江苏淮安人。南京邮电大学自动化学院硕士研究生。主要研究方向为复杂网络、嵌入式系统。