Abstract:  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.

  AMS Classications: 

  Keywords:  Networks, graphs, community structures, clique partitioning problem, graph partitioning problem, linear programming, integer linear programming, food webs, Zachary's karate club

  Download:     pdf