动态网络桥系数增量聚类算法

doi:10.3969/j.issn.1001-2400.2013.01.006

Abstract

Abstract:

An incremental clustering algorithm is proposed to identify community structures in dynamic networks. Based on the feature that in dynamic networks there is little change in adjacent network snapshots, the community structures detected in last snapshot are used as the initial clustering results in current snapshot. Then the edge bridgeness is adopted to judge the snapshot change's influence on clustering results. Finally, the community structures fitting current snapshot are obtained by locally modifying the initial clustering results. The accuracy and efficiency of our algorithm are validated by comparing with the MCL algorithm. Experimental results demonstrate that our approach performs accurately and effectively in identifying community structures in dynamic networks because clustering the current snapshot can be avoided by incrementally analyzing the dynamic networks.

Key words: complex networks, community, clustering algorithm, incremental clustering, bridgeness

CLC Number:

TP301.6

WANG Yu;GAO Lin. Discovering communities in dynamic networks: a bridgeness incremental clustering algorithm[J].J4, 2013, 40(1): 30-35.

References

［1］ Palla G, Barabasi A-L, Vicsek T. Quantifying Social Group Evolution ［J］. Nature, 2007, 446(7136): 664-667.
［2］ Palla G, Derenyi I, Farkas I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society ［J］. Nature, 2005, 435(7043): 814-818.
［3］ Asur S, Parthasarathy S, Ucar D. An Event-based Framework for Characterizing the Evolutionary Behavior of Interaction Graphs ［C］//Proc of the 13th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. California: ACM, 2007: 913-921.
［4］ Dongen S V. Graph Clustering by Flow Simulation ［D］. Netherlands: University of Utrecht, 2000.
［5］ Rosvall M, Bergstrom C T. Mapping Changes in Large Networks ［J］. Plos One, 2010, 5(1): 8694.
［6］单波, 姜守旭, 张硕, 等. IC: 动态社会关系网络社区结构的增量识别算法［J］. 软件学报, 2009, 20(12): 184-192.
Shan Bo, Jiang Shouxu, Zhang Shuo, et al. IC: Incremental Algorithm for Community Identification in Dynamic Social Networks［J］. Journal of Software, 2009, 20(12): 184-192.
［7］ Nguyen N P, Dinh T N, Tokala S, et al. Overlapping Communities in Dynamic Networks: Their Detection and Mobile Applications ［C］//Proc of the 17th Annual International Conference on Mobile Computing and Networking. Las Vegas: ACM, 2011: 85-95.
［8］ Cheng Xueqi, Ren Fuxin, Shen Huawei, et al. Bridgeness: a Local Index on Edge Significance in Maintaining Global Connectivity ［J］. Journal of Statistical Mechanics: Theory and Experiment, 2010(10): 10011.
［9］ Lancichinetti A, Fortunato S. Detecting the Overlapping and Hierarchical Community Structure in Complex Networks ［J］. New Journal of Physics, 2009, 11(3): 033015.
［10］ Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks ［J］. Phys Rev E, 2004, 69(2): 026113.
［11］ Kim M, Han Jiawei. A Particle-and-Density Based Evolutionary Clustering Method for Dynamic Networks ［C］//Proc of the VLDB Endowment. Lyon: ACM, 2009: 622-633.

[1]	ZHANG Shubo,REN Shuxia,WU Tao. Improved spectral clustering community detection algorithm by combining the probability matrix [J]. Journal of Xidian University, 2019, 46(3): 167-172.
[2]	FU Lidong;MA Xiaoke;NIE Jingjing. Evolutionary spectral approach to finding communities in dynamic networks [J]. Journal of Xidian University, 2018, 45(2): 43-47+53.
[3]	GUO Jingjing;MA Jianfeng. Trust recommendation algorithm for the virtual community based Internet of Things(IoT) [J]. J4, 2015, 42(2): 52-57+179.
[4]	CHEN Guoqiang;WANG Yuping. Revealing of the hierarchy community of the complex network by decomposition multi-objective optimization [J]. J4, 2013, 40(3): 205-211.
[5]	FU Lidong;GAO Lin. Kernel k-means clustering algorithm for detecting communities in complex networks based on eigenvector [J]. J4, 2012, 39(2): 175-180.
[6]	WANG Shiqiang;ZHANG Dengfu;BI Duyan;YONG Xiaoju. Novel radar signal sorting method with low complexity [J]. J4, 2011, 38(4): 148-153.
[7]	FU Li-dong;GAO Lin. Spectral approach to finding communities in networks based on the modularity density [J]. J4, 2010, 37(5): 916-920+965.
[8]	CHEN Ying-hui;DU Hai-feng;LI Shu-zhuo. Modified modularity and the corresponding community structure detecting algorithm [J]. J4, 2010, 37(2): 374-379.
[9]	TIAN Xiao-lin;JIAO Li-cheng;GOU Shui-ping. SAR image segmentation using optimized FCM with weighted spatial function [J]. J4, 2008, 35(5): 846-852.
[10]	ZHANG Li1;2;YU Zhen-wei1;ZHANG Yang3. Adaptive-weighted clustering algorithm based on flow balance for mobile ad hoc networks [J]. J4, 2008, 35(3): 572-576.
[11]	FENG Shao-rong1;2;XIAO Wen-jun1. New method to improve DBSCAN clustering algorithm quality [J]. J4, 2008, 35(3): 523-529.

Discovering communities in dynamic networks: a bridgeness incremental clustering algorithm

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 11

Metrics

Comments

Recommended 0