基于非负矩阵分解的半监督动态社团检测

doi:10.11959/j.issn.1000-436x.2016039

Abstract

Abstract:

How to effectively combine the network structures on different time points was the key and difficulty to affect the performance of detection algorithms. Based on this, a semi-supervised dynamic community algorithm SDCD based on non-negative matrix factorization, which effectively extracted the historical stability structure unit firstly, and then use it as a regularization item supervision of nonnegative matrix decomposition, to guide the network community detection on current moment. Experiments on the real network dat sets show that the method has a higher community detection quality compared with existing methods, which can accurately mine the relationship among different time, and explore network evolution and the law of development more adva geously.

Key words: semi-supervised, dynamic, community detection, on-negative matrix factorization

Zhen-chao CHANG,Hong-chang CHEN,Rui-yang HUANG,Hong-tao YU,Yang LIU. Semi-supervised dynamic community detection based on non-negative matrix factorization[J]. Journal on Communications, 2016, 37(2): 132-143.

Figures/Tables 7

References 47

[1]	FORTUNATO S . Community detection in graphs[J]. Physics Reports, 2010, 486(3-5): 75-174.
[2]	GIRVAN M , NEWMAN M E J . Community structure in social and biological networks[J]. Proc Natl Acad Sci, 2002, 99(2): 7821-7826.
[3]	LUXBURG U . A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4): 395-416.
[4]	YANG L , CAO X C , JIN D . A unified semi-supervised community detection framework using latent space graph regularization[J]. IEEE Transactions on Cybernetics, to Appear 2015, DOI: 10. 1109/TCYB, 2014.2377154.
[5]	ZHANG Z Y . Community structure detection in complex networks withpartial background information[J]. Europhys Lett, 101(4):Art. ID 48005.
[6]	郭昆, 郭文忠, 邱启荣 , 等. 基于局部近邻传播及用户特征的社区识别算法[J]. 通信学报, 2015, 36(2): 2015035-1-2015035-12. GUO K , GUO W Z , QIU Q R , et al. Community detection algorithm based on local affinity propagation and user profile[J]. Journal of Communications, 2015, 36(2): 2015035-1-2015035-12.
[7]	卫红权, 陈鸿昶, 刘力雄 , 等. 基于强度排序的通信社区检测算法[J]. 通信学报, 2014, 35(10): 165-170. WEI H Q , CHEN H Q , LIU L X , et al. Communication community detection algorithm based on ranking of strength[J]. Journal of Com-munications, 2014, 35(10): 165-170.
[8]	EUSTACE J , WANG X Y , CUI Y Z , et al. Overlapping commu ity detection using neighborhood ratio matrix[J]. Physica A, 2015, 421(2015): 510-521.
[9]	CHAKRABARTI D , KUMAR R , TOMKINS A S , et al. Evolutionary clustering[C]// The 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. c2006: 554-560.
[10]	CAZABET R , AMBLARD F . Dynamic community detection[M]. Encyclopedia of Social Network Analysis and Mining. Springer New York Press, 2014.
[11]	CHARU A , KARTHIK S . Evolving network analysis: a survey[J]. ACM Computing Surveys, 2014, 47(1): 1-36.
[12]	LEE D D , SEUNG H S . Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401(6755): 788-791.
[13]	LAI J H , WANG C D , YU P . Dynamic community detection i weighted graph streams[C]// The 2013 SIAM International Conference on Data Mining. c2013: 151-161.
[14]	CHENG Y , REGE M , DONG M , et al. Non-negative matrix factorization for semi-supervised data clustering[J]. Knowledge and Information Systems, 2008, 17(3): 355-379.
[15]	WANG H , NIE F P , HUANG H . Nonnegative matrix tri-factorization based high-order co-clustering and its fast implementation[C]// The 2011 SIAM International Conference on Data Mining. c2011: 784783.
[16]	尚凡华 . 基于低秩结构学习数据表示[D]. 西安：西安电子科技大学, 2012. SHANG F H . The low rank structure learning based on data represen-tation[D]. Xi'an: Xidian University, 2012.
[17]	CAI D , HE X F , HAN J W , et al. Graph regularized non-negative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 8(33): 1548-1560.
[18]	SUN J M , PAPADIMITRIOU S , YU P S , et al. Graphscope: parameter-free mining of large time-evolving graphs[C]// The 13th ACM SIGKDD Int’l Conf on Knowledge Discovery and Data Minig. c2007: 687-696.
[19]	黄永锋, 董永强, 张三峰 , 等. 基于社会特征周期演化的机会移动网络路由转发策略[J]. 通信学报, 2015, 36(3): 2015055. HUANG Y F , DONG Y Q , ZHANG S F , et al. Message forward ng based on periodically evolving social characteristics in opportunistic mobile networks[J]. Journal of Communications, 2015, 36(3): 2015055-1—2015055-12.
[20]	NING H Z , XU W , CHI Y , et al. Incremental spectral clustering by efficiently updating the eigen-system[J]. Pattern Recognition, 2010, 43(1): 113-127.
[21]	单波, 姜守旭, 张硕 . IC：动态社会关系网络社区结构的增量识别算法[J]. 软件学报, 2009, 20(1): 184-192. SHAN B , JINAG S X , ZHANG S . IC: incrementalalgorithm for community identification in dynamic socialnetworks[J]. Journal of Software, 2009, 20(1): 184-192.
[22]	肖杰斌, 张绍武 . 基于随机游走和增量相关节点的动态网络社团挖掘算法[J]. 电子与信息学报, 2013, 35(4): 977-981. XIAO J B , ZHANG S W . An algorithm of integrating random walk and increment correlative vertexes for mining communit of dynamic networks[J]. Journal of Electronics ＆ Information Technology, 2013, 35(4): 977-981.
[23]	郭进时, 汤红波, 王晓雷 . 基于社会网络增量的动态社区组织探测[J]. 电子与信息学报, 2013, 35(9): 2240-2246. GUO J S , TANG H B , WANG X L . A dynamic community structure detection scheme based on social network incremental[J]. Journal of Electronics ＆ Information Technology, 2013, 35(9): 2240-2246.
[24]	MIGUEL A , SPIROS P , STEPHAN G , et al. 1Com2: fast automatic discovery of temporal ('Comet')communities[C]// The PAKDD. c2014: 271-283.
[25]	NIGN H Z , XU W , CHI Y , et al. Incremental spectral clu ing with application to monitoring of evolving blog communities[C]// The 2007 SIAM International Conference on Data Mining. c2007: 261-272.
[26]	ROBERT G , TANJA H , DOROTHEA W . Dynamic graph clusterin using minimum-cut trees[J]. Journal of Graph Algorithms and Applications, 2012, 16(2): 411-446.
[27]	DUAN D S , LI Y H , LI R X , et al. Incremental -clique clustering ink dynamic social networks[J]. Artificial Intelligence, 2012, 38(2): 129-147.
[28]	CHI Y , SONG X D , ZHOU D Y , et al. Evolutionary spectral clustering by incorporating temporal smoothness[C]// The 13th ACM International Conference on Knowledge Discovery and Data Mining. c2007: 153-162.
[29]	LIN Y R , CHI Y , ZHU S H , et al. Analyzing communities nd their evolutions in dynamic social networks[J]. ACM Transact ons on Knowledge Discovery from Data, 2009, 3(2): 8:1-8:31.
[30]	THANG N D , NGUYEN N P , THAI M T . An adaptive approximation algorithm for community detection in dynamic scale-free networks[C]// The 2013 IEEE INFOCOM. c2013: 55-59.
[31]	GORKE R , MAILLARD P , SCHUMM A , et al. Dynamic graph clustering combining modularity and smoothness[J]. ACM Journal of Experimental Algorithmics, 2013, 18(1): 1.5:1.1-1.5:1.29.
[32]	BECCHETTI L , BOLDI P , CASTILLLO C , et al. Efficient se istreaming algorithms for local triangle counting in massive graphs[C]// The 14th ACM SIGKDD international conference on Knowledge discovery and data mining. c2008: 16-24.
[33]	KIM M S , HAN J W . A particle-and-density based evolutionary clustering method for dynamic networks[C]// The 35th International Conference on Very Large Databases. c2009: 622-633.
[34]	TANG L , LIU H , ZHANG J P . Identifying evolving groups n dynamic multimode networks[J]. IEEE Trans on Knowledge and Data Engineering, 2012, 24(1): 72-85.
[35]	XU KS , KLIGER M , HERO A O . Adaptive evolutionary clustering[J]. Data Mining and Knowledge Discover, 2014, 28(2): 304-336.
[36]	MA H F , ZHAO W Z , SHI Z Z . A nonnegative matrix factorization framework for semi-supervised document clustering with dual constraints[J]. Knowledge and Information Systems September, 2013, 36(3): 629-651.
[37]	WASSERMAN S , FAUST K . Social network analysis: methods and applications[M]. Cambridge University Press, 1994.
[38]	PALLA G , DETRNYI I , FARKAS I , et al. Uncovering the overlapping community structure of complex networks in nature and iety[J]. Nature, 2005, 435(1): 814-818.
[39]	NEWMAN M . Spectral methods for network community detection and graph partitioning[J]. Phys Rev E, 2013, 88(4): 042822:1-042822: 11.
[40]	AIROLDI E M , BLEI D M , FIENBERG S E , et al. Mixed membership stochastic block models[J]. J Mach Learn Res, 2009, 9(1): 1981-2014.
[41]	CHRISTOPHER M , MAES . A regularized active-set method roe sparse convex quadratic programming[M]. 2010 Ph D Dissertation Stanford university.
[42]	WEBER M , RUNGSARITYOTIN W , SCHLIEP A . Perron cluster analysis and its connection to graph partitioning for isy data[M]. Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2004.
[43]	LANCICHINETTI A , FORTUNATO S . Community detection algorithms: a comparative analysis[J]. Phys Rev E 2009 2009, 80(5): 733-737.
[44]	SUN J , FALOUTSOS C , PAPADIMITRIOU S , et al. Graphscope parameter-free mining of large time-evolving graphs[C]// The 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. c2007: 687-696.
[45]	ArXiv dataset[EB/OL]. . 2003.
[46]	NGUYEN N P , DINH T N , XUAN Y , et al. Adaptive algorith for detecting community structure in dynamic social networks[C]// The 2011 INFOCOM. c2011: 2282-2290.
[47]	VISWANATH B , MISLOVE A , CHA M , et al. On the evolution of user interaction in facebook[C]// The 2nd ACM workshop on Online social networks. c2009: 37-42.

Metrics

Recommended 0

No Suggested Reading articles found!

Semi-supervised dynamic community detection based on non-negative matrix factorization

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 47

Related Articles 15

Metrics

Recommended 0

[1]	Yang GAO, Hongli ZHANG. Survey on community detection method based on random walk [J]. Journal on Communications, 2023, 44(6): 198-210.
[2]	Dacheng ZHOU, Hongchang CHEN, Weizhen HE, Guozhen CHENG, Hongchao HU. Research on multidimensional dynamic defense strategy for microservice based on deep reinforcement learning [J]. Journal on Communications, 2023, 44(4): 50-63.
[3]	Wenhao YAN, Zijing JIANG, Xin HUANG, Shujuan ZHU, Qun DING. Generalized 2D polynomial chaotic map and its application in information transmission [J]. Journal on Communications, 2022, 43(9): 80-89.
[4]	Jing ZHAO, Jun LI, Chun LONG, Wei WAN, Jinxia WEI, Kai CHEN. Unsupervised detection method of RoQ covert attacks based on multilayer features [J]. Journal on Communications, 2022, 43(9): 224-239.
[5]	Ao LI, Cong FENG, Yutong NIU, Shibiao XU, Yingtao ZHANG, Guanglu SUN. Multiview clustering method for view-unaligned data [J]. Journal on Communications, 2022, 43(7): 143-152.
[6]	Xiaofeng FENG, Jianfeng XU, Chuan HE. Dynamic generalized principal component analysis with applications to fault subspace modeling [J]. Journal on Communications, 2022, 43(5): 92-101.
[7]	Ruizhong DU, Yuqing ZHANG, Mingyue LI. Efficient dynamic searchable encryption scheme for conjunctive queries based on bidirectional index [J]. Journal on Communications, 2022, 43(5): 123-132.
[8]	Fan ZHANG, Yun HUANG, Zizhuo FANG, Wei GUO. Lost-minimum post-training parameter quantization method for convolutional neural network [J]. Journal on Communications, 2022, 43(4): 114-122.
[9]	Yinghui ZHANG, Lingyun HU, Yixin LI, Jianting NING, Dong ZHENG. Secure and efficient batch authentication scheme based on dynamic revocation mechanism in space information network [J]. Journal on Communications, 2022, 43(4): 164-176.
[10]	Hongyong JIA, Yunfei PAN, Wenhe LIU, Junjie ZENG, Jianhui ZHANG. Executive dynamic scheduling algorithm based on high-order heterogeneity [J]. Journal on Communications, 2022, 43(3): 233-245.
[11]	Yinuo HAO, Zhou ZHONG, Xiaoli SUN, Liang JIN. DMA-based key generation method for IoT scenario [J]. Journal on Communications, 2022, 43(12): 45-53.
[12]	Ru HUO, Xiangfeng CHENG, Chuang SUN, Shuo WANG, Tao HUANG, Yu F.Richard. Topology optimization and forwarding strategy design for blockchain network [J]. Journal on Communications, 2022, 43(12): 89-100.
[13]	Xiujuan DU, Lijuan WANG, Jingping LIU, Long JIN. Ranging localization method for nodes in underwater wireless sensor network based on zeroing neural dynamics [J]. Journal on Communications, 2022, 43(10): 177-185.
[14]	Huafeng HUANG, Purui SU, Yi YANG, Xiangkun JIA. Automatic exploitation generation method of write-what-where vulnerability [J]. Journal on Communications, 2022, 43(1): 83-95.
[15]	Lingcui ZHANG, Yaobing XU, Fenghua LI, Liang FANG, Yunchuan GUO, Zifu LI. Dynamic security-empowering architecture for space-ground integration information network [J]. Journal on Communications, 2021, 42(9): 87-95.