基于引力作用的可选粒度社区发现算法

董宇欣，迟阔，印桂生

（哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001）

基于引力作用的可选粒度社区发现算法

董宇欣，迟阔，印桂生

（哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001）

社区发现是复杂网络研究中的一个重要领域，且应用广泛，但目前已有的大多数算法都需采用社区评判函数来确定社区结构的划分，且仅能得到一种划分结果。引入宇宙星系模型和万有引力定律，基于引力思想提出一种新的复杂网络社区发现算法，为网络中节点赋予质量并构建出社区框架，继而利用引力作用完成社区结构划分，并可对发现社区的粒度大小进行选择以得到多种划分结果，无需先验知识及相关参数。通过真实网络实验验证，并与现有的社区发现算法比较，本文提出的算法能有效且较为准确地挖掘出复杂网络中的社区结构。

复杂网络；可选粒度；社区发现；引力作用

复杂网络广泛存在于现实世界中［1］，随着互联网的发展，大规模在线社交网络的出现也使得网络结构更加趋于复杂，社区发现也变得尤为重要。社区作为网络中一些具有某种相同属性的节点组合，能够更加方便、快速且准确地寻找具有相同属性的节点，使得复杂网络更加易于分析，且社区结构在信任机制，网络影响力传播，寻找恶意节点联盟等方面也起着十分重要的作用［2］。因此如何准确和快速地在复杂网络中发现并挖掘出社区结构，深入研究社区结构的演化过程对复杂网络的研究和发展具有重要的推动作用。

复杂网络的社区发现问题到目前主要有两类划分方法：一类基于层次聚类，利用树图来划分社区；另一类基于中心聚类思想，通过聚类范围的扩大来实现社区的扩充。Newman等最初提出了GN算法［1］，通过计算网络中每条边的边介数，不断地移除边介数最大的边来达到划分社区结构的目的，算法执行后可以得到多种社区粒度不同的划分结果，但无法确定最优的社区结构，且算法的时间复杂度过高，不适合大规模的复杂网络。为了解决最优社区结构划分的问题，Newman等又提出了网络模块度函数来作为社区划分评判函数［3］，后来很多模块度优化算法和优化策略被引入［4⁃7］，许多类似的社区评判函数也被提出［8⁃9］。此外还有很多不需要利用社区评判函数来帮助进行社区发现的算法也被提出，这些算法大部分基于中心聚类思想［10⁃11］。这些算法不需要社区评判函数来辅助进行社区发现，而是通过寻找网络社区的核心进而完成社区结构的划分。虽然上述算法一定程度上可以挖掘出网络中的社区结构，且可适合应用于大型网络，但往往仅能得到一种划分结果，而在社区研究中可能需要对同一网络下不同粒度的社区进行分析。

基于宇宙星系模型及万有引力思想，本文提出了一种基于节点间引力作用的可选粒度的复杂网络社区发现方法，将引力作用引入复杂网络，通过为网络中的节点赋予质量，引力搜索节点最终划分出网络的社区结构，并可调整所得社区的粒度大小。最后利用真实网络对算法的准确性进行验证。

1 宇宙星系模型的引入

在本节中，将宇宙星系模型引入到复杂网络中，将网络中的每一个节点映射为宇宙中的星体，为每个节点赋予相应的质量，仿照宇宙中星系结构的形成，通过节点间引力的相互作用聚类来划分社区结构。

给定复杂网络的无权无向图NG＝（V，E），网络中的节点个数为N，边条数为M、V是节点集合，E是边集合。此外也可以用N×N的邻接矩阵A＝［aij］N×N来表示网络图，其中，对于任意vi，vj∈V，若存在eij∈E则aij＝1，否则aij＝0。节点vi的度，是节点vi与其他节点直接相连的边数目的总和。假设网络中存在节点集合的集合｛C1，C2，…，Cn｝，1≤n≤N，对任意i，j∈｛1，2，…，n｝，当满足下列条件时：①Ci∈V；②Ci≠φ；.每个节点集合称为NG的一个社区。

宇宙由数以亿计的星体所组成，部分星体与临近星体之间由于万有引力的作用而相互运动，最终形成星系系统。相类似地，复杂网络由大量彼此间相互联系的网络节点组成，社区可看成是由若干彼此间联系更为紧密的网络节点所组成的局部团体。本文将宇宙星系模型引入到复杂网络中来模拟网络结构并尝试通过节点间相互吸引来实现社区结构的划分，因此需要为网络中的每个节点赋予质量。本文用图NG来描述网络，一个节点的度表示该节点与周围节点的联系密集程度，一个节点的度越大，表示该节点与周围较多节点彼此之间相互联系，也能从一定程度上反映该节点在社区中的重要性，因此本文选用节点度的大小作为其质量大小。

在复杂网络中引入宇宙模型后，接下来通过引力作用来划分社区结构。这里引入万有引力计算公式：

式中：fij表示个体vi与vj之间的引力；G为引力常量，由于本文的研究对象均为同构网络，因此将其设定为1；mi表示个体vi的质量；Rij表示网络中节点vi与节点vj的拓扑距离，为了简化计算，这里认为只有直接相连的节点间存在引力作用，因此式（1）可修改为

2 基于引力搜索的可选粒度社区发现

本文通过下列步骤来挖掘网络中的社区：首先找到作为社区核心的Star节点，进而聚类其周围Planet节点构建社区框架，最后通过引力作用搜索剩余的节点完成社区结构的划分。

2.1 构建社区框架

社区框架可看作由Star节点和Planet节点组成。宇宙的一个星系中，恒星的数量可能是多个，因此假定网络中的社区核心也不仅仅局限于一个。考虑到网络中的部分节点因与其相联系的节点数目较多而具有较大的中心性，部分节点因与其联系的节点更紧密而具有较大的中心性，本文中社区核心节点选取具有上述2种中心性的节点集合。依据上文为每个节点定义的质量，从全局的角度选取具有局部极大T值和局部极大M值的节点的并集作为网络的Star节点集合。如图1所示。

图1 一个网络中的Star节点Fig.1 The Star nodes in a network

在给定的网络NG中，节点vi的T值定义为节点vi与其邻居节点所形成的的三角形个数与其度大小的比值，可以反映该节点在与周围节点联系规模条件下的联系紧密程度。局部极大T值节点定义为：存在节点vi，i∈｛1，2，…，N｝，对任意满足eij＝1的节点vj，都有T（vi）≥T（vj）。

节点vi的M值定义为节点vi的质量，大小等于节点度的大小。局部极大M值节点定义为：存在节点vi，i∈｛1，2，…，N｝，对任意满足eij＝1的节点vj，都有M（vi）≥M（vj）。

接下来要对Star节点集合进行划分来完成社区的初始化。这里有2种划分策略：

1）将所有相连的Star节点划入到同一个社区中，不相连的Star节点则认为其分属于不同的社区结构，这样最终得到的社区是粗粒度的；

2）在上一种划分策略基础上，再对每个社区的Star节点进一步细分，以每个具有局部极大M值的节点为细化中心，将与其相连的局部极大T值节点划入同一个社区，同时连接到多个局部极大M值节点的局部极大T值节点划分到收到引力大小最大的细化社区中，这样最终得到的社区结构是细粒度的。此外，还可以仅对部分粗粒度的社区结构进行细化，一些不需要进一步细化研究的粗粒度社区继续保留，这样就可以得到多种不同的中间粒度的社区初始化结果。

接下来通过聚类的方法构建社区框架：将与Star节点相连的节点纳入社区中，并称这些节点为Planet。此时可能会有一个Planet节点同时与多个社区相连的情况，本文根据社区对其引力作用的大小将其划入对其引力更大的社区中。

社区C对节点vi的引力F值定义为

式中：Fin（vi，C）表示节点vi与社区C中节点引力大小之和，即

式中：Fout（vi，C）表示节点vi与社区C外节点引力大小之和，即

对于同时与社区Ci与社区Cj相连的Planet节点，当F（vi，C）＞0时，说明了社区Ci中的节点对节点vi的引力作用大于社区Cj中的节点，就将节点vi划入社区Ci。反之，将其划入社区Cj。

2.2 引力搜索完成社区划分

此时，网络中仍然有一些节点没有被划分进入社区，本文利用各社区的引力关系大小搜索这些节点。同样利用F值作为这些节点划入相应社区的依据，当F（vi，Ci）＞0时，说明了社区Ci中的节点对节点vi的引力作用大于社区Ci外的节点，则将节点vi划入社区Ci中。

2.3 算法步骤

算法 基于引力作用的可选粒度社区发现算法（optional granularity community detection algorithm based on gravitation）

输入：网络图NG＝（V，E）输出：NG的最终社区划分1）计算网络中各节点的度，并以此作为节点的质量；由式（2）来构建全网络的引力矩阵。

2）计算每个节点的T值大小，将具有局部极大T值的节点和具有局部极大M值的节点选取出来，作为整个网络的Star节点集合。

3）将Star节点集合中相连的Star节点初始化进入同一个社区，不相连的则初始化进入不同的社区，初始化后得到各个社区的Star节点集合。若最终社区划分结果想获得粗粒度社区结构，则跳转至5）；若最终社区划分结果想获得细粒度或中间粒度的社区结构则跳转至4）。

4）在各个社区的Star节点集合中，以其中具有极大M值的Star节点为中心，将与其相连的Star节点划分进同一个细化社区，若其中有极大T值节点同时连接多个极大M值节点，则将其划入对其引力大小更大的细化社区中。也可以仅对其中部分社区的Star节点进行上述处理，其余不做改变。

5）由各个社区的Star节点集合将与其相连的节点（Planet节点）聚类进入各个社区中。若有Planet节点同时受到多个社区的吸引，则根据式（4）将其划入对其引力值更大的社区。

6）利用社区对节点的引力作用的大小搜索剩余节点，将其划分进对其引力值更大的社区中，直到所有的节点都被划分进对其引力作用最大的社区中，完成社区结构的划分。

算法的整体时间复杂度约为O（N2）。

3 实验分析

本文选择3个数据集（空手道俱乐部社交网络、海豚社会网络、VAST通信网络）来验证该算法的有效性（见表1）。

表1 实验数据集Table 1 The experimental data set

实验所采用的对比算法是GN算法［1］，Fast算法和基于拓扑势的社区发现算法［10］。最后将各算法划分结果与真实网络划分结果进行对比。

3.1 空手道俱乐部社交网络

该网络是社会网络分析的常用经典数据集，整个网络被分成了2个社区。

在图2中，2个社区中都仅含有一个极大M值节点（节点1和节点34），因此均无法再细化。图2是根据局部极大T值和局部极大M值所选取的Star节点；图3是最终得到的社区划分结果。

GN算法在模块度Q函数取得最大值时划分得到了4个社区；Fast算法划分得到了2个社区，但有节点划分错误；基于拓扑势的社区发现算法结果也有2个节点被误分。表2是对这4种算法划分结果的准确率的对比。3.2 海豚社会网络

图2 空手道俱乐部社交网络—Star节点的选取Fig.2 Zachary's karate club—Star selected

图3 空手道俱乐部社交网络—最终社区划分结果Fig.3 Zachary's karate club—The final results

表2 各算法划分结果准确率的对比Table 2 The accuracy of the results compared

该网络也是社会网络分析的常用数据集，网络初始被分成了一大一小2个社区，但通过研究者的进一步观察，大的社区又进一步分裂成3个小社区。

图4和图5展示了本章所提出的算法划分海豚社会网络的最终社区划分结果。

本文所提的算法得到的粗粒度社区也为2个，同时右边社区可进一步细化为3个小的社区，与真实情形相一致，表3是对这4种算法划分结果的准确率的对比，这里仅列出细化后的社区划分结果。

图4 海豚社会网络-算法的最终社区划分结果（粗粒度社区）Fig.4 Dolphin social network—the final results（coars⁃ness）

图5 海豚社会网络-算法的最终社区划分结果（细粒度社区）Fig.5 Dolphin social network—the final results（fine⁃grit）

表3 各算法划分结果正确率的对比Table 3 The correct rate of the results compared

3.3 VAST通信网络

该数据集记录了400人在10 d中的通话情况，包含10个静态网络快照。表4给出了数据集中各个网络的基本信息，此数据集并未有确切的社区划分结果。

表4 VAST数据集各网络的信息Table 4 The information of VAST

表5展示了本章所提出的算法在粗粒度社区划分条件下对各网络社区的划分结果和与GN算法的对比情况，得到的粗粒度社区划分结果与GN算法大致相同，部分社区会划分可得到更细粒度，但对于研究意义不大，在此不再列出。

表5 各个网络的社区划分结果对比Table 5 Comparision of community division results

4 结论

本文提出了基于引力作用的可选粒度复杂网络社区发现算法。相比于目前现有的算法，本文所提出的算法具有如下优势：

1）算法本身无需任何先验知识和参数；

2）可根据需要划分出不同粒度的社区结构；

3）算法的时间复杂度较低，可应用于大规模的实际网络；

4）算法可以获得合理且较为准确的实验结果。

在下一步工作中，将尝试把算法引入到重叠社区划分和动态网络社区演化中，并利用更大规模的网络数据集来进行实验。

［1］GIRVAN M，NEWMAN M E J.Community structure in so⁃cial and biological networks［J］.Proc of the National Acade⁃my of Sciences of the United States of America，2002，99（12）：7821⁃7826.

［2］FORTUNATO S.Community detection in graphs［J］.Phys⁃ics Reports，2010，486（3／5）：75⁃174.

［3］NEWMAN M E J，GIRVAN M.Finding and evaluating com⁃munity structure in networks［J］.Physical Review E，2004，69（2）：026113.

［4］LEE J，GROSS S P，LEE J.Modularity optimization by con⁃formational space annealing［J］.Physical Review E，2012，85（5）：056702.

［5］SHANG Ronghua，BAI Jing，JIAO Licheng，et al.Commu⁃nity detection based on modularity and an improved genetic algorithm［J］.Physica A：Statistical Mechanics and Its Ap⁃plications，2013，392（5）：1215⁃1231.

［6］DUCH J，ARENAS A.Community detection in complex net⁃works using extremal optimization［J］.Phys Rev E，2005，72（2）：027104.

［7］GUIMER R，AMARAL L A N.Functional cartography of complex metabolic networks［J］.Nature，2005，433（7028）：895⁃900.

［8］PIZZUTI C.A multiobjective genetic algorithm to find com⁃munities in complex networks［J］.IEEE Trans on Evolution⁃ary Computation，2012，16（3）：418⁃430.

［9］LI Y Y，CHEN J，LIU R C，et al.A spectral clustering⁃based adaptive hybrid multi⁃objective harmony search algorithm for community detection［C］.Proc of the CEC 2012.［S.l.］，2012：1⁃8.

［10］淦文燕，赫南，李德毅，等.一种基于拓扑势的网络社区发现方法［J］.软件学报，2009，20（8）：2241⁃2254.GAN Wenyan，HE Nan，LI Deyi，et al.Community dis⁃covery method in networks based on topological potential［J］.Journal of Software，2009，20（8）：2241⁃2254.

［11］邓小龙，王柏，吴斌，等.基于信息熵的复杂网络社团划分建模和验证［J］.计算机研究与发展，2012，49（4）：725⁃734.DENG Xiaolong，WANG Bai，WU Bin，et al.Modularity modeling and evaluation in community detection of complex network based on information entropy［J］.Journal of Com⁃puter Research and Development，2012，49（4）：725⁃734.

Optional granularity community detection algorithm based on gravitation

DONG Yuxin，CHI Kuo，YIN Guisheng

（College of Computer Science and Technology，Harbin Engineering University，Harbin 150001，China）

Community detection is an important field in the study of complex networks，and it is widely applied.But for most of the existing algorithms at present，community structure is determined by some community evaluation function，and only one division result can be obtained.Referenced from the galaxy model and the law of universal gravitation，a new community detection algorithm of complex network based on gravitational search is proposed，nodes in a network are given quality，and community framework is built.Then community structure is divided via gravitation.The granularity of the detected communities can be selected，and thereby a variety of division results can be obtained，without prior knowledge and the related parameters.Experiments in real networks，and compari⁃son with other pre⁃existing community detection algorithms prove that，the community structure of complex networks can be effectively and accurately excavated via the proposed algorithm.

complex network；optional granularity；community detection；gravitation

10.3969／j.issn.1006⁃7043.201404026

TP391

：A

：1006⁃7043（2015）06⁃0809⁃05

http：／／www.cnki.net／kcms／detail／23.1390.u.20150428.1117.020.html

2014⁃04⁃14.网络出版时间：2015⁃04⁃28.

国家自然科学基金资助项目（61272186）；黑龙江省自然科学基金资助项目（F201110）.

董宇欣（1974⁃），女，副教授，博士；迟阔（1989⁃），男，博士研究生；印桂生（1964⁃），男，教授，博士生导师.

迟阔，E⁃mail：chik89769＠163.com.