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.
Sousa and Zhao @cite_14 empirically compared different clustering algorithms using synthetic and real networks. The objective of their work was to evaluate the performance of different algorithms. They found that the performance of some algorithms is effected by the number of nodes in a network. The artificial networks they generated were with a maximum node size of 100 which makes it difficult to generalize the results to large networks with hundreds and thousands of nodes. They use Modularity Q @cite_20 in part, to evaluate the quality of clustering algorithms which is shown to have problems with underestimation @cite_37 and overestimation @cite_59 of the number of communities when maximizing modularity.
@cite_59 @cite_37 @cite_14 @cite_20
2146191525 1967022297 2094934391 2247411266
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. Communities of vertices within a giant network such as the World-Wide Web are likely to be vastly smaller than the network itself. However, Fortunato and Barth ' e lemy have proved that modularity maximization algorithms for community detection may fail to resolve communities with fewer than @math edges, where @math is the number of edges in the entire network. This resolution limit leads modularity maximization algorithms to have notoriously poor accuracy on many real networks. Fortunato and Barth ' e lemy's argument can be extended to networks with weighted edges as well, and we derive this corollary argument. We conclude that weighted modularity algorithms may fail to resolve communities with fewer than @math total edge weight, where @math is the total edge weight in the network and @math is the maximum weight of an inter-community edge. If @math is small, then small communities can be resolved. Given a weighted or unweighted network, we describe how to derive new edge weights in order to achieve a low @math , we modify the CNM'' community detection algorithm to maximize weighted modularity, and show that the resulting algorithm has greatly improved accuracy. In experiments with an emerging community standard benchmark, we find that our simple CNM variant is competitive with the most accurate community detection methods yet proposed. Many networks, indifferent of their function and scope, converge to a scale-free architecture in which the degree distribution approximately follows a power law. Meanwhile, many of those scale-free networks are found to be naturally divided into communities of densely connected nodes, known as community structure. Finding this community structure is a fundamental but challenging topic in network science. Since Newman's suggestion of using modularity as a measure to qualify the strength of community structure, many efficient methods that find community structure based on maximizing modularity have been proposed. However, there is a lack of approximation algorithms that provide provable quality bounds for the problem. In this paper, we propose polynomial-time approximation algorithms for the modularity maximization problem together with their theoretical justifications in the context of scale-free networks. We prove that the solutions of the proposed algorithms, even in the worst-case, are optimal up to a constant factor for scale-free networks with either bidirectional or unidirectional links. Even though our focus in this work is not on designing another empirically good algorithms to detect community structure, experiments on real-world networks suggest that the proposed algorithm is competitive with the state-of-the-art modularity maximization algorithm. Many social networks and complex systems are found to be naturally divided into clusters of densely connected nodes, known as community structure (CS). Finding CS is one of fundamental yet challenging topics in network science. One of the most popular classes of methods for this problem is to maximize Newman's modularity. However, there is a littleunderstood on how well we can approximate the maximum modularity as well as the implications of finding community structure with provable guarantees. In this paper, we settle definitely the approximability of modularity clustering, proving that approximating the problem within any (multiplicative) positive factor is intractable, unless P = NP. Yet we propose the first additive approximation algorithm for modularity clustering with a constant factor. Moreover, we providea rigorous proof that a CS with modularity arbitrary close to maximum modularity QOPT might bear no similarity to the optimal CS of maximum modularity. Thus even when CS with near-optimal modularity are found, other verification methods are needed to confirm the significance of the structure.