一种社交网络的增量社区检测算法及实现优化

王冰玉，吴振宇，沈苏彬

(1.南京邮电大学 物联网学院，江苏 南京 210000；2.南京邮电大学 计算机学院，江苏 南京 210000)

1 概 述

在社交网络中，存在一些联系较为紧密的人群，这些人之间的互动和联系紧密和频繁，常常会把这类人群聚类用来分析[1]，在社交网络研究领域中一般将这些人群所构成的团体称为社区[2]。发现社交网络中的社区是十分有意义的，可以从中挖掘出许多隐含信息[3-4]。目前针对社交网络的社区检测算法进行了研究，如崔泓等[5]针对社交网络提出一种基于模块化的社区检测算法。社区的特点显而易见，即社区内部的联系紧凑，而社区之间的联系较为疏松。社区内部的人之间往往存在着一些共性，例如，在Facebook、Twitter、Weibo这样的社交网络中，联系紧密的人群往往在讨论一件他们都感兴趣的事件。再如在DBLP(digital bibliography & library project，计算机界反映共同作者关系的公共数据集)这样的数据网络中，联系紧密的学者往往是研究相关或者类似的领域。在众多的社区挖掘算法中，K-clique(K团)[6]是一种较为经典的社区检测算法，优点在于其允许重叠社区的存在，且其参数k可以直观地表示社区检测的密度要求。

现实中的社交网络规模都是较大的，对DBLP数据集中1990年-2016年中包含的会议论文的共同作者关系所形成的网络运行了K-Clique算法，算法的执行效率如图1所示。

图1 社区检测随网络规模变化的时间消耗

由图1可见，随着社交网络规模的不断增大，K-Clique算法的运行时间会急剧上升。对此，文中提出一种增量式社区检测算法。该算法在时间片更新时使用新时间片上出现的节点和边去更新已有的社区检测结果，而非在整个网络上重新进行社区检测。这里的增量式是批量递增，而非每新出现一条边或一个节点时就对已有社区进行更新[7]。也有使用滑动窗口[8]的方式对网络进行社区检测，但是这种方式每次只能输出网络中的若干个时间切片所包含的社区，而不能针对整个网络输出其社区结构。与传统K-Clique进行了对比，以验证该算法的有效性。

2 相关研究

2.1 社区检测算法研究

社区检测算法有多种类型，其中比较有代表性的是基于划分的社区检测算法[9-10]、基于模块度[11-13]的社区检测算法、基于标签传播[14-16]的社区检测算法以及基于团渗透[6]的社区检测算法等。基于划分的社区检测算法基本思想是找出社区之间的链接，然后逐步删除这些链接，最后剩余的便是社区结构。2004年Mark Newman基于贪心思想提出了模块度最大化的贪心算法(FN)，将整体最优化问题分解为局部最优化问题。模块度的思想实际上是社区内部的边的密度大于网络中的整体密度。为了降低算法的时间复杂度，Vincent Blondel等提出了另一种层次贪心算法[12]-基于标签传播(1abel propagation algorithm，LPA)，遵从的基本思想是“在具有社区结构的网络中，任一节点都应当与其大多数邻居在同一个社区内”。重叠社区算法[17-18]也是目前研究较多的社区检测算法，团渗透算法(clique percolation method，CPM)是重叠社区检测算法的代表性算法，这种算法将网络中共享节点的团连接在一起形成社区。这类理论认为，网络中存在的社区是可以有重叠的，这和实际的社交网络也是相符的。以微博为例，一个共同话题社区中的人可能同时也对另一个话题感兴趣。Yang等[19]还研究了在有向网络中利用概率模型进行社区检测的算法。

2.2 K-Clique基本原理

K-Clique是一种团渗透算法，基本原理可以描述如下：将图中的完全子图称为团(完全子图就是每两个点之间都有一条边的子图)，若该子图的节点数为k，那么该子图就称为K-Clique[1]，若两个K-Clique之间有k-1个相同节点，那么就称这两个K-Clique是相邻的。Clique渗透算法将彼此相邻的clique构成的最大集合称为社区。

3 增量式社区检测算法

3.1 算法整体设计

该算法需要对新时间片内网络中新增的元素进行处理，再使用处理结果去更新已有结果。首先定义以下几个概念：

定义1：CSS(complete subgraph set，完全子图集)，这个集合中存储的是已处理的网络中现有的所有完全子图结构。

定义2：DS(difference subgraph，差分子图)，这是一个图结构，在第一个时间片上，DS就是当前时间片内除去CSS中包含元素之外的子图结构。从第二个时间片开始，DS存储的是当前时间片中新增节点和边以及上个时间片中遗留的DS所共同构成的网络US(unprocessed subgraph)中去除了CSS中包含的节点及边之后的剩余元素。

定义3：US(unprocessed subgraph，未处理子图)，这是当前时间片中新增节点和边以及上个时间片中遗留的DS所共同构成的网络。

首先对第一个时间片中的网络进行传统K-Clique社区发现，保存第一个时间片中节点数大于等于k的CSS,以及时间片中关于CSS的差集所构成的DS，这个DS实际上也就是非完全子图所构成的局部网络，这些非完全子图虽然在当前处理的新增网络内没有被涵盖在社区之中，但有可能会与后续新增网络中的节点构成完全子图，从而参与社区更新。

在对下一个时间片的数据进行处理时，需要将DS也融入当前的时间片新增数据中构成当前US。对于当前时间片上的US，先找出其中包含的所有完全子图，之后，以新发现的完全子图去更新CSS以及DS。处理完最后一个时间片中的US后，对于CSS中的每一个完全子图，如果两个完全子图之间的共同节点数大于等于k-1,那么以完全子图为基本节点，在两个完全子图之间连一条边，构成一张宏观上的图H，图H中的每个节点都是一个完全子图，图H中的每一个连通图就是整个网络中的一个社区。

上述步骤可以用Algorithem1来描述，其中最主要的部分包括updateCSS、updateDS。

Algorithem1:

Input：dynamic Graph increases over time，K

Output: Communities in Graph

Get CSS in first time slice

Get DS in first time slice

While time slice:

Get US by combining DS with new edges and nodes in current time slice

Find newCliques in US

Call updateCSS(newCliques)

Call updateDS(newCliques)

Communities=combination of those cliques in CSS who’s common nodes>k-1 (connected parts in H)

3.2 更新CSS

在处理新时间片上未处理数据US时分为两步，首先需要获取当前US中所包含的完全子图结构，然后以这些新的完全子图去更新CSS。更新CSS时分为以下三种情况：

(1)新发现的clique与已有的所有clique均无交集;

(2)新发现的clique完全囊括于CSS中已有的clique中;

(3)新发现的clique与多个clique有交集，但不囊括于其中任何一个。

这几种情况如图2所示，白色节点和实线构成的图表示已有clique，黑色节点和虚线构成的图表示新发现的clique。

图2 CSS更新类别

情况(1)：直接将新发现的clique加入CSS中即可，不需要做其他改变。

情况(2)：新发现的clique对CSS中已有的clique不会造成结构和数量上的改变，因此不需要对CSS进行更新。

情况(3)：需要将与新clique有交集的已有clique进行结构上的更新，可能会造成CSS中已有clique的数量的变化。对于结构上可能造成的改变，采取的方式是，将新发现的clique与与其有交集的若干个clique先拼接成一张临时图结构，再从这个临时图结构中找出其中包含的完全子图。以这个方式重构相关clique之后，需要将之前的clique从CSS中删除，然后将重构后的若干个新Clique加入CSS中。更新CSS的算法如下：

Algorithem2:updateCSS

Input:newCliques

Output:updated CSS

If CSS==null:

CSS=newCliques;

Else:

for clique innewCliques:

If clique has no intersection with CSS:

add clique into CSS;

Else:

If clique belongs to one of CSS:

Do nothing;

Else:

Joint clique with related cliques in CSS;

Find new cliques structure in the jointed graph;

Add these new cliques into CSS and remove the old ones;

3.3 更新DS

在更新DS时，基本原则是将新发现的clique中包含的节点和边从DS中删除，以免这些节点在下个时间片的US内被重复运算。但是实际情况下，新发现的clique中的节点可能还与DS中其他非clique中的节点有联系，为了保存这样的联系，需要保留这样的clique节点。判断的依据是，如果某个clique中包含的某个节点的度大于其所在的所有clique中所有的节点数，即说明当前节点除了存在于clique中的边以外还有其他边连接，这样的节点就不予删除。采用遍历的方式收集需要删除的节点，上述过程描述如下：

Algorithem3:updateDS

Input:newCliques

Output:updated DS

S=all nodes in newCliques

For node N in S:

Find all the cliques innewCliques which include node N

If degree of node in DS>=sum of all cliques size:

Remove node from S

For clique innewCliques:

Remove edges innewClique from DS

Remove nodes in S from G

4 性能优化

为了提高算法的执行效率，缩短节点与clique的查找时间，文中采用两张哈希表的方式来存储clique集合以及节点到已有clique之间的映射关系，如图3所示。

图3 clique存储方式

图3中有两张哈希表，HashTable2中，每个clique都是一个真实的图结构，且每一个clique都有唯一对应的key值。HashTable1表示节点到clique键值对的映射，其中的Key_Clique表示的就是HashTable2中的key。当节点属于某一个clique中，那么就将node作为key，该clique对应的编号作为值存储在左侧的哈希表中。

同时还定义了一个资源池POOL，即clique的key值的资源分配池，定义POOL的目的是当容纳clique哈希表有更新时，能够有效地重分配key值。在更新HashTable2中的clique时，对POOL资源池的更新分为两种情况：

(1)新发现的clique没有对已有的clique的结构造成影响，只要将新发现的clique直接加入HashTable2中并为其分配未使用过的唯一键值作为其标识。而这个时候就必须要知道哪些键值已经被使用过，每次都重新遍历一次HashTable2的所有键就过于麻烦，而使用POOL资源池时就可以不用每次都遍历，直接从POOL池中选取键值即可，选取之后POOL资源池中对应的键值会被删除，以保证键的唯一性。

(2)另一种情况是新发现的clique结构对已有的clique结构造成了影响，这种情况下要采取的措施是，结构改变了的clique会从HashTable2中删除，并且POOL资源池对这些被删除的clique的键进行回收。随后将结构改变后的clique重新放入HashTable2中，并且从POOL中分配相应数目的键值对结构更新后的clique进行标识。这种情况下使用POOL的好处是，既保证了HashTable2中每个clique都有唯一标识，又可以使得键能被有效地回收利用，不用每次去与已有clique比对，从而保证不会分配已经使用过的键值。

5 实 验

5.1 DBLP数据集

DBLP是计算机界反映共同作者关系的公共数据集，数据集中包含了期刊或会议论文的共同作者信息以及论文发表时间信息。在这个数据集中，提取了1990-2016年发表于ICML会议的论文的共同作者信息，以作者为节点，以作者之间的共同发表文章的关系为边，即若两个作者共同发表了一篇文章，就在这两个作者中间连接一条边。最终的图中共包含4 771个节点，9 641条边。

5.2 算法效率

分别在上述数据集中对比了传统K-Clique与增量K-Clique在k分别为2,3,4,5时的运行效率，如图4所示。

图4 增量K-Clique与传统K-Clique效率对比

可以看到，随着时间片的递增，网络规模不断扩大，增量K-Clique算法比传统K-Clique算法在运行效率上有明显的提升，且k越大，效率提升得越显著。这是由于随着k的增大，对社区的密集程度要求更高，发现的社区数量相对较少，能够更加有效地减少社区增量更新过程中的一些计算量。

5.3 算法准确率

表1分别记录了k=2,3,4,5时从1990年到某一年使用K-Clique(CK)算法和增量K-Clique(incremental K-Clique，ICK)算法所发现的社区数量比较。可以看到，k=2时，K-Clique与增量K-Clique算法均是寻找网络中的连通图，因此两种方式寻找出的社区数量是一致的。当k≥3时，由于增量式K-Clique算法会忽略少量的连接细节，因此发现的社区数量与K-Clique相比会略多一些，但是数量基本与K-Clique发现的社区数量持平。

表1 K-Clique与增量K-Clique社区检测数量比较

为了更直观地看到算法的检测效果，图5为在检测出社区数量较小的情况下K-Clique算法与增量K-Clique算法的社区检测结果对比。取时间片1990至1993年为止的(k=4时)两种算法社区检测结果作对比，可以看到增量K-Clique算法与传统K-Clique的检测结果基本吻合。

6 结束语

社区检测是现实中各种网络的重要分析手段，因此社区检测的研究具有重要的实际意义。文中对K-Clique团渗透算法(CMP)在大规模网络中进行改进。这种改进算法适用于网络结构比较紧密的大规模网络中，在算法效率上有明显提升。而在网络规模稀疏的情况下可能效果会有所衰减，因为算法可能会忽略较多的细节从而导致准确率下降。后续会将这种算法应用到实际问题中，例如挖掘社交网络的密集用户社区，以进一步挖掘社区中的隐含信息等。

K-Clique增量K-Clique'John H.Gennari','KazuoHiraki','Yoshinobu Yamamoto','Yuichiro Anzai' 'John H.Gennari','KazuoHiraki','Yoshinobu Yamamoto','Yuichiro Anzai' 'DanaKedzier','DonaldMichie','ClaudeSammut','Scott Hurst''DanaKedzier','DonaldMichie','ClaudeSammut', 'Scott Hurst''Paul R. Cohen','Adam St.Amant', 'Adam Carlson','Lisa Ballesteros''Paul R. Cohen','Adam St.Amant','Adam Carlson','Lisa Ballesteros''James Garrett','Bradley L. Whitehall','Thomas G.Dietterich','Stephen C. Y. Lu','Richard J. Doyle','BrianFalkenhainer','Steve A.Chien''James Garrett','Bradley L. Whitehall','Thomas G.Dietterich','Stephen C. Y. Lu','Richard J. Doyle','BrianFalkenhainer','Steve A.Chien''JohnVittal','Bernard Silver','William J.Frawley','Kelly Bradford','Glenn A.Iba''JohnVittal','Bernard Silver','William J.Frawley','Kelly Bradford','Glenn A.Iba''David K.Tcheng','Stephen C. Y. Lu','Larry A. Rendell','Bruce L. Lambert''David K.Tcheng','Stephen C. Y. Lu','Larry A. Rendell','Bruce L. Lambert''Lee A.Appelbaum','Stuart L. Crawford','Richard M. Tong','Robert M. Fung''Lee A.Appelbaum','Stuart L. Crawford','Richard M. Tong','Robert M. Fung''Stewart W. Wilson','Alexandre Parodi','PierreBonelli','Sandip Sen''Stewart W. Wilson','Alexandre Parodi','PierreBonelli','Sandip Sen''Glenn R.Koller','Qian Yang','Jerry B. Weinberg','Gautam Biswas''Jerry B. Weinberg','Qian Yang','Glenn R.Koller','Gautam Biswas''Davide De Marchi','Attilio Giordana','Filippo Brancadori','FrancescoBergadano','Lorenza Saitta''Davide De Marchi', 'Attilio Giordana','Filippo Brancadori','FrancescoBergadano','Lorenza Saitta''Christopher M. Tuck','John E. Laird','Eric S.Yager','MichaelHucka''Christopher M. Tuck','John E. Laird','Eric S.Yager','MichaelHucka'

图5 K-Clique与增量K-Clique社区检测结果比较