Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 23, Issue 4, Pages 425-442Publisher
SPRINGER
DOI: 10.1007/s10878-010-9356-0
Keywords
Complex network; Community structure; Heuristic algorithm; Linear integer programming; NP-hard
Funding
- Natural Science Foundation of China [10631070, 60873205, 10801131, 10701080]
- Chinese Academy of Sciences [kjcx-yw-s7]
- Beijing Natural Science Foundation [1092011]
- Foundation of Beijing Education Commission [SM200910037005]
- Jurisdiction of Beijing Municipality (PHR(IHLB))
Ask authors/readers for more resources
Community structure is one of the important characteristics of complex networks. In the recent decade, many models and algorithms have been designed to identify communities in a given network, among which there is a class of methods that globally search the best community structure by optimizing some modularity criteria. However, it has been recently revealed that these methods may either fail to find known qualified communities (a phenomenon called resolution limit) or even yield false communities (the misidentification phenomenon) in some networks. In this paper, we propose a new model which is immune to the above phenomena. The model is constructed by restating community identification as a combinatorial optimization problem. It aims to partition a network into as many qualified communities as possible. This model is formulated as a linear integer programming problem and its NP-completeness is proved. A qualified min-cut based bisecting algorithm is designed to solve this model. Numerical experiments on both artificial networks and real-life complex networks show that the combinatorial model/algorithm has promising performance and can overcome the limitations in existing algorithms.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available