Volume 86, Number 2, April 2009
|Number of page(s)||6|
|Section||Interdisciplinary Physics and Related Areas of Science and Technology|
|Published online||04 May 2009|
Improved community structure detection using a modified fine-tuning strategy
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
Corresponding author: firstname.lastname@example.org
Accepted: 24 March 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.
PACS: 89.75.Hc – Networks and genealogical trees / 87.16.Yc – Regulatory genetic and chemical networks / 89.20.Hh – World Wide Web, Internet
© EPLA, 2009
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.