基于Spark的并行社区发现算法

摘要

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