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

摘要

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