摘要
随着大数据时代的到来，网络结构日益复杂，探索复杂网络的社区结构对理解其功能和组织机制具有重要意义。关于社区检测已有大量研究，其中标签传播算法(LPA)具有接近线性的时间复杂度，适用于大规模复杂网络，但其随机性较强，准确性不高。提出基于集体影响力的标签传播算法(CILPA)，用于发现重叠社区结构。CILPA引入集体影响力这一全局指标，融合节点自身信息和网络全局信息重新定义节点重要性，并依此固定节点更新顺序以提升算法稳定性；在标签传播过程中，设计一种标签选择策略，并设置自适应过滤因子，防止错误标签的干扰，从而提高算法的准确性和鲁棒性。最后在不同规模、复杂度及重叠率的人工网络和真实网络上进行实验，结果表明，CILPA的模块度和标准化互信息均优于COPRA、SLPA等主流算法，且标准差更小。说明本方法在重叠社区检测中兼具有效性和稳定性，为大规模复杂网络的重叠社区分析提供了可靠方法。
Abstract
With the advent of the era of big data, network structures are becoming more and more complex, and exploring the community structure of complex networks holds great significance in understanding their function and organization mechanisms. Many studies have been conducted for community detection, among which the label propagation algorithm (LPA) has a near linear time complexity and is applicable for large-scale complex networks. However, it has excessive randomness and relatively low accuracy. This paper proposed a collective influence-based label propagation algorithm (CILPA) for discovering overlapping community structures. CILPA introduced collective influence as a global indicator, redefined the node importance by integrating the node’s own information and global network information, and fixed node update order according to node importance to improve the algorithm’s stability. In the label propagation process, a label selection strategy was designed, and the adaptive filtering factor were set to prevent the interference of wrong labels, thereby improving the accuracy and robustness of the algorithm. Finally, experiments were conducted on artificial and real networks with different scales, complexities, and overlap rates. The results show that the modularity and normalized mutual information of CILPA are superior to those of mainstream algorithms such as COPRA and SLPA, with a smaller standard deviation. This indicates that the proposed method possesses both effectiveness and stability in overlapping community detection, providing a reliable method for the analysis of overlapping communities in large-scale complex networks.
在现实世界的诸多领域，都可以通过复杂网络进行表征[1]，如社交网络[2]、生物网络[3]、科学协作网络[4]等。要分析这些网络，就需要了解其拓扑特征，如小世界特性[5]、无标度特性[6]等。社区结构作为复杂网络的重要属性[7]，近年来已成为复杂网络领域的研究热点，有助于深入挖掘网络蕴含的潜在信息。早期社区检测研究多聚焦于非重叠社区划分[8-9]，但在现实世界中，大部分网络都是重叠网络，即一个节点可能同时属于多个社区，例如，推荐系统（如购物软件的智能推荐功能）[10]、科学协作网络（如学者跨学科研究）、信息网络（如学术论文引文网络）[11]、电网（如家庭与企业配电网络）[12]等。因此，重叠社区检测更具现实意义。
重叠社区检测的算法大致可以分为三类：第一类是基于派系过滤的方法[13]，这类方法虽然能识别重叠社区，但只适用于子图完全连通的网络；第二类是基于线图和边分割的方法[14]，核心思想是利用边而非节点进行分区，但其检测质量不如节点检测方法；第三类是基于模糊聚类的方法[15]，需要提前定义社区个数和模糊聚类的相关参数，这些参数都很难确定最优值。
上述算法在时间和空间上消耗较大，不适用于大规模社交网络结构检测。在大数据时代，随着网络规模持续扩大，网络结构愈发复杂，亟需低时间复杂度的高效算法。标签传播算法（LPA）[16]是由Raghavan等学者提出的一种半监督算法，具有接近线性的时间复杂度，适用于大规模网络的高效社区检测。该算法受流行病传播机制的启发，通过节点标签的迭代传播实现社区检测，直到收敛（具有相同标签的节点构成社区）。COPRA是首个用于重叠社区检测的LPA改进算法[17]，其规定每个节点可以包含多个社区标签，并为每个标签定义隶属度，在传播过程中根据邻居节点信息更新标签及隶属度，但该算法认为所有节点的重要性是相同的，一定程度上降低了检测精度，易产生小社区。SLPA引入了“speaker-listener”规则[18]，给每个节点分配内存用来储存历史标签，最后根据内存里的历史标签确定最终的社区标签，并通过参数r删除低隶属度标签，但r值的确定具有较强主观性。MGA算法通过分析标签传播的Newman模块化增益函数[19]，提出加速模块化增益检测方法，但受模块化分辨率限制，算法存在局限性。Zhao等[20]提出基于图压缩和标签传播的大规模社区检测方法，通过压缩低度数节点并搜索社区中心，根据相似性等信息检测社区结构，但社区中心的搜索结果对最终检测效果影响显著。Qiong等[21]提出基于边界节点的标签传播算法LBN，通过核心节点给边界节点赋予权值并进行社区划分，但边界节点的计算增加了时间复杂度。LPANNI定义节点相似度和邻居节点影响力[22-23]，提出基于邻居节点影响力和历史标签偏好的更新策略，但在小规模网络中效果欠佳。NI-LPA基于节点自身属性定义节点重要性[24]，依据重要性进行标签传播，虽提高了准确性，但只考虑了节点的局部信息，没有充分考虑整个网络的拓扑信息。
针对上述问题，本文提出改进的标签传播算法CILPA。引入集体影响力指标衡量节点的重要性，综合考虑节点自身信息和全局信息定义节点重要性，提升重叠社区检测准确性；设计新型节点标签更新策略，在保证准确性的同时，维持了低时间复杂度；定义自适应过滤因子，删除不重要标签。通过在真实网络和LFR基准网络上进行实验，验证了此算法兼具检测重叠社区的有效性和稳定性。
1 基于集体影响力的标签传播算法
1.1 基本定义
给定包含n个节点的无向图G=（V，E），其中V为节点集，V={v1，v2，···，vn}，E为边集，E={（vi，vj）|1≤i≠j≤n}。A是图V的邻接矩阵。重叠社区检测旨在将V中所有的节点分到m个社区中，得到社区划分P={C1，C2，···，Cm}，每个社区之间可以互相连接，同一社区内节点连接紧密，不同社区间节点连接稀疏，且每个节点可以同时属于多个社区，即。
1.2 核心指标定义
1）集体影响力
集体影响力（collective influence，CI）是量化节点影响力的全局指标[25]。节点i的集体影响力记为CIl（i），定义为节点i与其l阶邻居的节点度之和的乘积：
(1)
式中：ki是节点i的度；d（i，j）是节点i和j的最短距离。CI通过l阶邻居描述节点的重要性。等式右边的和包含了围绕中心节点i的球表面上的节点的贡献度，每个节点的权重都是k-1。这表明，即使节点自身度不高，若其周围存在大量连接，仍可能具有较高影响力，如图1所示。
图1集体影响力示意图
Fig.1Collective influence
2）节点重要性
节点重要性用于衡量标签传播过程中衡量节点所携带信息的传播优先级。一个节点的重要性越高，该节点发送的标签在传播阶段的优先级就越高。节点重要性也可以反映节点成为社区中心的概率。仅通过节点度来度量节点重要性存在局限性，因为具有相同度的节点在复杂网络中可能不会发挥相同的作用。现有研究[23-24]考虑节点邻域信息来量化节点重要性，但仍局限于局部视野。CI作为全局指标，能更全面反映拓扑特征，量化节点重要性。由于每个节点的CI会随参数l的增加而增加，需进行归一化处理。本文将节点度和归一化的集体影响力结合，重新定义节点重要性：
(2)
式中〈CI〉是所有节点集体影响力的均值。
1.3 CILPA算法
1）初始化
针对重叠社区检测需求，每个节点对应一个标签集。标签集里的每个元素为一个标签对，包含标签和对应的隶属度，定义如下：
(3)
式中：c是节点v的一个社区标签；b是标签的隶属度，既表示节点属于该社区的概率，也代表该标签的传播优先级。
在初始化时，将每个节点视为一个独立社区，为每个节点的标签赋予一个隶属度，初始化时所有节点的隶属度设置为节点重要性的值，即Lv={（v，NIv）}。
同时，为了缓解传播过程中随机选择更新节点得出结果的不稳定性，将所有节点按重要性进行降序排序，并更新标签，得到序列Nsort。
2）传播策略
为了降低算法的复杂度，同时减少不重要标签对结果的干扰，借鉴DLPA[30]的做法，在传播过程中，仅传播每个节点隶属度最大的标签，定义主导标签为
(4)
采取异步更新模式避免震荡问题。在第t次迭代中，节点标签通过邻居节点第t-1次迭代的主导标签（未更新邻居）和第t迭代的主导标签（已更新邻居）共同更新，公式如下：
(5)
式中，N1（v）是v的邻居中未更新的节点集，N2（v）是v的邻居中已更新的节点集。
在接受邻居所有信息后，得到一个新的标签集，此时标签集里可能会有干扰信息，需要对这个标签集进行过滤。由于固定参数难以确定，选择自适应的过滤因子，删除隶属度小于ρ的标签，并对标签集进行归一化处理，得到更新后的标签集，并从中提取隶属度最大的标签作为主导标签，用于下次更新。
按Nsort中的节点顺序进行标签更新与传播，具体更新策略如下：
a.对于Nsort中的每个节点v，从其所有邻居接收主导标签信息，并按公式（5）更新v的标签集Lv。
b.将更新后的标签集Lv进行过滤，删除隶属度小于ρ的标签，得到新的标签集Lu。
c.对Lu进行归一化处理，找到隶属度最大的标签，更新v的主导标签domv。
d.如果domv不变，则终止迭代；否则，重复步骤a~c。
标签传播完成后，网络中每个节点均保留标签集信息，最后再将含有相同标签的节点划分到同一个社区，得到社区划分P。
标签传播过程如图2所示，黑色节点为待更新节点，接收来自邻居节点a、b、c的主导标签信息（图中加粗部分）得到一个标签集，然后将其过滤后进行归一化处理，计算ρ=0.25，删除不满足条件的标签b，得到最终标签集，其中c为主导标签，用于下一次传播。
图2标签传播过程
Fig.2Label propagation process
3）算法描述
2 实验与分析
2.1 评价指标
1） 标准化互信息（NMI）
Danon等[26]提出标准化互信息（normalized mutual information，NMI）用于评价算法得到的社区与真实网络社区分布的相似程度。然而NMI在部分场景下可能会高估两个社区划分的相似性，例如：当一个多社区划分与一个单社区划分存在完全重合的社区时，NMI值可能偏高。McDaid等[27]提出了一种改进的标准化互信息（NMImax），可有效解决该问题，定义如下：
(6)
式中：X为算法得到的社区划分；Y为真实网络社区划分；H（X）和H（Y）分别为随机变量X、Y的信息熵；H（X|Y）为条件熵。当算法得到的社区结果与真实划分完全一致时，则NMImax=1；当两个社区完全独立时，NMImax=0。
2）模块度
在真实网络中，正确的社区划分通常是未知的，为了评价社区划分的优劣，Newman等提出了模块度的概念。优质社区划分应满足社区内部节点连接稠密、社区间连接稀疏，此时模块度值更大。这是针对非重叠社区的模块度定义。Nicosia等[28]将该模块度扩展到了重叠社区检测，定义如下：
(7)
式中：m是网络中边的个数；Oi是节点i属于的社区个数；A是网络的邻接矩阵。
2.2 对比算法和实验数据
1）对比算法
本文选择了5种主流重叠社区检测算法作为对比算法，分别为COPRA、SLPA、CPM、LPANNI、ENDNTM，各比较算法的参数均参考原始文献设置。
2）真实数据
选择5个不同规模的真实数据集，详细参数见表1。
表1真实网络参数表
Tab.1Parameters of real network
3）人工合成数据
由于真实数据有限且多数真实网络的社区划分未知，本文采用LFR模型生成基准网络[29]。该模型可以通过调节不同参数生成不同特性的人工网络。主要参数包括：N（节点数，反映网络规模）；k（平均度，通常设为10，以接近真实社会网络）；μ（社团内部连接强度系数，值越大代表连接越弱）；Cmin和Cmax（社团规模上下限）；on（网络重叠节点占比）；om（重叠节点最多属于几个社区），on和om共同决定复杂网络中社区的重叠度。
为了验证算法在不同类型网络中的有效性，用LFR生成4种不同性质的人工网络，参数见表2。通过改变N、μ、om和on，验证算法在不同规模、复杂度、社区重叠度网络中的有效性。
表2LFR网络参数表
Tab.2Parameters of LFR network
2.3 结果分析
1）参数l的确定
在CILPA中引入集体影响力，由公式（1）可知，CI表达式中的参数l需合理确定。l越大，CI包含的拓扑信息越丰富，有助于提高算法准确性，但同时也会增加时间复杂度。为在准确性和时间复杂度之间取得平衡，设置实验检验不同l值对社区检测的影响，并确定合适的l值。实验在LFR1网络上进行，结果如图3所示。
图3CILPA在不同l下的结果
Fig.3Results of CILPA under different l values
由图3可以看出，当N=1 000时，在不同om值下，NMImax在l=3或l=4的时候达到顶峰，l＞4后趋于平稳或者小幅度下降；当N=5 000时，不同om值下，NMImax在l=4处达到顶峰。综合不同规模和复杂度网络来看，更丰富的拓扑信息确实能够提高算法的准确性，但过大的l也可能降低精度并增加了时间复杂度。
根据实验结果，当l=4时，算法效果最好，既能准确检测重叠社区，又能维持较低的时间复杂度。
2）真实网络实验结果
在5个不同规模的真实网络中，从准确性（模块度均值Qavg）和稳定性（模块度标准差Qstd）两方面对比五种算法。图4为不同网络中模块度均值的对比结果。可以看到，CILPA的模块度值一直较高。
图4真实网络中模块度均值的比较结果
Fig.4Comparison result of average modularity in real networks
表3列出各算法的模块度均值和标准差。可以看出，CILPA在多数网络中的精度和稳定性方面都表现较好；ENDNTM在Email网络中表现更好；LPANNI和SLPA整体表现处于上游水平，但CILPA的Qavg还是更高。CPM的稳定性也表现很好，但精度方面是5种算法中最差的。综合来看，CILPA在真实网络中发现重叠社区的能力更好，并兼具准确性和稳定性。
表3真实网络中的结果
Tab.3Result on real network
3） LFR实验结果分析
首先通过改变μ值调整网络复杂度。μ是混合参数，表示社区内节点与其他社区的连接强度，μ值越大，代表网络越复杂，社区的边界越模糊。图5结果显示，随着μ值的增加，每个算法的NMImax值均有下降。其中，CILPA在μ≤0.1时，NMImax接近于1，且始终优于其他算法；COPRA在μ＞0.1后性能迅速下降。这表明在较为复杂的网络中，CILPA能够更有效地检测重叠社区。
图5不同复杂度网络下各算法比较结果
Fig.5Comparison results of algorithms on networks with different complexities
其次，通过改变on（重叠节点占比）和om（重叠节点隶属社区数）来调整网络的重叠度。随着om和on的增加，网络中的重叠社区结构变得越来越复杂。图6显示，所有算法的NMImax都随着om和on的增加而有所下降。在om从2增加的8的过程中，CILPA下降幅度相对较小。在N=10 000时，COPRA和SLPA在om=8 时NMImax几乎降为了0，而LPANNI、CPM和CILPA虽然也有所下降，但仍在可接受范围内，其中CILPA表现最优。而随着on的增加，所有算法识别重叠社区的能力都有所下降。综合来看，LPANNI、CPM和CILPA的效果是比较好的，其中，CILPA的效果更好。
同时，综合图5、图6的结果来看，在规模更大、结构更复杂的网络中，对比其他算法，CILPA仍能有效准确识别重叠社区。
图6不同重叠度下各算法的比较结果
Fig.6Comparison results of algorithms under different overlapping degrees
3 结语
本文提出了一种基于集体影响力的重叠社区检测算法CILPA，该算法保持了LPA的低时间复杂度，适用于大规模复杂网络的重叠社区检测。CILPA通过集体影响力衡量节点重要性，综合考虑节点自身信息和全局信息，并以此来改进标签传播过程，显著提高了重叠社区检测的准确性。此外，算法引入自适应过滤因子以删除不重要标签，大大提高了检测精度。通过调节CI中的参数l，可在准确性与时间复杂度之间取得良好平衡，实验表明l=4适用于多数网络。
在人工和真实网络上的实验表明，CILPA能够识别出最接近真实划分的社区结构，在精度和稳定性方面均具优势。然而，本文提出的CILPA目前只适用于静态无权网络。未来研究将把该算法进一步推广至加权网络以及动态网络的重叠社区检测场景。
