A Weighted Parsimony Model for Community Detection in Complex Networks

Many real-world networks have a common feature of organization, i.e., community structure. Detecting this structure is fundamental for uncovering the links between the structure and the function in complex networks and for practical applications in many disciplines such as biology and sociology. In this paper we propose a weighted parsimony criterion for community detection in complex networks. This criterion relates communities with cliques (or complete subgraphs). Parsimony here means that as minimal as possible number of inserted and deleted edges is needed when we make the network considered become a disjoint union of cliques. A weight based on the topological features of the network is introduced to ensure the obtained subgraphs to be communities by balancing the inserted and deleted edges. Tests on real networks give excellent results.