通信学报 ›› 2016, Vol. 37 ›› Issue (2): 132-143.doi: 10.11959/j.issn.1000-436x.2016039
常振超,陈鸿昶,黄瑞阳,于洪涛,刘阳
出版日期:
2016-02-26
发布日期:
2016-02-26
基金资助:
Zhen-chao CHANG,Hong-chang CHEN,Rui-yang HUANG,Hong-tao YU,Yang LIU
Online:
2016-02-26
Published:
2016-02-26
Supported by:
摘要:
如何有效融合不同时刻的网络结构信息,是影响复杂网络中动态社团检测算法检测性能的关键和难点。基于此,提出了一种基于非负矩阵分解的半监督动态社团检测方法 SDCD-NMF,该方法首先有效提取了历史时刻所包含的稳定结构单元,然后将其作为正则化监督项,指导当前时刻的网络社团检测。在真实网络数据集上的实验表明,所提方法与已有方法相比具备更高的社团划分质量,更有利于探索网络的演变与发展规律。
常振超,陈鸿昶,黄瑞阳,于洪涛,刘阳. 基于非负矩阵分解的半监督动态社团检测[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.
[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. |
[1] | 周大成, 陈鸿昶, 何威振, 程国振, 扈红超. 基于深度强化学习的微服务多维动态防御策略研究[J]. 通信学报, 2023, 44(4): 50-63. |
[2] | 解元, 邹涛, 孙为军, 谢胜利. 面向高混响环境的欠定卷积盲源分离算法[J]. 通信学报, 2023, 44(2): 82-93. |
[3] | 赵静, 李俊, 龙春, 万巍, 魏金侠, 陈凯. 基于多层次特征的RoQ隐蔽攻击无监督检测方法[J]. 通信学报, 2022, 43(9): 224-239. |
[4] | 李骜, 冯聪, 牛宇童, 徐士彪, 张英涛, 孙广路. 面向视角非对齐数据的多视角聚类方法[J]. 通信学报, 2022, 43(7): 143-152. |
[5] | 冯晓伟, 许剑锋, 何川. 动态广义主成分分析及其在故障子空间建模中的应用[J]. 通信学报, 2022, 43(5): 92-101. |
[6] | 杜瑞忠, 张玉晴, 李明月. 基于双向索引的高效连接关键字查询动态可搜索加密方案[J]. 通信学报, 2022, 43(5): 123-132. |
[7] | 张帆, 黄赟, 方子茁, 郭威. 卷积神经网络的损失最小训练后参数量化方法[J]. 通信学报, 2022, 43(4): 114-122. |
[8] | 张应辉, 胡凌云, 李艺昕, 宁建廷, 郑东. 空间信息网络中基于动态撤销机制的安全高效批量认证方案[J]. 通信学报, 2022, 43(4): 164-176. |
[9] | 贾洪勇, 潘云飞, 刘文贺, 曾俊杰, 张建辉. 基于高阶异构度的执行体动态调度算法[J]. 通信学报, 2022, 43(3): 233-245. |
[10] | 郝一诺, 钟州, 孙小丽, 金梁. 面向IoT场景的动态超表面天线密钥生成方法[J]. 通信学报, 2022, 43(12): 45-53. |
[11] | 霍如, 程祥凤, 孙闯, 汪硕, 黄韬, F.Richard Yu. 区块链网络拓扑优化和转发策略设计[J]. 通信学报, 2022, 43(12): 89-100. |
[12] | 黄桦烽, 苏璞睿, 杨轶, 贾相堃. 可控内存写漏洞自动利用生成方法[J]. 通信学报, 2022, 43(1): 83-95. |
[13] | 张玲翠, 许瑶冰, 李凤华, 房梁, 郭云川, 李子孚. 天地一体化信息网络安全动态赋能架构[J]. 通信学报, 2021, 42(9): 87-95. |
[14] | 姜春晓, 王佳蔚. 高动态卫星DSSS信号Turbo迭代捕获算法[J]. 通信学报, 2021, 42(8): 15-24. |
[15] | 王念平, 郭祉成. 动态密码结构抵抗差分密码分析能力评估[J]. 通信学报, 2021, 42(8): 70-79. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||
|