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.

32 pages, 4 figures

References in corpus (17)

• Fast unfolding of communities in 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
• Statistical Mechanics of Community Detection
• 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
• A sequential algorithm for fast clique percolation
• EdMot: An Edge Enhancement Approach for Motif-aware Community Detection
• Detecting Communities in Networks by Merging Cliques
• A Streaming Algorithm for Graph Clustering