title: Discovering link communities in complex networks by an integer programming model and a genetic algorithm.
abstract: Identification of communities in complex networks is an important topic and issue in many fields such as sociology, biology, and computer science. Communities are often defined as groups of related nodes or links that correspond to functional subunits in the corresponding complex systems. While most conventional approaches have focused on discovering communities of nodes, some recent studies start partitioning links to find overlapping communities straightforwardly. In this paper, we propose a new quantity function for link community identification in complex networks. Based on this quantity function we formulate the link community partition problem into an integer programming model which allows us to partition a complex network into overlapping communities. We further propose a genetic algorithm for link community detection which can partition a network into overlapping communities without knowing the number of communities. We test our model and algorithm on both artificial networks and real-world networks. The results demonstrate that the model and algorithm are efficient in detecting overlapping community structure in complex networks.
authors.affiliation: School of Information, Beijing Wuzi University, Beijing, China.
authors.forename: Zhenping
authors.initials: Z
authors.lastname: Li
authors.affiliation: National Center for Mathematics and Interdisciplinary Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Science, Beijing, China.
authors.forename: Xiang-Sun
authors.initials: XS
authors.lastname: Zhang
authors.affiliation: Department of Physics, The Pennsylvania State University, University Park, Pennsylvania, United States of America.
authors.forename: Rui-Sheng
authors.initials: RS
authors.lastname: Wang
authors.affiliation: School of Information, Beijing Wuzi University, Beijing, China.
authors.forename: Hongwei
authors.initials: H
authors.lastname: Liu
authors.affiliation: National Center for Mathematics and Interdisciplinary Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Science, Beijing, China.
authors.forename: Shihua
authors.initials: S
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D006801:Humans; D008962:Models, Theoretical