模式识别与人工智能
Saturday, May. 3, 2025 Home      About Journal      Editorial Board      Instructions      Ethics Statement      Contact Us                   中文
  2018, Vol. 31 Issue (11): 965-978    DOI: 10.16451/j.cnki.issn1003-6059.201811001
Papers and Reports Current Issue| Next Issue| Archive| Adv Search |
Incremental Dynamic Community Detection Algorithm Based on Density Clustering
GUO Kun1,2,3, PENG Shengbo1,2,3, CHEN Yuzhong1,2,3, GUO Wenzhong1,2,3
1.College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116
2.Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350116
3.Key Laboratory of Spatial Data Mining and Information Sharing, Ministry of Education, Fuzhou University, Fuzhou 350116

Download: PDF (1075 KB)   HTML (1 KB) 
Export: BibTeX | EndNote (RIS)      
Abstract  The community structures of social networks in the real world are always varying with nodes and edges of social networks increasing or disappearing dynamically as time goes by. In this paper, an incremental dynamic community detection algorithm based on density clustering is proposed. Firstly, the initial communities are generated according to the improved DBSCAN algorithm. Then, an index of edge variation rate is proposed and it is combined with the cosine similarity index to determine the community belonging adjustment process of the nodes whose neighbors vary in adjacent moment. In addition, both direct and indirect neighbor nodes are taken into account during the calculation of community belongingness.Finally, the communities are merged by iteratively updating the modularity gain to reduce the interference of noise communities. Experimental results on artificial datasets and real networks show that the proposed algorithm effectively copes with the variation of the network structures and incremental calculation cumulative errors with a low time complexity.
Key wordsDynamic Community Detection      Density Clustering      Edge Variation Rate      Modularity     
Received: 31 May 2018     
ZTFLH: TP 391  
Fund:Supported by National Natural Science Foundation of China(No.61300104,61300103,61672158), Natural Science Foundation of Fujian Province(No.2013J01230,2014J01232), Fujian Province High School Science Fund for Distinguished Young Scholars(No.JA12016), Program for New Century Excellent Talents in Fujian Province University(No.JA13021), Fujian Natural Science Funds for Distinguished Young Scholar(No.2014J06017,2015J06014), Technology Innovation Platform Project of Fujian Province(No.2009J1007,2014H2005), Industry-Academy Cooperation Project(No.2014H6014,2017H6008), Haixi Government Big Data Application Cooperative Innovation Center
Corresponding Authors: GUO Wenzhong, Ph.D., professor. His research interests include computer network, computational intelligence algorithm and VLSI physical design algorithm.   
About author:: GUO Kun, Ph.D., associate professor. His research interests include complex network, grey system theory and data mining;PENG Shengbo, master student. His research interests include complex network and data mining;CHEN Yuzhong, Ph.D., professor. His research interests include complex network, computational intelligence and data mining.
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
GUO Kun
PENG Shengbo
CHEN Yuzhong
GUO Wenzhong
Cite this article:   
GUO Kun,PENG Shengbo,CHEN Yuzhong等. Incremental Dynamic Community Detection Algorithm Based on Density Clustering[J]. , 2018, 31(11): 965-978.
URL:  
http://manu46.magtech.com.cn/Jweb_prai/EN/10.16451/j.cnki.issn1003-6059.201811001      OR     http://manu46.magtech.com.cn/Jweb_prai/EN/Y2018/V31/I11/965
Copyright © 2010 Editorial Office of Pattern Recognition and Artificial Intelligence
Address: No.350 Shushanhu Road, Hefei, Anhui Province, P.R. China Tel: 0551-65591176 Fax:0551-65591176 Email: bjb@iim.ac.cn
Supported by Beijing Magtech  Email:support@magtech.com.cn