Parallel Toolkit for Measuring the Quality of Network Community Structure
arXiv:1507.05492 · doi:10.1109/ENIC.2014.26
Abstract
Many networks display community structure which identifies groups of nodes within which connections are denser than between them. Detecting and characterizing such community structure, which is known as community detection, is one of the fundamental issues in the study of network systems. It has received a considerable attention in the last years. Numerous techniques have been developed for both efficient and effective community detection. Among them, the most efficient algorithm is the label propagation algorithm whose computational complexity is O(|E|). Although it is linear in the number of edges, the running time is still too long for very large networks, creating the need for parallel community detection. Also, computing community quality metrics for community structure is computationally expensive both with and without ground truth. However, to date we are not aware of any effort to introduce parallelism for this problem. In this paper, we provide a parallel toolkit to calculate the values of such metrics. We evaluate the parallel algorithms on both distributed memory machine and shared memory machine. The experimental results show that they yield a significant performance gain over sequential execution in terms of total running time, speedup, and efficiency.
arXiv comment8 pages; in Network Intelligence Conference (ENIC), 2014 European
References in corpus (14)
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Fast algorithm for detecting community structure in networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Link communities reveal multiscale complexity in networks
- Detecting the overlapping and hierarchical community structure of complex networks
- Community Detection via Maximization of Modularity and Its Variants
- A New Metric for Quality of Network Community Structure
- Towards Linear Time Overlapping Community Detection in Social Networks
- LabelRankT: Incremental Community Detection in Dynamic Networks via Label Propagation