大规模复杂网络社区并行发现算法

发布时间：2018-06-28 10:55

本文选题：复杂网络 + 社区发现　；参考：《计算机学报》2017年03期

【摘要】：随着网络规模的不断扩大,传统社区发现算法已无法有效和高效地处理大规模网络数据.基于Spark分布式图计算模型,提出大规模复杂网络社区并行发现算法DBCS(Discovering Big Community on Spark).算法利用基于模块度的聚类思想,首先计算出节点对之间的模块度增量,然后迭代查找出所有模块度增量最大的节点对,对所有节点对进行合并操作,并更新节点对之间的模块度增量,进而实现大规模复杂网络社区识别.大量真实复杂网络与仿真网络数据集上的实验结果表明:DBCS算法能有效地解决传统社区发现算法无法处理的大规模复杂网络社区划分问题,百万级以上节点处理时间约为4min,是Hadoop平台下并行发现算法运行时间的1/20,社区识别准确率比传统社区发现算法提高了7.4%.
[Abstract]:With the expansion of network scale, traditional community discovery algorithms can not deal with large scale network data effectively and efficiently. Based on the Spark distributed graph computing model, a parallel discovery algorithm DBCS (Discovering Big Community on spark) is proposed. Based on the idea of modular degree clustering, the algorithm first calculates the module degree increment between node pairs, then iterates to find out the node pair with the largest module degree increment, and then combines all node pairs. The modularity increment between node pairs is updated to realize large scale complex network community identification. The experimental results on a large number of real complex network and simulation network data sets show that the solution to the problem of large-scale complex network community partitioning which can not be handled by the traditional community discovery algorithm can be effectively solved by using the "DBCS" algorithm. The processing time of multi-level nodes is about 4 mins, which is 1 / 20 of the running time of parallel discovery algorithm in Hadoop platform. The accuracy of community recognition is 7.4g higher than that of traditional community discovery algorithm.
【作者单位】：成都信息工程大学信息安全工程学院;西南交通大学信息科学与技术学院;成都信息工程大学管理学院;电子科技大学大数据研究中心;广西师范学院科学计算与智能信息处理广西高校重点实验室;四川大学计算机学院;
【基金】：国家自然科学基金(61100045,61165013) 高等学校博士学科点专项科研基金(20110184120008) 教育部人文社会科学研究规划基金(15YJAZH058);教育部人文社会科学研究青年基金(14YJCZH046) 四川省教育厅资助科研项目(14ZB0458) 科学计算与智能信息处理广西高校重点实验室开放课题(GXSCIIP201407)资助
【分类号】：O157.5

【相似文献】