DETECTING COMMUNITY STRUCTURE： FROM PARSIMONY TO WEIGHTED PARSIMONY  

作　　者：Junhua ZHANG Yuqing QIU Xiang-Sun ZHANG 

机构地区：[1]Key Laboratory of Random Complex Structures and Data Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China [2]Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

出　　处：《Journal of Systems Science & Complexity》2010年第5期1024-1036,共13页系统科学与复杂性学报（英文版）

基　　金：This research is partially supported by the National Natural Science Foundation of China under Grant No. 60873205, Innovation Project of Chinese Academy of Sciences, kjcsyw-sT.

摘　　要：Community detection has attracted a great deal of attention in recent years. A parsimony criterion for detecting this structure 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. However, many small groups of nodes are obtained by directly using this criterion to some networks especially for sparse ones. In this paper we propose a weighted parsimony model in which a weight coefficient is introduced to balance the inserted and deleted edges to ensure the obtained subgraphs to be reasonable communities. Some benchmark testing examples are used to validate the effectiveness of the proposed method. It is interesting that the weight here can be determined only by the topological features of the network. Meanwhile we make some comparison of our model with maximizing modularity Q and modularity density D on some of the benchmark networks, although sometimes too many or a little less numbers of communities are obtained with Q or D, a proper number of communities are detected with the weighted model. All the computational results confirm its capability for community detection for the small or middle size networks.

关 键 词：CLIQUES community detection complex networks parsimony. 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置] U467.5[自动化与计算机技术—控制科学与工程]