基于Hadoop框架下的Fast-Newman算法改进

摘要

Fast-Newman算法的复杂程度高,尤其是在计算模块度(Modularity)时,在边数较多的情况下,随着结点数提高,极大的影响着计算速度.为此,本文提出了一种基于Hadoop框架下的改进策略.该策略通过结点-边信息的划分,完成一定程度的分布化,在利用大量mappers的基础上,降低每次迭代时间,从而最终提升计算速度.通过对Zachary网络与随机ego-Facebook部分集的实验对比可以发现,算法加速比与并行序列数量有关.