Graph clustering is the task of identifying dense sub-graphs of a given graph such that these sub-graphs are sparsely interconnected. In this paper, the authors conduct an experimental evaluation of greedy graph clustering algorithms. First, the problem (density-constrained clustering) and its background are briefly introduced. Second, two greedy algorithms are presented. The first one is the greedy merge (GM) algorithm, which greedily merges two clusters. The second one is the greedy vertex moving (GVM) algorithm, which allows vertices to move to another cluster to improve objective function. Then several measures are applied to compare GM and GVM algorithms, including intercluster density, balancedness, cluster size distribution, and effectiveness of different objective functions. The GVM algorithm is also compared with several reference algorithms. In the end, the GVM and multilevel modularity (ML-MOD) algorithms are employed to compare different objective functions.

Graph clustering is very important to the modern Internet, including uses such as online shopping, social network analysis, and link prediction; it is a popular research area. Through various experiments, the authors show advantages and disadvantages of different clustering algorithms. The results of this paper are interesting and practical, which make them useful to software developers and algorithm researchers; they can serve as a guideline.