复杂网络的重叠社区发现并行算法

摘要：

随着网络规模的快速增长,传统社区发现算法难以处理大规模网络数据和满足复杂网络的可扩展分析需求.本文提出一种适用于大规模复杂网络的重叠社区发现算法PHLink.该算法根据复杂网络的无标度特性将节点建立连边的原因进行分析和归类,用以识别网络中具有重叠性的社区结构,并采用MapReduce计算框架对网络进行分割和冗余存储,减弱了图计算的耦合性,解决了社区发现算法的分布式计算问题.通过真实网络测试,PHLink算法可以大幅度降低边计算的复杂度,对于无标度特性明显的复杂网络提取0.1％的枢纽节点即可节省94％以上的计算量,较传统算法具有较高的稳定性和准确性,并且在Hadoop平台有良好的加速性和伸缩性,可以处理千万级连边规模的大规模复杂网络.

关键词：复杂网络、重叠社区、社区发现、无标度、并行算法、Hadoop

所属期刊栏目：54

分类号：V221.3(飞机构造与设计)

资助基金：国家自然科学基金资助项目61573292,61572407;四川省软科学研究计划资助项目2016ZR0034中铁第一勘察设计院集团有限公司轨道交通工程信息化国家重点实验室开放课题SKLK16-04

在线出版日期：2019-08-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：211-218