Force-Based Incremental Algorithm for Mining Community Structure in Dynamic Network

作     者：杨博 刘大有 

作者机构：College of Computer Science and Technology & Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education Jilin University Changchun 130012 P.R. China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2006年第21卷第3期

页      面：393-400页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This work is supported by the NSFC Major Research Program under Grant No. 60496321  the National Natural Science Foundation of China under Grant No. 60503016  and the National High-Tech Development 863 Program of China under Grant No. 2003AA118020 

主　　题：incremental algorithm community structure dynamic network 

摘      要：Community structure is an important property of network. Being able to identify communities can provide invaluable help in exploiting and understanding both social and non-social networks. Several algorithms have been developed up till now. However, all these algorithms can work well only with small or moderate networks with vertexes of order 104. Besides, all the existing algorithms are off-line and cannot work well with highly dynamic networks such as web, in which web pages are updated frequently. When an already clustered network is updated, the entire network including original and incremental parts has to be recalculated, even though only slight changes are involved. To address this problem, an incremental algorithm is proposed, which allows for mining community structure in large-scale and dynamic networks. Based on the community structure detected previously, the algorithm takes little time to reclassify the entire network including both the original and incremental parts. Furthermore, the algorithm is faster than most of the existing algorithms such as Girvan and Newman＇s algorithm and its improved versions. Also, the algorithm can help to visualize these community structures in network and provide a new approach to research on the evolving process of dynamic networks.