基于广度优先搜索的局部社区发现算法

王豫中，范 磊，李建华

（上海交通大学电子信息与电气工程学院，上海200240）

基于广度优先搜索的局部社区发现算法

王豫中，范 磊，李建华

（上海交通大学电子信息与电气工程学院，上海200240）

局部社区发现是网络拓扑研究中的热点，从起始节点的最大结合性节点出发，提出一个基于给定节点的局部社区发现算法。对整个社区进行广度优先搜索（BFS），从起始节点开始找到最大结合性节点，基于节点相似度（共同好友数目）并且利用BFS进行社区发现，对所发现的社区进行剪枝策略，从而得到起始节点所在的局部社团。实验结果证明，该算法在不降低精度的前提下，时间复杂度为O（kd3）。

最大结合性；共同好友数；节点相似度；广度优先搜索；局部社区发现

DO I：10.3969/j.issn.1000-3428.2015.10.008

1 概述

随着网络的发展，越来越多的学者开始研究复杂网络，如：社交网络，蛋白质网络［1］，签名网络，微博社区网络［2］，通信网络，在线社会网络［3］以及W eb网络［4］。大量的研究表明，社区结构普遍地存在于大型网络中，并扮演着重要的角色。研究发现在社区结构内部的节点联系相对比较紧密，而在社区结构之间节点联系相对比较稀疏［5］。发现社区结构对于研究大型复杂网络具有现实以及长远意义。

目前网络拓扑发现社区结构主要有两大方向：一个是全局社区发现；另一个是局部社区发现。全局社区发现以整个网络为基准，发现网络中存在的所有社区［6］。然而由于全局社区发现通常需要全局网络信息，有时网络是动态变化的或获取全网信息难度较大等客观因素的制约［7］，很多学者提出了局部社区发现方法［8-10］。与全局社区发现不同的是，局部社区发现从某个单一节点出发，进而发现该节点所在的社区结构。因此，在局部社区发现算法中整个网络被划分为2个社区：该节点所在的社区CT以及剩余社区～CT。局部社区发现算法不需要知道整个网络的信息，算法从一个起始节点出发，然后采用某种机制扩展社区直到达到某个预定义的条件。

本文算法从起始节点的最大结合性节点出发，用图的广度优先搜索算法（BFS）进行社区发现。对于图中的每一个节点，用该算法找到它所在的局部社区，并采用经典的衡量标准来验证算法的有效性和优越性。

2 相关工作

用G=（V，E）来代表整个网络，其中，V表示节点集合；E表示边集合。n和 m分别代表节点的个数和边的个数。和全局社区发现将整个网络划分为几个社区不同的是，局部社区发现算法定义一个起始节点ν0，发现这个节点ν0所在的社区。

文献［11］定义了局部社区发现问题，将局部社区发现问题转换为最优化问题，在此将该算法简记为M算法。

定义节点集合C为所探测到的社区（起始时C只包含一个起始节点ν0）。定义节点集合 U中的节点和C中的节点相连但是不属于C。另外定义了C的的边界节点集合B，B中的节点属于C，但是这些节点又和U中节点相连。最优化函数定义如下：

如果i，j∈E，节点νi和νj中至少有一个在B中，这时 Bij=1。否则 Bij=0。如果（i，j）∈E，δ（i，j）=1，否则δ（i，j）=0。算法通过贪心策略从U中选择可以使R达到最大的节点，并将其加到C中，直到达到某个阈值为止。然而该算法显著的缺点是需要指定社区的大小以及具有 O（k2d）的较高的时间复杂度。其中，d是节点的平均度数；k是最终发现的局部社区的节点个数。

文献［12］提出另外一种最优化算法来发现局部社区，简记为R算法。最优化函数定义为：

其中，Ein代表社区C内部边的个数；Eout代表社区C外部边的个数。算法要实现M的最大化，分为2个阶段：增加节点阶段和删除节点阶段。使得M增大的节点被加入社区C中，同时如果从社区C中删除一个节点也能使M增大，则删除。这2个阶段交替进行直到 M达到最大值。该算法的缺点是起始节点ν0可能被删除。

文献［13］定义另外一个度量函数：

文献［14］为了提高算法的鲁棒性，描述局部社区发现算法不是从起始节点出发进行社区发现，而是找到起始节点最近的局部最大中心点，从这个局部最大中心点出发进行社区发现，因此该算法可以有LMD-M，LMD-R，LMD-F等多种算法实现，简记为LMD算法。

文献［15］提出的局部社区发现算法不同于上述算法，该算法从一个团出发进行社区发现。此算法可挖掘出起始节点的重叠社区。本文将该算法简记为LMD-MC算法。

3 本文算法

上述算法都有各自的缺点，文献［11-12］提出的算法达到了O（k2d）的时间复杂度。文献［14］提出的算法由于要发现局部最大中心点，这个过程可能具有较大的时间复杂度。文献［15］提出的算法也有着时间复杂度过高的问题。

本文提出一种新的局部社区发现算法，该算法从一个起始节点相对应的最大结合性节点出发，基于2个节点的共同好友数目，利用经典的广度优先搜索算法来进行社区发现。发现起始节点相对应的最大结合性节点：一是可以提高算法的鲁棒性，避免边界节点找不到社区的情况；二是可以降低寻找局部最大中心点的时间复杂度。基于共同好友数目并且结合广度优先搜索的算法将时间复杂度由原来的O（k2）降低到O（k）。

3.1 相似度

相似度用来衡量2个个体之间连接的紧密程度，如果2个个体的相似度越大，则它们属于同一个社区的概率也就越大。基本的相似度度量有欧氏距离、Jaccard相似性［16］以及余弦函数［17］等。本文中用来衡量2个节点的相似度定义为：

其中，S（νi，νj）表示节点 νi和节点 νj的相似度；N（νi）表示节点νi的邻居节点集合；N（νj）表示节点νj的邻居节点集合。所以分子表示节点νi和节点νj的共同邻居节点数目。分母表示节点 νi和节点 νj邻居节点数目的最小值。若某一个节点的邻居数量为1，则将它和其邻居节点的相似度定义为1，因此此节点始终可以归为其邻居节点所在的社区，其中0≤S（νi，νj）≤1。

3.2 节点的最大结合性

3.2.1 节点的结合性

一个节点的结合性定义为它的邻居节点之间连接的边数和它的邻居节点之间可能存在的最大连接边数的比值。节点ν的结合性dν定义为：

其中，eij表示节点i和节点j有边相连；分子表示节点ν的邻居节点集合中实际存在的边数；分母表示节点ν的邻居节点集合中可能存在的最多的边数。3.2.2 节点最大结合性

考虑一个节点ν以及其邻居节点集合N（ν），找出集合（ν，N（ν））中具有最大结合性 d的节点作为此节点ν的最大结合性节点。即节点 ν的最大结合性节点w定义为：

3.3 社区的邻居节点集合

一个社区的邻居节点集合定义为未被此社区包含的但有边和此社区中的节点相连的节点的集合。对于社区C的邻居节点集合B定义如下：

3.4 节点社区的内度和外度

一个节点对于社区的内度定义为此节点的邻居节点中在社区内部的节点的个数。

一个节点对于社区的外度定义为此节点的度数减去节点对于社区的内度。

节点ν对于社区C的内度定义为：

节点ν对于社区C的外度定义为：

3.5 算法过程

算法的主要符号说明如下：

ν0：起始节点；

dν：节点ν的结合性；

w0：节点ν0对应的最大结合性节点；

C：被发现的局部社区；

Q：广度优先搜索算法中用到的队列；

S（νi，νj）：节点νi和节点νj的相似度；

sth：相似度阈值。

算法步骤如下：

（1）初始化社区 C为空，从起始节点 ν0出发找到它所对应的最大结合性节点 w0，将节点 w0加入C，并标记w0为已经访问过的节点。

（2）从w0出发对图进行广度优先搜索（BFS）。假如νi是当前从队列中出队的节点，将其邻居节点中满足S（νi，νj）≥sth的节点νj入队并标记。将所有出队的节点放入C中。

（3）对于C的邻居节点集合B中的任何一个节点b∈B，若inward（b，C）≻0.5，则将b加入到C中。在此步骤中由于起始节点或者是真正的起始节点ν0，或者是其对应的最大结合性节点w0。所以起始节点ν0要么位于新发现的社区C中，要么位于社区C的邻居节点集合B中。所以对B中每一个节点实施上述操作也就相当于判断了inward（ν0，C）≻

0.5 的正确性。

算法的伪代码描述如下：

算法1FindMaχConnection（ν0）：寻找节点ν0的最大结合性节点

代码中sort（result）表示对result集合中的数值按照从小到大的顺序进行排序。maχ（result）表示提取出result集合中的最大值。

算法2getSimilarity（data1，data2）：计算节点data1和节点data2的相似度

算法3BFS-Process（ν0）：寻找ν0的局部社区C

代码中enqueue（queue，w0）表示将w0放入队列queue。dequeue（queue）表示从队列queue中出队一个元素。

算法4main：寻找ν0的局部社区入口函数

代码中BFS-Process（ν0）表示从起始节点ν0出发发现局部社区的过程，对应算法3的函数调用，函数返回被发现的局部社区。

3.6 算法复杂度分析

本文算法的时间复杂度分析主要包括两部分。一部分是发现指定起始节点的最大结合性节点部分的时间复杂度，另外一部分是局部社区发现部分的时间复杂度。

（1）发现指定起始节点最大结合性节点部分的时间复杂度（算法1时间复杂度）

计算某个节点 νi结合性的时间复杂度为O（di

2），其中，di为节点 νi的度。为了计算节点 νi的最大结合性节点，需要计算此节点以及它的邻居节点的结合性，并找出其最大值，所以总的时间复杂度为O（di

3）+O（di）=O（di3）。

（2）计算2个节点相似度的时间复杂度（算法2时间复杂度）

在广度优先搜索过程中，要计算当前节点 νi和它的邻居节点νj（eij∈E）的相似度。要计算其共同好友数目，假设di和dj分别为节点νi和节点 νj对应的度数，则计算两者共同好友数目的时间复杂度为O（didj）。

（3）局部社区发现过程的时间复杂度（算法3时间复杂度）

对于广度优先搜索过程，要遍历当前节点 νi的所有邻居节点νj（eij∈E），并计算两者的相似度，所以对于单个节点νi其时间复杂度为假设需要遍历k个节点才能将整个局部社区发现出来，并假设 d为整个社区的平均节点度数，所以局部社区发现过程的时间复杂度为O（kd3）。再加上算法1的时间复杂度，总的复杂度为由此可见，此算法将原来的具有O（k2）的时间复杂度降低为O（k）。

3.7 算法鲁棒性分析

本文算法具有很强的鲁棒性。为了避免起始节点位于边界，采取算法1FindMaχConnection（ν0）来找出起始节点ν0相对应的最大结合性节点，此最大结合性节点一般位于比较中心的位置，从此节点出发进行社区发现可以避免边界起始节点鲁棒性差的缺点。另外在函数getSimilarity（data1，data2）中分母为这样节点度数较小的节点也可以发现节点度数较大的邻居节点，提高了算法鲁棒性。

4 实验结果分析

为验证算法的正确性，引入Precision，recall，F-measure3个指标，分别定义为：

从以上公式可以看出，Precision表示真实社区和算法挖掘出来的社区的交集占算法挖掘出来的社区的比例。recall表示真实社区和算法挖掘出来的社区的交集占真实社区的比例。F-measure表示Precision和recall的几何平均数。

将此算法应用到经典的社区网络中，分别是日本足球俱乐部网络、海豚网络、大学生足球赛网络和美国政治书籍网络。各个网络的社区规模如表 1所示。

表1 经典数据集

为了验证算法的有效性，将此算法和原来的经典局部社区挖掘算法以及近几年新提出的局部社区挖掘算法进行对比。包括Clauset算法（简称M算法）、Luo算法（简称R算法）、Lee算法（简称F算法）、Chen算法（简称LMD算法）、Zhu算法（简称LMD-CD

算法）。在本文的算法中，对于getSimilarity（u，ν）≥sth中阈值sth的设置比较重要，sth的取值不同，所发现社区的精度区别很大。在此取sth=0.5。实验结果如表2所示。

表2 对不同数据集的实验结果

从上面的显示结果可以看出，对于日本足球俱乐部网络，本文所采用的算法无论在准确率、召回率以及综合值上面均是最优的。对于海豚网络和足球队网络，除了召回率本文算法低于LMD算法之外，其他2个指标均高于其他算法，尤其是综合值。对于政治书籍网络，本文算法在召回率和综合值上面均是最优的。由此可以得出，本文算法在将时间复杂度降低为社区规模的线性复杂度的前提下，仍然提高了算法精度，是一个可选算法。

5 结束语

本文提出的局部社区发现算法从起始节点的最大结合性节点出发，对整个社区进行BFS搜索，基于共同好友数目考虑是否将一个节点加入到已经发现的社区中。将本文算法应用到各种经典社区中均取得了良好的效果。本文算法最大的优势是将社区发现的时间复杂度由O（k2）降低到O（k）。

［1］ Jonsson P F，Cavanna T，Zicha D，et al.Cluster Analysis of Networks Identification of Important Protein Communities Involved in Cancer Metastasis［J］.BMC Bioinformatics，2006，6（7）：2-9.

［2］ 蔡波斯，陈 翔.基于行为相似度的微博社区发现算法研究［J］.计算机工程，2013，39（8）：55-59.

［3］ 熊正理，姜文君，王国军.基于用户紧密度的在线社会网络社区发现算法［J］.计算机工程，2013，39（8）：50-54.

［4］ Dourisboure Y，Geraci F，Pellegrini F.Extraction and Classification of Dense Communities Int-the Web［C］// Proceedings of the 16th International Conference on World Wide Web.Washington D.C.，USA：IEEE Press，2007：461-470.

［5］ Girvan M，Newman M E.Comm unity Structure in Socialand Biological Networks［J］.Sciences of the United States of America，2002，99（12）：7821-7826.

［6］ 郭进时，汤红波，葛国栋.一种联合拓扑与属性的社区模糊划分算法［J］.计算机工程，2013，39（11）：35-40.

［7］ Li Xiang，Chen Guanrong.A Local-world Evolving Network Model［J］.Physical A：Statistical Mechanics and Its Applications，2003，328（1/2）：274-286.

［8］ Clauset A.Finding Local Comm unity Structure in Networks［J］.Physical Review E，2005，72（2）.

［9］ Luo Feng，Wang J Z，Promislow E.Exploring Local Community Structures in Large Networks［C］// Proceedings of 2006 IEEE/WIC/ACM International Conference on Web Intelligence.Washington D.C.，USA：IEEE Press，2006：233-239.

［10］ Lancichinetti A，Fortunato S，Kertesz J.Detecting the Overlapping and Hierarchical Comm unity Structure in Complex Networks［J］.New Journal of Physics，2009，11（3）.

［11］ Girvan M，Newman ME.Finding and Evaluating Community Structure in Networks［J］.Physical Review E，2004，69（2）.

［12］ Newman M E.Modularity and Comm unity Structure in Networks［J］.Sciences of the United States of America，2006，103（23）：8857-8882.

［13］ Acuña M A，Dorso G.Detection of Community Structures in Networks via Global Optimization［J］. Physica A：Statistical Mechanics and Its Applications，2005，538（1）：593-604.

［14］ Jure L，Kevin J L，Anirban D，et al.Community Structure in Large Networks：Natural Cluster Sizes and the Absence of Large W ell-defined Clusters［EB/OL］.（2009-10-21）.http：//projecteuclid.org/euclid.im.

［15］ Newman M E.Fast Algorithm for Detecting Community Structure in Networks［J］.Physical Review E，2004，69（6）.

［16］ Gibson D，Kumar R，Tom kins A.Discovering Large Dense Subgraphs in Massive Graphs［C］//Proceedings of the 31st International Conference on Very Large Bases Databases.Washington D.C.，USA：IEEE Press，2005：721-732.

［17］ Fortunato S.Comm unity Detection in Graphs［J］.Physics Reports，2010，486（3）：75-174.

编辑 索书志

Local Community Discovery Algorithm Based on Bread th-first Search

WANG Yuzhong，FAN Lei，LI Jianhua
（School of Electronic Information and Electrical Engineering，Shanghai Jiaotong University，Shanghai200240，China）

Local community detection is a hot topic in network topology research recently，this paper proposes a local community detection algorithm based on a given node.This algorithm starts from original node，finds the max connective node relevant to the original node，uses Breadth-first Search（BFS）based on node similarity to find local community，and cuts off the found community and gets the entire community which contains the original node.Experimental result shows that this algorithm reduces the time complexity to O（kd3）with high accuracy.

max associativity；common number of friends；node similarity；Breadth-first Search（BFS）；local community detection

王豫中，范 磊，李建华.基于广度优先搜索的局部社区发现算法［J］.计算机工程，2015，41（10）：37-41.

英文引用格式：Wang Yuzhong，Fan Lei，Li Jianhua.Local Community Discovery Algorithm Based on Breadth-first Search［J］.Computer Engineering，2015，41（10）：37-41.

1000-3428（2015）10-0037-05

A

TP391

国家“973”计划基金资助项目（2013CB329603）；上海市科委基础研究领域基金资助项目（13JC1403500）。

王豫中（1990-），男，硕士研究生，主研方向：社交网络，数据挖掘；范 磊，副教授；李建华，教授。

2014-09-02

2014-10-15E-mail：wangyuzhong@sjtu.edu.cn