Community Detection in Random Networks

In recent years, the problem of detecting communities in networks has received a large amount of attention, with important applications in the social and biological sciences, among others (Fortunato, 2010). The vast majority of this expansive literature focuses on developing realistic models of (random) networks (Albert and Barabási, 2002; Barabási and Albert, 1999), on designing methods for extracting communities from such networks (Girvan and Newman, 2002; Newman, 2006; Reichardt and Bornholdt, 2006) and on fitting models to network data (Bickel et al., 2011). The underlying model is that of graph G (E,V), where E is the set of edges and V is the set of nodes. For example, in a social network, a node would represent an individual and an edge between two nodes would symbolize a friendship or kinship of some sort shared by these two individuals. In the literature just mentioned, almost all the methodology has concentrated on devising graph partitioning methods, with the end goal of clustering the nodes in V into groups with strong inner-connectivity and weak inter-connectivity (Bickel and Chen, 2009; Lancichinetti and Fortunato, 2009; Newman and Girvan, 2004).