Distributed Community Detection with the WCC Metric
arXiv:1411.0557
Abstract
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 vertices. The algorithm scales best with the largest graphs, and to our knowledge, it is the first distributed algorithm for optimizing the WCC metric.
arXiv comment6 pages, 6 figures
References in corpus (11)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Finding community structure in very large networks
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Resolution limit in community detection
- Community detection algorithms: a comparative analysis
- Link communities reveal multiscale complexity in networks
- Graph spectra and the detectability of community structure in networks
- Communities and bottlenecks: Trees and treelike networks have high modularity
- Parallel Heuristics for Scalable Community Detection