A Distributed Infomap Algorithm for Scalable and High-Quality Community Detection
A Distributed Infomap Algorithm for Scalable and High-Quality Community Detection
复制标题
DOI：
10.1145/3225058.3225137
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
Jianping Zeng;Hongfeng Yu
中科院分区：
文献类型：
--
作者：
Jianping Zeng;Hongfeng Yu
社区检测对于各种图形分析应用是必不可少的。Infomap是一种能够实现高质量社区的图聚类算法。然而，在大型图表上有效地应用Infomap仍然是一个非常具有挑战性的问题。通过分析Infomap的通信和负载模式，利用分布式代理划分和分发方法，提出了一种新的启发式策略，在分布式环境下从图的顶点仔细协调社区构成，并实现了分布式聚类算法的收敛。我们使用MPI(消息传递接口)实现了我们的优化算法，它可以方便地应用或扩展到大规模分布式计算系统中。我们分析了算法的正确性，并进行了深入的实验研究，以考察分布式算法的通信和计算开销，这在以前的工作中是没有表现出来的。在大规模真实数据集上的实验结果证明了该分布式Infomap算法的可扩展性和正确性。
Community detection is essential to various graph analysis applications. Infomap is a graph clustering algorithm capable of achieving high-quality communities. However, it remains a very challenging problem to effectively apply Infomap on large graphs. By analyzing communication and workload patterns of Infomap and leveraging a distributed delegate partitioning and distribution method, we develop a new heuristic strategy to carefully coordinate the community constitution from the vertices of a graph in a distributed environment, and achieve the convergence of the distributed clustering algorithm. We have implemented our optimized algorithm using MPI (Message Passing Interface), which can be easily employed or extended to massively distributed computing systems. We analyze the correctness of our algorithm, and conduct an intensive experimental study to investigate the communication and computation cost of our distributed algorithm, which has not shown in previous work. The results demonstrate the scalability and the correctness of our distributed Infomap algorithm with large-scale real-world datasets.