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

• 学术论文 • 上一篇    下一篇

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

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

  1. 国家数字交换系统工程技术研究中心, 河南郑州 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   

  1. 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: 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

中图分类号: