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

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

摘要/Abstract

摘要：

如何有效融合不同时刻的网络结构信息，是影响复杂网络中动态社团检测算法检测性能的关键和难点。基于此，提出了一种基于非负矩阵分解的半监督动态社团检测方法 SDCD-NMF，该方法首先有效提取了历史时刻所包含的稳定结构单元，然后将其作为正则化监督项，指导当前时刻的网络社团检测。在真实网络数据集上的实验表明，所提方法与已有方法相比具备更高的社团划分质量，更有利于探索网络的演变与发展规律。

关键词: 半监督, 动态, 社团检测, 非负矩阵分解

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

常振超,陈鸿昶,黄瑞阳,于洪涛,刘阳. 基于非负矩阵分解的半监督动态社团检测[J]. 通信学报, 2016, 37(2): 132-143.

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.

图/表 7

图1

图2

图3

图4

图5

图6

图7

参考文献 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.