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.

Published in:
2010 Ieee International Symposium On Circuits And Systems, 3777-3780
Presented at:
International Symposium on Circuits and Systems Nano-Bio Circuit Fabrics and Systems (ISCAS 2010), Paris, FRANCE, May 30-Jun 02, 2010
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa

 Record created 2012-01-12, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)