Community Detection with the Weighted Parsimony Criterion

作     者：BETTINELLI Andrea HANSEN Pierre LIBERTI Leo 

作者机构：Dipartimento di Ingegneria dell’Energia Elettrica e Dell’Informazione Università di Bologna Viale del Risorgimento 2 40136 Bologna Italy Groupe d’études et de Recherche en Analyse des Décisions Hautes tudes Commerciales Montréal Canada LIXcole Polytechnique F-91128 Palaiseau France CNRS LIX Ecole Polytechnique 91128 Palaiseau France 

出 版 物：《Journal of Systems Science & Complexity》 (系统科学与复杂性学报（英文版）)

年 卷 期：2015年第28卷第3期

页      面：517-545页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Community detection complex networks parsimony. 

摘      要：Community detection in networks has been studied extensively in the last decade. Many criteria, expressing the quality of the partitions obtained, as well as a few exact algorithms and a large number of heuristics have been proposed. The parsimony criterion consists in minimizing the number of edges added or removed from the given network in order to transform it into a set of disjoint *** Zhang, Qiu and Zhang have proposed a weighted parsimony model in which a weight coefficient is introduced to balance the numbers of inserted and deleted edges. These authors propose rules to select a good value of the coefficient, use simulated annealing to find optimal or near-optimal solutions and solve a series of real and artificial instances. In the present paper, an algorithm is proposed for solving exactly the weighted parsimony problem for all values of the parameter. This algorithm is based on iteratively solving the problem for a set of given values of the parameter using a row generation algorithm. This procedure is combined with a search procedure to find all lowest breakpoints of the value curve(i.e., the weighted sum of inserted and deleted edges). Computational results on a series of artificial and real world networks from the literature are reported. It appears that several partitions for the same network may be informative and that the set of solutions usually contains at least one intuitively appealing partition.