基于局部邻域连通性的重叠社区发现算法

郑文萍，乔艳超，杨贵

（1.山西大学 计算机与信息技术学院，山西 太原 030006；2.山西大学 计算智能与中文信息处理教育部重点实验室，山西 太原 030006；3.山西大学 智能信息处理研究所，山西 太原 030006）

0 引言

现实世界中的复杂系统可以建模为复杂网络如社交网络、科研协作网络、蛋白质相互作用网络等，其中节点代表系统个体，边代表个体间的联系［1］。社区结构是复杂网络的重要特征之一。发现真实网络中的社区结构有助于了解实体之间的相互作用，深入理解和分析复杂系统的群体特征和结构特征。如发现社交网络中有相似兴趣爱好的用户群体、科研协作网络中具有相似研究兴趣的学术团体、蛋白质相互作用网络中行使生物功能的蛋白质复合体等。鉴于此，社区发现算法已被广泛应用个性化兴趣推荐、社会网络分析、蛋白质功能预测等诸多领域［1-3］。

目前已经有许多成功的非重叠社区发现算法用来检测网络中社区间没有共同节点的社区结构。然而在真实网络中，有些节点可能有多个社区归属，如在线社交网络中的用户可能属于不止一个兴趣爱好团体、科研协作网络中一个科学家可能归属于多个研究领域、蛋白质相互作用网络中大部分蛋白质属于多个蛋白质功能复合体，发现复杂网络中的重叠社区得到了越来越多的关注。目前已有的重叠社区发现算法主要包括基于派系过滤的、基于标签传播的和基于局部扩展的重叠社区发现算法等。

最早的重叠社区检测算法是2005年Palla等［4］提出的派系过滤算法CPM，通过发现相邻τ派系检测到重叠的稠密社区，然而发现网络中所有的τ派系是NP困难问题，算法计算代价比较大。2008年Kumpula等［5］提出SCP算法对CPM算法中的派系发现过程进行改进，从一个空网络开始，在插入边的同时检测τ-团，提高了社区检测速度。基于派系过滤的算法通常用于检测网络中的内部连边稠密的社区，对网络中普遍存在的内部稀疏连接的社区发现能力不足。派系过滤算法的计算开销依赖于网络团的分布，无法适用于大规模网络的社区发现问题。

2010年，Gregory等［6］提出了基于标签传播的重叠社区发现算法COPRA，计算标签传播过程中节点对社区的隶属度，高于给定阈值的标签被赋予节点。由于COPRA仅根据邻域的当前标签信息更新节点标签，因此最终产生大量的小规模社区。针对这一问题，2011年Xie等［7］提出基于动态交互规则的标签传播算法SLPA，根据节点的所有历史标签信息更新标签。2012年Coscia等［8］提出了基于局部结构的标签传播算法DEMON，利用标签传播算法检测网络中每个节点的直接邻居节点所构成的局部子图内的社区结构，对所发现的局部社区进行合并得到最终重叠社区检测结果。由于节点更新顺序和标签更新过程中的一些随机性，导致标签传播算法的社区发现结果不稳定；另一方面，由于仅利用节点的直接邻居信息更新标签，这类算法通常不能较好地发现网络中大度节点周围的社区［9］。

基于“种子扩展”策略的重叠社区发现算法首先选取一部分节点作为种子节点，将这些种子节点看作社区中心进行扩展，可以更好地发现网络中内部连接密度各异的社区结构。种子节点选择和社区扩展方式影响基于“种子扩展”策略的重叠社区发现质量。Lancichinetti等［10］提出的算法LFM随机选取尚未分配社区的节点作为种子节点，可能导致社区结果不稳定，并且当种子节点属于社区重叠部分时，无法准确发现网络中的重叠社区。Lee等［11］提出的算法GCE选取网络中τ派系作为初始种子进行扩展，在一定程度上提高了算法稳定性，然而由于寻找网络τ派系计算代价大，不适用于大规模网络的重叠社区发现算法，且无法对网络节点完全聚类。Wang等［12］提出算法LOCD优先选择与已有种子节点的相距较远的大度节点作为种子扩展社区。Zhang等［13］提出算法CFCD，根据节点的k核中心性选择种子节点。这些算法在选取种子节点时考虑了节点的局部邻域结构，提高了社区检测质量。基于“种子扩展”策略的社区发现算法往往通过定义社区适应度函数来判断节点是否加入或者离开社区，如算法LFM和GCE以社区内部边数占与社区关联的所有边数比例作为适应度函数，算法LOCD以社区内部节点间Salton相似性与社区关联的所有度数之比作为适应度函数，算法CFCD根据社区内节点的k核中心性定义适应度函数。根据某一种适应度函数进行社区扩展，通常能够发现网络中内部连接比较稠密、适应度值较高的社区结构，无法发现大规模网络中内部结构差异较大的不同社区结构。

2013年，Whang等［14］提出了基于个性化PageRank的社区扩展算法框架NISE，对已选好的种子节点进行扩展，以社区导电性作为社区评价指标，能够更好地发现种子节点周围的社区结构。2015年，Soundarajan等［15］提出了基于节点局部邻域结构的重叠社区检测算法框架Node_Perception，首先发现每个节点的直接邻域导出子图内的局部社区结构，最终合并各节点邻域的局部社区结构得到社区发现结果。

根据节点的邻域结构信息来选择有效的种子节点，并采用合适方式对种子节点进行扩展，是重叠社区检测算法的核心问题。本文提出了一种基于邻域连通性的重叠社区发现算法LNCA，首先根据节点的度信息和k步邻域连通信息计算节点邻域中心性并选择种子节点；采用带重启的随机游走过程扩展种子节点；最后，根据两社区之间的重叠度对相似性较大的社区进行处理。

在6个真实带标签网络、9个真实无标签网络，将本文算法LNCA与6个经典重叠社区发现 算 法 SLPA［7］、DEMON［8］、CPM［4］、Node_Perception［15］、Ego_Networks［16］、Egonet_Splitter［16］进行比较，实验结果表明LNCA算法社区发现结果表现出良好的稳定性，在重叠社区NMI、F1分数和重叠模块度EQ等指标上都表现出较好的性能。

1 背景知识

一个复杂网络可以建模成一个图G=(V，E)，其 中 节 点 集 V={v1，v2，…，vn}，边 集E={(vi，vj)|1 ≤ i≠ j≤ n}。除非特别指出，本文仅对无向无权图进行研究。节点v和w的距离l(v，w)指这两个节点间最短路径的边数。节点v的k步邻域记作Nk(v)={w∈V|l(v，w)=k}，则 N1(v)为 v的直接邻居节点集合，简记为N(v)。因此，节点v的度d(v)=|N(v)|，简记为 dv。顶点子集 S(⊆ V)的体积为Vol(S)=∑v∈Sdv，表示S中所有节点的度 数 和 。 对 图 G′=(V′，E′)，若 V′⊆V 且E′⊆E，则称G′是G的子图，记作G′⊆G。若V′⊆ V 且 边 E′={(vi，vj)|vi，vj∈ V′∧(vi，vj)∈ E}，则称子图G′是图G的导出子图，记为G[V′]，简 记 为 [V′]；若 |V′|= τ且 |E′|= τ(τ-1)/2，则G′是图G的一个包含τ个节点的完全子图，也称为图G的一个τ派系。如果图G的任意两个节点v和w间至少存在一条路径，则称图G是连通的。无向图G中的一个极大连通子图称为G的一个连通分支。

社区结构是复杂网络的重要特征之一，通常表现为社区内部的节点间连接比较紧密，社区之间的节点间连接相对稀疏。对一个图G，社区发现是指将G中的节点分成若干子集，即V=C1∪C2…∪Ck，其中 k为社区的个数。若对任意的 1≤ i，j≤ k，有 Ci∩Cj= ∅，则称 Ω ={C1，C2，…，Ck}是图 G 的一种非重叠社区发现结果；否则称Ω为图G的一种重叠社区发现结果［17］。

Newman等［18］提出的模块度是最常用的衡量社区划分质量的标准，如公式（1）所示：

其中Cv和Cw分别表示节点v和w所属的社区，若Cv=Cw，则 δ(Cv，Cw)=1，否 则 δ(Cv，Cw)=0；avw是邻接矩阵元素。模块度通常用来衡量一种社区发现结果的整体质量。

社区导电性常用来衡量单个社区内部节点与社区外其他部分的连接紧密程度［19］。假设C是图G的一个社区，其导电性如公式（2）所示：

其中

E(C，VC)={(v，w)|v∈C，w∈VC，(v，w)∈E}，表示社区C的向外连边集合。一个社区导电性越低，其社区结构越明显。

2 基于局部邻域连通熵的节点邻域中心性度量

种子节点的选择对于基于局部扩展策略的重叠社区发现算法至关重要，通常应该选择能够代表社区内的局部拓扑结构分布的节点作为一个社区的种子节点，找到合适的种子节点，可以提高社区发现的质量。早期用于重叠社区发现的LFM算法，通过随机选取种子节点进行社区发现，导致算法结果不稳定；而GCE算法把网络中的τ派系作为种子节点，不适用于大规模稀疏网络中的社区发现；DEMON算法将所有节点看作初始种子节点进行扩展，往往将大度节点及其所有邻居节点发现为一个社区，导致网络中的小社区被大社区湮没。2017年所提出的LOCD算法选择大度节点作为种子节点，减少了初始种子节点的数目；而2019年所提的CFCD算法利用节点的k核中心性选择种子节点，由于节点的k核中心性在一定程度上代表了该节点邻域拓扑结构的连通信息，算法对不同社区的区分能力得到提高。

为了有效利用节点邻域拓扑结构的连通信息进行种子节点选择，本节首先给出一种基于节点局部邻域连通熵的节点邻域中心性度量指标。首先根据节点及其局部邻域的导出子图的连通信息计算网络中每个节点的连通概率分布，再计算所得概率分布的熵，称为该节点的局部邻域连通熵。它反映了一个节点的局部邻域拓扑结构的连通分布情况，熵越小代表连通情况越好，该节点对一个社区局部结构的代表性也越强。

2.1 节点的k步邻域连通熵

令Hk(v)表示图G中节点v的k步邻域节点的导出子图，即Hk(v)=[Nk(v)]。设Hk(v)中的连通分支为

连通熵SC(v)值越高，说明节点v局部邻域内的节点越分散，可能归属的社区越多；SC(v)值越低，说明节点v的局部邻域内的节点聚集性较好，属于同一个社区的可能性越大。若网络中的一个节点位于某社区的中心，则该节点的局部邻域节点聚集性较好，因此也应具有较低的连通熵。

图1给出了Dolphin网络及网络节点的k步连通熵（k=2）的分布情况。Dolphin网络包含62个节点，159条边，网络中节点分成2个社区，分别用图中的方形节点和圆形节点表示；图中的黄色节点表示连通熵最小的24个节点。可以看出，有些度较大的节点具有较低的连通熵，这些节点的邻域节点聚集性比较好，通常位于社区中心；然而，一些度较小的边缘节点（如节点61和节点13），由于其邻域中仅包含极少的节点，所得的连通熵也比较低，但这些节点并不位于社区中心。为了更好地选择社区中心，本文提出了基于节点度信息和k步邻域连通熵的节点邻域中心性度量指标。

图1 Dolphin网络中连通熵较低的节点Fig.1 Nodes with low connectivity entropy in Dolphin network

2.2 基于度信息和k步邻域连通熵的节点邻域中心性度量指标

考虑到社区中心节点通常具有较多的连接，并且其邻域中的节点聚集性比较高，因此给出如公式（5）所示的节点邻域中心性度量。对网络中的任意节点v∈V(G)，其邻域中心性为：

图2给出了Dolphin网络中各节点的节点邻域中心性度量指标的分布情况，黄色节点表示中心性最高的24个节点。可以看出，中心性较高的节点更有可能成为社区中心。

图2 Dolphin网络中节点邻域中心性较高的节点Fig.2 Nodes with high neighborhood centrality in Dolphin network

3 基于局部邻域连通性的重叠社区发现算法LNCA

基于上一节提出的节点邻域中心性度量指标，本节给出基于节点邻域连通性的重叠社区检测算法（Overlapping Community Detection Algorithm Based on Node Loca Neighborhood Connectivity，LNCA），算法采用种子扩展策略，包括三个主要步骤：种子节点选择，初始社区扩展，合并社区。

3.1 种子节点选择

对图G=（V，E），首先根据公式（5）计算每个节点的邻域中心性，并将G中节点按照中心性从大到小的顺序排列，即V={v1，v2，…，vn}，对 于 1≤i＜j≤n，有cc(vi)≥cc(vj)。假设ˉ表示网络中节点的平均邻域中心性，选择中心性指标高于cˉcˉ的节点作为候选种子节点集CI。为了避免将两个相邻的中心性较高的节点同时标记为社区中心，依次从候选种子集合CI中选择中心性最高的节点v加入种子节点集I，同时将v及其直接邻居节点从CI中删除，直到CI为空。种子节点的选择过程如算法1所示。图2给出了Dolphin网络的种子节点集，用红色边框表示。

3.2 扩展阶段

在社区扩展阶段，将利用随机游走过程将每个种子节点扩展成为一个社区，为了避免随机游走过程偏离种子节点太远，此处采用带重启的随机游走过程进行社区扩展。

从种子节点s出发进行带重启的随机游走，随机游走粒子每走一步，都以概率1-r返回种子节点s，以概率r从它指出的边中随机选择一条边并沿这条边到达另一个节点。令pt(v)表示经过t步随机游走到达节点v的概率，则t+1步随机游走到达节点v的概率如公式（6）所示：

图3给出了Dolphin网络中以节点46作为种子进行扩展，当r=0.6，0.8，0.9，0.99时所得的社区。本文取r=0.99。对每个种子节点进行扩展，可以得到网络的初始社区发现结果。

图3 Dolphin网络中以节点46为种子扩展所得社区Fig.3 Extended communities with node 46 as seed in Dolphin network

图4给出了Dolphin网络以种子节点｛46，15，48，33，58｝扩展所得的社区，可以看出，由这些种子节点扩展所得的初始社区与网络的真实社区情况比较相符，说明利用带重启的随机游走过程对种子节点进行扩展，可以得到合理的社区结果。然而，如果这些社区包含的节点有很大的重叠，需要对这些重叠度偏高的社区进行合并，以得到最终的社区发现结果。

图4 Dolphin网络种子节点s扩展出的初始社区发现结果Fig.4 Initial communities discovered from seed node s in Dolphin network

3.3 合并重叠度高的社区

对图

G=(V，E)，Ω={C1，…，Ci，…，Cj，…，Cm}是图G的一种社区发现结果，则社区Ci和Cj的重叠度计算如公式（7）所示：

本文中设置当社区Ci和Cj的重叠度大于0.8时，则将Ci和Cj合并为一个社区，即Ω={C1，…，Ci∩Cj，…，Cm}。对初始社区划分结果进行一次合并得到最终社区。

图5给出了Dolphin网络在合并重叠度较大社区之后的社区发现结果，其中分别用方形节点和圆形节点代表不同的社区，节点8和20是重叠节点。

图5 Dolphin网络最终社区划分结果Fig.5 The final community partition result of Dolphin network

4 实验结果

在6个带标签网络和9个无标签网络上，将本文算法LNCA与6个经典重叠社区发现算法SLPA［7］、DEMON［8］、CPM［4］、Node_Perception［15］、Ego_Networks［16］、Egonet_Splitter［16］进行比较实验。数据集基本情况如表1所示，其中未标注引用文献的数据均可从http：//networkrepository.com/index.php 和 https：//snap.stanford.edu/data/获取。

表1 数据集基本情况Table 1 Basic information of datasets

4.1 评价指标

假设 Ω={C1，C2，…，Cm}表示算法得到的社 区 发 现 结 果 ，O={O1，O2，…，Om′}表 示 带 标签数据集的真实社区划分。对带标签网络，采用重叠社区NMI和F1分数评价算法运行结果，对无标签网络，采用扩展模块度（Extended modularity，EQ）评价社区发现质量。

重叠NMI和F1分数的取值范围都是［0，1］，值越高表明算法所得社区发现结果越符合网络真实社区划分结果。

对于无标签网络，采用沈华伟等［22］提出的扩展模块度EQ进行评价，其定义如公式（10）所示：

其中，v和w表示网络节点；m是算法划分得到的社区数目；Ov表示节点v所属的社区数；avw是邻接矩阵元素。EQ越接近1，说明所得到的社区发现结果模块度越高。

4.2 带标签网络的实验比较结果

表2和表3分别给出了在空手道俱乐部（Karate）［23］、海豚社交网络（Dolphin）［24］、大学生 足 球 网 络（Football）［25］、美 国 政 治 书 网 络（Polbooks）［26］、亚马逊网络（Amazon）［27］、引文网络（DBLP）［27］等6个带标签的真实网络上，不同算法所发现社区的重叠NMI值和F1分数实验结果。

表2 在带标签网络上的重叠NMI实验结果Table 2 Experimental results of overlapping NMIon labeled networks

表3 在带标签网络上的F1分数实验结果Table 3 Experimental results ofF1Score on labeled networks

可以看出，在 Karate、Dolphin、Football、Polbooks等真实社区较少的网络上，本文算法LNCA在重叠NMI和F1分数方面明显优于对比算法。由于Amazon和DBLP等网络规模较大，且有很多包含3至10个节点的小规模社区，这些小社区往往被其他规模更大的社区完全覆盖，LNCA经过社区去重处理后忽略了这部分小社区，导致LNCA在Amazon和DBLP等网络上具有较低的重叠NMI值。实际上，LNCA所发现的社区与真实社区匹配程度更高，因此在Karate、Dolphin、Polbooks、DBLP 等网络上 LNCA所得社区发现结果F1分数明显优于对比算法，在Football、DBLP网络上F1分数略低于SLPA算法，优于其他对比算法。

4.3 无标签网络的实验比较结果

表 4 给 出 了 在 Les、Jazz［28］、Usair、Net-Science、Email、Facebook、Power、PGP、Ca-AstroPh等9个无标签网络上，本文算法LNCA与其他6个对比算法结果的扩展模块度EQ的比较情况。

表4 在无标签网络上的模块度实验结果Table 4 Experimental results of modularity on unlabeled networks

实验结果表明，在无标签网络上，LNCA所发现社区的重叠模块度优于DEMON、CPM、Node_Perception、Ego_Networks等算法。在一些网络上LNCA的重叠模块度略低于SLPA，但SLPA算法过程中存在较大随机性，无法得到稳定的社区发现结果，而LNCA通过节点的邻域中心性选择种子节点并通过带重启的局部随机游走扩展种子节点，因此所发现的社区模块度较高且运行结果稳定。

5 结论

本文提出了一种基于邻域连通性的重叠社区发现算法LNCA，用于发现网络中的重叠社区结构。首先，计算每个节点的局部邻域连通熵和邻域中心性cc；选择邻域中心性高的节点作为种子节点，采用带重启的随机游走过程对种子节点进行扩展得到初始社区；最后合并重叠度较大的社区。在6个带真实社区标签的网络和9个无真实社区标签的网络上，对所提算法LNCA与其他6个经典的重叠社区检测算法进行比较实验，结果表明LNCA算法可以较好地发现网络中的真实社区结构。