2009/01/15 by Yan Sun, Yudong Sun, Bogdan Danila +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Bioinformatics and Genomic Networks #Community structure #Complex Network Analysis Techniques #Complex network #Computational complexity theory #Computer science #Constraint (computer-aided design) #Limiting #Mathematical optimization #Mathematics #Modularity (biology) #Opinion Dynamics and Social Influence #cond-mat.stat-mech #cs.CY #cs.DS #physics.comp-ph #physics.soc-ph #q-bio.QM
paper · pdf · doi:10.1209/0295-5075/86/28004
6 pages, 3 figures, 1 table
arxiv created 2009/01/15 · openalex publication_date 2009/04/01 · arxiv updated 2015/05/12 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/06
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.