A Weighting Scheme for Enhancing Community Detection in Networks

Many algorithms have recently been proposed for finding communities in networks. By definition, a community is a subset of vertices with a high number of connections among the vertices, but only few connections with other vertices. The worst drawback of most of the proposed algorithms is their computational complexity which is usually an exponentially increasing function of the number of the vertices. Newman-Fast is a well-known community detection algorithm which is suitable for large networks due to its low computational cost. Although the performance of this algorithm is good for well structured networks, it does not perform well for more fuzzy-clustered networks. In this paper, we propose a weighting scheme which considerably enhances the performance of the Newman-Fast algorithm with a little effort. We also show that the modified algorithm effectively enhances the community discovery process in both computer-generated and real-world networks.