This is version . It is not the current version, and thus it cannot be edited.
Back to current version   Restore this version

QMC: A combinatorial model and algorithm for globally searching community structure in complex networks

  • Version 0.0.1
  • Last updated: Nov. 1, 2012

References#

  • Xiang-Sun Zhang, Zhenping Li, Rui-Sheng Wang, Yong Wang. A combinatorial model and algorithm for globally searching community structure in complex networks.Journal of Combinatorial Optimization, Vol. 23, No. 4, 425-442, 2012.

Motivation#

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.

Method#

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 andreal-life complex networks show that the combinatorial model/algorithm has promising performance and can overcome the limitations in existing algorithms.

Software#

This version of the program is in very preliminary stage and provided just for testing purpose. The program is still under development.

Add new attachment

Only authorized users are allowed to upload new attachments.

List of attachments

Kind Attachment Name Size Version Date Modified Author Change note
rar
Quamincut.rar 3.1 kB 1 18-May-2013 23:36 YongWang
« This particular version was published on 18-May-2013 23:36 by YongWang.