基于标签传播的可并行复杂网络重叠社区发现算法

摘要：

针对复杂网络重叠社区发现算法中预先输入参数的局限性以及标签冗余等缺点,提出一种改进的复杂网络重叠社区发现算法,最小极大团标签传播算法MMCLPA (minimal maximal clique labelpropagation algorithm).该算法通过寻找网络中的最小极大团(MMC)并对每个MMC中的节点赋予相同的标签来减少冗余标签,提高算法的稳定性,标签更新时采用亲密度作为权重并由MMC构成的核心节点群向四周扩散,后期处理采用自适应阈值方式克服了预先输入参数对未知网络的局限性.通过仿真和真实网络数据与其他几种有代表性的社区发现算法的实验对比分析,表明MMCLPA算法提高了对混合参数u的容忍度以及算法的鲁棒性.利用分布式计算模型MapReduce和Hadoop云平台实现了MMCLPA算法的并行化,实验结果表明并行化的MMCLPA算法在百万级节点的复杂网络大数据中拥有单机系统下近似的社区发现质量以及良好的可扩展性.

关键词：复杂网络、社区发现、重叠社区、标签传播、并行计算

所属期刊栏目：46

分类号：TP301.6;O157.5;S

资助基金：国家自然科学基金;国家科技支撑计划;国家高技术研究发展计划（863计划）;广东省自然基金项目;广东省科技重大专项

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

页码：212-227