Community detection enhancement in networks using proper weighting and partial synchronization

A community in a network is a subset of vertices densely connected to each other, but less connected to the vertices outside. Many different approaches have been developed to find such structures in a given network, but the main drawback of most of the available algorithms is that they are computationally demanding and their complexity 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 utilize a proper weighting scheme and an algorithm based on partial synchronization phenomenon as pre- and post-processing steps to improve the Newman-Fast algorithm. Furthermore, we evaluate the proposed method for both computer-generated and real-world networks. The results show that either both or one of the proposed steps enhance the performance of the Newman-Fast algorithm significantly while they impose little additional effort.