基于染色的分布式弱连通分量求解算法

社交网络、生物信息网络等链接关系数据呈现爆炸性增加,对亿万个顶点级别的大图处理需求愈加迫切,传统的图算法对单点内存的计算依赖性已经不能满足数据规模急速增长的需求.本文针对图的弱连通分量求解问题,提出了一种快速、可扩展的迭代染色算法CR,并建立了算法的MapReduce模型.最后,在Hadoop平台上,对斯坦福大学社会网络分析实验室提供的四组通联数据进行测试,并和开源的数据挖掘工具箱XRIME提供的算法进行了对比.