Volume 86, Number 2, April 2009
Article Number 28004
Number of page(s) 6
Section Interdisciplinary Physics and Related Areas of Science and Technology
Published online 04 May 2009
EPL, 86 (2009) 28004
DOI: 10.1209/0295-5075/86/28004

Improved community structure detection using a modified fine-tuning strategy

Y. Sun1, B. Danila1, K. Josić2 and K. E. Bassler1, 3

1   Department of Physics, University of Houston - Houston, TX 77204-5005, USA
2   Department of Mathematics, University of Houston - Houston, TX 77204-3008, USA
3   Texas Center for Superconductivity, University of Houston - Houston, TX 77204-5002, USA

received 15 January 2009; accepted in final form 24 March 2009; published April 2009
published online 4 May 2009

The community structure of a complex network can be determined by finding the partitioning of its nodes that maximizes modularity. Many of the proposed algorithms for doing this work by recursively bisecting the network. We show that this unduely constrains their results, leading to a bias in the size of the communities they find and limiting their effectiveness. To solve this problem, we propose adding a step, which is a modification of the Kernighan-Lin algorithm, to the existing algorithms. This additional step does not increase the order of their computational complexity. We show that, if this step is combined with a commonly used method, the identified constraint and resulting bias are removed, and its ability to find the optimal partitioning is improved. The effectiveness of this combined algorithm is also demonstrated by using it on real-world example networks. For a number of these examples, it achieves the best results of any known algorithm.

89.75.Hc - Networks and genealogical trees.
87.16.Yc - Regulatory genetic and chemical networks.
89.20.Hh - World Wide Web, Internet.

© EPLA 2009