One of the most widely studied problem in mining and analysis of complex networks is the detection of community structures. The problem has been extensively studied by researchers due to its high utility and numerous applications in various domains. Many algorithmic solutions have been proposed for the community detection problem but the quest to find the best algorithm is still on. More often than not, researchers focus on developing fast and accurate algorithms that can be generically applied to networks from a variety of domains without taking into consideration the structural and topological variations in these networks. In this paper, we evaluate the performance of different clustering algorithms as a function of varying network topology. Along with the well known LFR model to generate benchmark networks with communities,we also propose a new model named Naive Scale Free Model to study the behavior of community detection algorithms with respect to different topological features. More specifically, we are interested in the size of networks, the size of community structures, the average connectivity of nodes and the ratio of inter-intra cluster edges. Results reveal several limitations of the current popular network clustering algorithms failing to correctly find communities. This suggests the need to revisit the design of current clustering algorithms that fail to incorporate varying topological features of different networks.
A more recent work in evaluating network clustering algorithms was performed by Wang @cite_40 . They proposed a procedure-oriented framework for benchmarking to evaluate different community detection approaches in an attempt to find better algorithms. Although their objectives were clearly different from what we have proposed in this paper, one of their findings also pointed towards the varying performance of algorithms for different networks.
@cite_40
2296746822
Revealing the latent community structure, which is crucial to understanding the features of networks, is an important problem in network and graph analysis. During the last decade, many approaches have been proposed to solve this challenging problem in diverse ways, i.e. different measures or data structures. Unfortunately, experimental reports on existing techniques fell short in validity and integrity since many comparisons were not based on a unified code base or merely discussed in theory. We engage in an in-depth benchmarking study of community detection in social networks. We formulate a generalized community detection procedure and propose a procedure-oriented framework for benchmarking. This framework enables us to evaluate and compare various approaches to community detection systematically and thoroughly under identical experimental conditions. Upon that we can analyze and diagnose the inherent defect of existing approaches deeply, and further make effective improvements correspondingly. We have re-implemented ten state-of-the-art representative algorithms upon this framework and make comprehensive evaluations of multiple aspects, including the efficiency evaluation, performance evaluations, sensitivity evaluations, etc. We discuss their merits and faults in depth, and draw a set of take-away interesting conclusions. In addition, we present how we can make diagnoses for these algorithms resulting in significant improvements.