基于图流在线非负矩阵分解的社团检测

doi:10.3969/j.issn.0372-2112.2017.09.004

电子学报 ›› 2017, Vol. 45 ›› Issue (9): 2077-2084.DOI: 10.3969/j.issn.0372-2112.2017.09.004

基于图流在线非负矩阵分解的社团检测

常振超, 陈鸿昶, 王凯, 卫红权, 黄瑞阳

国家数字交换系统工程技术研究中心, 河南郑州 450001

收稿日期:2016-01-11 修回日期:2016-03-29 出版日期:2017-09-25
- 作者简介:
- 常振超,男,1987年生于河北邯郸.国家数字交换系统工程技术研究中心博士生.研究方向为网络分析.E-mail:changzc2012@126.com.cn;陈鸿昶,男,1964年生于河南郑州.国家数字交换系统工程技术研究中心教授,博士生导师,研究方向为网络分析;王凯,男,1980年生于河南许昌,国家数字交换系统工程技术研究中心副研究员,研究方向为无网络分析;卫红权,男,1971年生于河南郑州,国家数字交换系统工程技术研究中心副研究员,研究方向为无网络分析;黄瑞阳,男,1986年生于福建漳州,国家数字交换系统工程技术研究中心讲师,研究方向为无网络分析.
- 基金资助:
- 国家自然科学基金创新群体 (No.61521003）; 国家自然科学基金 (No.61171108）; 国家973重点基础研究发展计划 (No.2012CB315901，No.2012CB315905）; 国家科技支撑计划 (No.2014BAH30B01）

Graph Streams Community Detection via Online Nonnegative Matrix Factorizations

CHANG Zhen-chao, CHEN Hong-chang, WANG Kai, WEI Hong-quan, HUANG Rui-yang

National Digital Switching System Engineering & Technological R & D Center, Zhengzhou, Henan 450002, China

Received:2016-01-11 Revised:2016-03-29 Online:2017-09-25 Published:2017-09-25

摘要/Abstract

摘要： 针对现有的在线社团检测方法大多仅从增量相关的节点和边出发，难以有效挖掘社团结构的动态变化特性问题，提出了一种基于图流在线非负矩阵分解的社团检测方法.首先将网络中持续到达的图数据按照流式数据进行存储和预处理，然后借鉴梯度下降思想，采用在线非负矩阵分解架构，根据不同时刻达到的图流序列，实时迭代更新社团归属矩阵，并通过有效的学习率和缓存策略设置，保证了图流处理的收敛性和合理性.实验结果表明，相比于已有在线社团检测方法，该方法具备更高的社团检测精度.

关键词: 在线, 非负矩阵分解, 图流, 社团检测

Abstract: While the existing online community detection methods mostly only deal with the nodes and edges from the increment part,which are difficult to effectively detect the dynamic changes in the community structure.Based on this,a new method for the detection of flow graphs based on online non negative matrix factorization (ONMF) is proposed.Firstly,our method put graph data into the cache as continuous streams to deal with.Then,our method iteratively updates the existing community belonging matrix real-time using online nonnegative matrix decomposition architecture and by means of the projected gradient descent theory.Lastly,through effective learning rate and cache strategy setting,our method ensures the convergence and rationality of graph stream processing.Experiments on real network data sets show that ONM has a higher community detection quality compared with the existing methods.

Key words: online, nonnegative matrix factorization, graph streams, community detection

中图分类号:

TP393

常振超, 陈鸿昶, 王凯, 卫红权, 黄瑞阳. 基于图流在线非负矩阵分解的社团检测[J]. 电子学报, 2017, 45(9): 2077-2084.

CHANG Zhen-chao, CHEN Hong-chang, WANG Kai, WEI Hong-quan, HUANG Rui-yang. Graph Streams Community Detection via Online Nonnegative Matrix Factorizations[J]. Acta Electronica Sinica, 2017, 45(9): 2077-2084.

参考文献

[18]
[1] Fortunato S.Community detection in graphs[J].Physics Reports,2009,486(3-5):75-174.
[2] 潘磊,金杰,等.社会网络中基于局部信息的边社区挖掘[J].电子学报,2012,40(11):2255-2263. PAN Lei,JIN Jie,et al.Detecting link communities based on local information in social networks[J].Acta Electronica Sinica,2012,40(11):2255-2263.(in Chinese)
[3] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2001,99(12):7821-7826.
[4] 张健沛,邓琨,等.基于边标签传播的复杂网络社区识别方法[J].电子学报,2015,43(6):1113-1118. ZHANG Jian-pei,DENG Kun,et al.Community detection in complex networks based on link label propagation[J].Acta Electronica Sinica,2015,43(6):1113-1118.(in Chinese)
[5] LEE D D,SEUNG H S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999,401(6755):788-791.
[6] 常振超,陈鸿昶,等.基于联合矩阵分解的节点多属性网络社团检测[J].物理学报,2015,64(21):456-465. Chang Zhen-Chao,Chen Hong-Chang,et al.Community detection based on joint matrix factorizaSinica,2015,64(21):456-465.(in Chinese)
[7] 皓慧.Facebook CTO详谈十年愿景:网络连接、AI和VR[EB/OL].http://tech.163.com/16/0817/07/BULDRELV00097U7R.html,2016-08-17.
[8] H Kwak,C Lee,H Park,S Moon.What is twitter,a social network or a news media?[A].Proceedings of the 19th International Conference on World Wide Web[C].New York:ACM,2010.591-600.
[9] Varamesh A,Akbari M K,Fereiduni M,et al.Distributed clique percolation based community detection on social networks using MapReduce[A].20135th Conference on IEEE/ACM Information and Knowledge Technology (IKT)[C].Shiraz,Iran:IEEE,2013.478-483.
[10] Wickramaarachchi C,Frincu M,Small P,et al.Fast parallel algorithm for unfolding of communities in large graphs[A].2014 IEEE High Performance Extreme Computing Conference (HPEC)[C].Waltham,MA USA:IEEE,2014.1-6.
[11] Prat-Pérez A,Dominguez-Sal D,Larriba-Pey J L.High quality,scalable and parallel community detection for large real graphs[A].International Conference on World Wide Web[C].Seoul,Korea:WWW,2014.225-236.
[12] Gregori E,Lenzini L,Mainardi S.Parallel K-clique community detection on large-scale networks[J].IEEE Transactions on Parallel & Distributed Systems,2013,24(8):1651-1660.
[13] Yun S Y,Lelarge M,Proutiere A.Streaming,memory limited algorithms for community detection[J].Advances in Neural Information Processing Systems,2014,2014(4):3167-3175.
[14] Tsourakakis C,Gkantsidis C,Radunovic B,et al.FENNEL:Streaming graph partitioning for massive scale graphs[A].Proceedings Of The 7th ACM International Conference On Web Search And Data Mining[C].New York,USA:ACM,2014.333-342.
[15] Yuan M,Wu K L,Jacques-Silva G,et al.Efficient processing of streaming graphs for evolution-aware clustering[A].Proceedings of the 22nd ACM International Conference on Conference on Information & Knowledge Management[C].Burlingame,USA:ACM,2013.319-328.
[16] Lin Y R,Chi Y,Zhu S,et al.Analyzing communities and their evolutions in dynamic social networks[J].Acm Transactions on Knowledge Discovery from Data,2009,3(2):307-308.
[17] 郭进时,汤红波,王晓雷.基于社会网络增量的动态社区组织探测[J].电子与信息学报,2013,35(9):2240-2246. Guo J,Tang H B,et al.A dynamic community structure detection scheme based on social network incremental[J].Journal of Electronics & Information Technology,2013,35(9):2240-2246.(in Chinese)
[18] Pan G,Zhang W,Wu Z,et al.Online community detection for large complex networks.[A].International Joint Conference on Artificial Intelligence[C].Beijing,China:[U]IJCAI,2013.1903-1909.
[19] Duan D,Li Y,Li R,et al.Incremental K-clique clustering in dynamic social networks[J].Artificial Intelligence Review,2012,38(2):129-147.
[20] Chris D,Tao L,Jordan M I.Convex and semi-nonnegative matrix factorizations.[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2010,32(1):45-55.
[21] Gaussier E,Goutte C.Relation between PLSA and NFM and implications[A].Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval[C].Salvador,Brazil:ACM,2005.601-602.
[22] Cao B,Shen D,Sun J T,et al.Detect and track latent factors with online nonnegative matrix factorization[A].International Joint Conference on Artificial Intelligence[C].Hyderabad,India:IJCAI,2007.2689-2694.
[23] Wang F,Li P,König A C.Efficient document clustering via online nonnegative matrix factorizations[A].Proceedings of the 2011 SIAM International Conference on Data Mining[C].Mesa Arizon,USA:SIAM,2011.908-919.
[24] Guan N,Tao D,Luo Z,et al.Online nonnegative matrix factorization with robust stochastic approximation[J].IEEE Transactions on Neural Networks & Learning Systems,2012,23(7):1087-1099.
[25] Lin C J.Projected gradient methods for nonnegative matrix factorization[J].Neural Computation,2007,19(10):2756-2779.
[26] Cottle R.Nonlinear programming[J].John Wiley & Sons,1979,4(1):67-110.
[27] Yang J,Leskovec J.Defining and evaluating network communities based on ground-truth[J].Knowledge & Information Systems,2012,42(1):745-754.
[28] Mcauley J,Leskovec J.Learning to discover social circles in ego networks[J].Advances in Neural Information Processing Systems,2012,2012:539-547.

基于图流在线非负矩阵分解的社团检测

Graph Streams Community Detection via Online Nonnegative Matrix Factorizations

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陆克中, 陈超凡, 蔡桓, 吴定明. 面向概念漂移和类不平衡数据流的在线分类算法[J]. 电子学报, 2022, 50(3): 585-597.
[2]	张磊, 刘庆, 杨尚尚, 杨海鹏, 程凡, 马海平. 基于双编码的重叠社团检测多目标优化方法[J]. 电子学报, 2021, 49(11): 2101-2107.
[3]	汤萍萍, 董育宁. 基于粒关系矩阵的流量在线分类[J]. 电子学报, 2021, 49(1): 1-7.
[4]	罗大鹏, 杜国庆, 曾志鹏, 魏龙生, 高常鑫, 陈应, 肖菲, 罗琛. 基于少量样本学习的多目标检测跟踪方法[J]. 电子学报, 2021, 49(1): 183-191.
[5]	尤殿龙, 郭松, 赵春慧, 原福永, 申利民, 陈真. 面向分类的流特征在线特征选择算法[J]. 电子学报, 2020, 48(2): 321-332.
[6]	李航, 冯朝胜, 刘帅南, 刘彬, 赵开强. 支持离线/在线加密及可验证外包解密的CP-WABE方案[J]. 电子学报, 2020, 48(11): 2146-2153.
[7]	张二华, 王明合, 唐振民. 加性噪声条件下鲁棒说话人确认[J]. 电子学报, 2019, 47(6): 1244-1250.
[8]	张浩为, 谢军伟, 胡祺勇, 葛佳昂, 宗彬锋, 路文龙. 数字阵列雷达在线交错调度算法[J]. 电子学报, 2019, 47(6): 1260-1266.
[9]	贺超波, 汤庸, 张琼, 刘双印, 刘海. 基于增量式鲁棒非负矩阵分解的短文本在线聚类[J]. 电子学报, 2019, 47(5): 1086-1093.
[10]	汪林玉, 谷科, 余飞, 尹波, 廖年冬. 基于个人意愿的社会网络团体结构与信息检测方案[J]. 电子学报, 2019, 47(4): 886-895.
[11]	谷允捷, 胡宇翔, 丁悦航, 谢记超. 基于流量演化感知的服务功能链在线弹性编排策略[J]. 电子学报, 2019, 47(10): 2192-2201.
[12]	魏波, 吴瑞峰, 张文生, 吕敬钦, 王莹莹, 夏学文. 具有双重稀疏机制的在线学习算法[J]. 电子学报, 2019, 47(10): 2202-2210.
[13]	金宏桥, 董一鸿, 陈华辉, 钱江波. 分布式环境下基于马尔科夫链的图流三角近似计算[J]. 电子学报, 2018, 46(9): 2139-2148.
[14]	吴志鹏, 杨苹, 姜新宇, 崔勇. 在线监测信息系统结构层次设计与实践[J]. 电子学报, 2018, 46(11): 2803-2808.
[15]	范利云, 左万利, 王英, 王鑫. 一种基于差分隐私和时序的推荐系统模型研究[J]. 电子学报, 2017, 45(9): 2057-2064.