Ensemble Clustering for Graphs: Comparisons and Applications
arXiv:1903.08012 · doi:10.1007/s41109-019-0162-z
Abstract
We recently proposed a new ensemble clustering algorithm for graphs (ECG) based on the concept of consensus clustering. We validated our approach by replicating a study comparing graph clustering algorithms over benchmark graphs, showing that ECG outperforms the leading algorithms. In this paper, we extend our comparison by considering a wider range of parameters for the benchmark, generating graphs with different properties. We provide new experimental results showing that the ECG algorithm alleviates the well-known resolution limit issue, and that it leads to better stability of the partitions. We also illustrate how the ensemble obtained with ECG can be used to quantify the presence of community structure in the graph, and to zoom in on the sub-graph most closely associated with seed vertices. Finally, we illustrate further applications of ECG by comparing it to previous results for community detection on weighted graphs, and community-aware anomaly detection.
arXiv comment9 pages, 10 figures
References in corpus (17)
- Fast unfolding of communities in large networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Finding community structure in very large networks
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Statistical Mechanics of Community Detection
- Community detection in networks: A user guide
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- Overlapping Community Detection in Networks: the State of the Art and Comparative Study
- Consensus clustering in complex networks
- A Comparative Analysis of Community Detection Algorithms on Artificial Networks
- Comparative Evaluation of Community Detection Algorithms: A Topological Approach
- Towards realistic artificial benchmark for community detection algorithms evaluation