Comparison and Benchmark of Graph Clustering Algorithms

Abstract

Graph clustering is widely used in analysis of biological networks, social networks and etc. For over a decade many graph clustering algorithms have been published, however a comprehensive and consistent performance comparison is not available. In this paper we benchmarked more than 70 graph clustering programs to evaluate their runtime and quality performance for both weighted and unweighted graphs. We also analyzed the characteristics of ground truth that affects the performance. Our work is capable to not only supply a start point for engineers to select clustering algorithms but also could provide a viewpoint for researchers to design new algorithms.

arXiv comment32 pages, 4 figures

References in corpus (26)

• Scikit-learn: Machine Learning in Python
• Fast unfolding of communities in large 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
• Community detection algorithms: a comparative analysis
• Statistical Mechanics of Community Detection
• Link communities reveal multiscale complexity in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Detect overlapping and hierarchical community structure in networks
• Extracting the hierarchical organization of complex systems
• Community detection in networks with positive and negative links
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Detecting highly overlapping community structure by greedy clique expansion
• A sequential algorithm for fast clique percolation
• Local resolution-limit-free Potts model for community detection
• EdMot: An Edge Enhancement Approach for Motif-aware Community Detection
• Computing communities in large networks using random walks (long version)
• Detecting Communities in Networks by Merging Cliques
• Hierarchical Graph Clustering using Node Pair Sampling
• A Streaming Algorithm for Graph Clustering