Community Structures of Networks

We present an approach to studying the community structures of networks by using linear programming (LP). Starting with a network in terms of (a) a collection of nodes and (b) a collection of edges connecting some of these nodes, we use a new LP-based method for simultaneously (i) finding, at minimal cost, a second edge set by deleting existing and inserting additional edges so that the network becomes a disjoint union of cliques and (ii) appropriately calibrating the costs for doing so. We provide examples that suggest that, in practice, this approach provides a surprisingly good strategy for detecting community structures in given networks.

Authors and Affiliations

1. Center for Combinatorics, LPMC, Nankai University, Tianjin, 300071, P.R. China

   William Y. C. Chen & Winking Q. Yu

2. CAS-MPG Partner Institute for Computational Biology, Shanghai Institutes for Biological Sciences, Chinese Academy of Sciences, Shanghai, 200031, P.R. China

   Andreas W. M. Dress

3. Max-Planck-Institut für Mathematik in den Naturwissenschaften, Inselstrasse 22–26, D-04103, Leipzig, Germany

   Andreas W. M. Dress

Corresponding author

Correspondence to Andreas W. M. Dress.

Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.

Reprints and permissions