Distributed Community Detection with the WCC Metric
Distributed Community Detection with the WCC Metric
复制标题
使用 WCC 指标进行分布式社区检测
DOI：
10.1145/2740908.2744715
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
David Dominguez
中科院分区：
文献类型：
--
作者：
Matthew Saltz;Arnau Prat;David Dominguez
近年来，社区检测已成为一个极其活跃的研究领域，研究人员提出了各种新的指标和算法来解决该问题。最近，加权社区聚类（WCC）指标被提出作为一种根据图中三角形的分布来判断社区划分质量的新方法，并且被证明比其他常用指标（例如模块化）产生更好的结果。同一作者后来提出了一种在大图上优化 WCC 的并行算法。在本文中，我们提出了一种新的分布式、以顶点为中心的算法，用于使用 WCC 度量进行社区检测。结果展示了该算法在多达 32 台工作机器和多达 18 亿条边的真实图上的性能和可扩展性。该算法在最大的图上具有最佳的扩展性，在一个多小时内完成了最大的图，据我们所知，它是第一个用于优化 WCC 指标的分布式算法。
Community detection has become an extremely active area of research in recent years, with researchers proposing various new metrics and algorithms to address the problem. Recently, the Weighted Community Clustering (WCC) metric was proposed as a novel way to judge the quality of a community partitioning based on the distribution of triangles in the graph, and was demonstrated to yield superior results over other commonly used metrics like modularity. The same authors later presented a parallel algorithm for optimizing WCC on large graphs. In this paper, we propose a new distributed, vertex-centric algorithm for community detection using the WCC metric. Results are presented that demonstrate the algorithm's performance and scalability on up to 32 worker machines and real graphs of up to 1.8 billion edges. The algorithm scales best with the largest graphs, finishing in just over an hour for the largest graph, and to our knowledge, it is the first distributed algorithm for optimizing the WCC metric.
影响因子：
2.4
作者：
Lancichinetti, Andrea;Fortunato, Santo
通讯作者：
Fortunato, Santo