A Novel Approach for Detecting Community Structure in Networks

Several approaches have been proposed to solve the well-studied problem of detecting community structure in networks. However, many existing algorithms encounter difficulties when the proportion of inter-community links is higher than the proportion of intra-community links. To overcome this situation, we propose a novel algorithm which performs community detection in two phases. The first phase exploits the covariance of links between nodes and the interclass inertia in order to perform an initial partitioning of the network. The objective is to generate small disconnected groups of nodes mostly from the same community. Then, in the second phase, we propose an iterative process that repeatedly merges these initial groups to identify the final community structure that maximizes the modularity. We illustrate the suitability of our proposal through an empirical study that uses both generated and real-life networks.