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.
In this paper we discuss some problematic aspects of Newman and Girvan’s modularity function Q N . Given a graph G, the modularity of G can be written as Q N = Q f − Q 0, where Q f is the intracluster edge fraction of G and Q 0 is the expected intracluster edge fraction of the null model, i.e., a randomly connected graph with same expected degree distribution as G. It follows that the maximization of Q N must accomodate two factors pulling in opposite directions:Q f favors a small number of clusters and Q 0 favors many balanced (i.e., with approximately equal degrees) clusters. In certain cases the Q 0 term can cause overestimation of the true cluster number; this is the opposite of the well-known underestimation effect caused by the “resolution limit” of modularity. We illustrate the overestimation effect by constructing families of graphs with a “natural” community structure which, however, does not maximize modularity. In fact, we show there exist graphs G with a “natural clustering” V of G and another, balanced clustering U of G such that (i) the pair (G, U) has higher modularity than (G, V) and (ii) V and U are arbitrarily different. Detecting community structure is fundamental for uncovering the links between structure and function in complex networks and for practical applications in many disciplines such as biology and sociology. A popular method now widely used relies on the optimization of a quantity called modularity, which is a quality index for a partition of a network into communities. We find that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined. This finding is confirmed through several examples, both in artificial and in real social, biological, and technological networks, where we show that mod ularity optimization indeed does not resolve a large number of modules. A check of the modules obtained through modularity optimization is thus necessary, and we provide here key elements for the assessment of the reliability of this community detection method. Complex networks became a very important tool in machine learning field, helping researchers to investigate and mine data. They can model real dynamic networks, aiding to unveil information's about the systems they model. Communities are notable groups that may exist in a complex network and the community detection problem is the focus of attention of many researchers. The igraph library implements a good set of community detection algorithms, allowing researchers to easily apply them to data mining tasks. But each algorithm uses a different approach, leading to different performances. In this paper, the community detection algorithms implemented in the igraph library are investigated and ranked according to their performances in a set of different scenarios. Results show walktrap and multi-level got the highest scores while leading eigenvector and spinglass got the lowest ones. These findings are an important contribution for aiding researchers to select or discard algorithms in their own experiments using igraph library. 