A similarity based generalized modularity measure towards effective community discovery in complex networks

Modularity is a widely used goodness metric that effectively measures the strength of the community structures present in a network. However its performance may not be desirable for identifying densely connected communities or clusters of a network. It also often fails to identify communities or clusters that contain very few nodes. Furthermore, modularity is defined based only on the exact node-to-node connectivity of a network while disregarding their neighborhood connectivity. In this paper, we associate the neighborhood connectivity to the modularity function and propose a generalized modularity function based on the node similarity measure which quantifies the quality of a given network partition. Making use of this similarity based modularity function, an effective agglomerative approach for identifying communities is introduced. This agglomerative approach iteratively discovers the final community structure of the network by finding and merging together, at each step, the community pairs which maximize the proposed modularity value. A significant characteristic of the proposed method is that it does not need any prior knowledge about the actual communities of a network. The performance of the proposed method and state-of-the-art algorithms are compared using the value of modularity, normalized mutual information and adjusted variation of information measures on several real world and artificial networks. The empirical results show the effectiveness of the proposed method compared to the state-of-the-art techniques.