基于高领导力种子扩展的有向网络重叠社区发现研究.pdf

摘要

随着信息技术的革新与发展，复杂网络对于设计和优化复杂系统、深入探

讨网络结构演化具有愈发重要的意义。社区结构作为复杂网络的基本特征，能

够挖掘网络中的潜在拓扑结构和动态演变规律。因此，近年来涌现出大量的社

区检测算法。其中比较典型的是局部扩展方法，仅需部分网络信息可发现重叠

社区结构，但存在种子质量参差不齐、算法效率低等问题；特别地，真实网络

中边的方向和权重信息具有极高的利用价值，而多数算法局限于无向无权网络

社区结构分析，忽略了边信息潜藏的关系结构。因此，结合局部扩展方法存在

的不足，本文引入了边的方向和权重信息，并合理定义过程指标和评估标准，

提出了基于高领导力种子扩展的有向网络重叠社区发现算法。主要研究内容如

下：

（1）为解决局部扩展方法中存在的缺陷和方向信息考虑不足问题，本文提

出基于高领导力种子扩展的有向网络重叠社区发现算法（LSEDC）。首先，本

文综合考虑了节点局部信息和全局信息并融入连边方向性，选取具有高领导力

和信息传输能力的种子作为社区扩展的起点；其次，提出了基于k阶邻域跟随

度和密度最大化原则的种子社区形成策略，以精准挖掘社区核心；随后，采取

社区邻居层扩展方式进行节点聚集，并在导率驱动下通过节点移动修正与社区

的隶属关系；最后，通过分配自由节点，合并高度重叠社区进行社区再优化，

得到最终划分结果。通过在真实网络和LFR基准网络上进行对比实验，验证了

所提算法能够有效改善种子质量和分布情况，并提高了有向网络重叠社区发现

结果的准确性和稳定性。

（2）为提高有向网络社区发现的效率并扩展至加权网络，本文进一步考虑

了连边权重，并引入基于Hadoop的MapReduce计算框架，提出基于高领导力种

子扩展的有向加权网络并行化重叠社区发现算法（P-DWLS）。该方法可以精准

度量有向加权网络中的节点领导力，筛选最大权值点作为候选种子节点，并行

式形成种子社区和邻居层扩展，以加权导率和加权隶属度为指导修正节点位置

和优化社区。实验表明，P-DWLS算法在提高了算法效率的同时，能够在有向

加权网络上发现高质量社区结构，且具有较高的通用性和灵活性，从而验证了

研究工作的合理性及有效性。

关键词：重叠社区发现；有向网络；局部扩展；高领导力种子；MapReduce

I

Abstract

Withtheinnovationanddevelopmentofinformationtechnology,complex

networkshavebecomeincreasinglycrucialfordesigningandoptimizingcomplex

systemsandprofoundlyexploringtheevolutionofnetworkstructures.Asa

fundamentalfeatureofcomplexnetworks,communitystructurecanexplorenetworks

potentialtopologyanddynamicevolutionlaws.Therefore,manycommunitydetection

algorithmshaveemergedinrecentyears.Amongthem,themoretypicalisthelocal

extensionmethod,whichcandiscovertheoverlappingcommunitystructurewithonly

partialnetworkinformation,butthereareproblemssuchasunevenseedqualityand

lowefficiencyofthealgorithm;inparticular,thedirectionandweightinformationof

edgesintherealnetworkisofgreatvaluetoexploit,