计算机应用研究

作者：刘东江,黎建辉,

单位：1.中国科学院计算机网络信息中心,北京100190；2.中国科学院大学,北京100190；

关键词：社区发现,Spark,并行算法,图聚类,图数据,

基金：国家重点研发计划资助项目(2016YFB1000600)；中国科学院战略性先导科技专项资肋项目(XDA06010307)；；

针对大规模图数据顶点聚类进行研究，提出了一种基于Spark的并行社区发现算法，其在基于极值优化的串行社区发现算法的基础上设计而成。此外还针对该串行算法在簇调整时因选择顶点数量过少而影响算法运行效率的问题，提出了一种多个顶点选择方法。该方法会计算一个阈值并发现所有适应度值小于该阈值的顶点，作为被选择的顶点；由于阈值是基于所有顶点的适应度值计算出来的，为了避免非常大的适应度值对阈值造成的影响该方法会限制被选择顶点的数量，若被选择的顶点过多，算法只保留其中的一部分。同时，还提出了一种顶点过滤方法，其可以有效减少图数据的数据量。实验表明，提出算法的运行时间明显短于比较的其他基于Spark的并行化社区发现算法，可以发现其运行速度相对较快。

来源：2020年第8期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2020年第8期