Complex Networks, Communities, and Clustering: A survey

Abstract

This paper is an extensive survey of literature on complex network communities and clustering. Complex networks describe a wide variety of systems in nature and society, especially systems composed of a large number of highly interconnected dynamical entities. Complex networks, like real networks, can also have community structure. There are several types of methods and algorithms for the detection and identification of communities in complex networks. Several complex networks have the property of clustering or network transitivity. Some of the important concepts in the field of complex networks are small-world and scale-free networks, evolving networks, the relationship between topology and the network’s robustness, degree distributions, clustering, network correlations, random graph models, models of network growth, dynamical processes on networks, etc. Some current areas of research on complex network communities are those on community evolution, overlapping communities, communities in directed networks, community characterization, and interpretation, etc. Many of the algorithms or methods proposed for network community detection through clustering are modified versions of or inspired by the concepts of minimum-cut-based algorithms, hierarchical connectivity-based algorithms, the original Girvan–Newman algorithm, concepts of modularity maximization, algorithms utilizing metrics from information and coding theory, and clique based algorithms.