Graph Streams Community Detection via Online Nonnegative Matrix Factorizations

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

doi:10.3969/j.issn.0372-2112.2017.09.004

您当前的位置：

首页 >

文章列表页 >

Graph Streams Community Detection via Online Nonnegative Matrix Factorizations

更新时间：2025-07-16

- Graph Streams Community Detection via Online Nonnegative Matrix Factorizations
- Acta Electronica Sinica Vol. 45, Issue 9, Pages: 2077-2084(2017)
- 作者机构：
  
  国家数字交换系统工程技术研究中心,河南,郑州,450001
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2017.09.004
  CLC： TP393
- Published Online：25 September 2017，
  
  Published：2017
- 稿件说明：
移动端阅览
CHANG Zhen-chao, CHEN Hong-chang, WANG Kai, et al. Graph Streams Community Detection via Online Nonnegative Matrix Factorizations[J]. Acta Electronica Sinica, 2017, 45(9): 2077-2084.
DOI：

CHANG Zhen-chao, CHEN Hong-chang, WANG Kai, et al. Graph Streams Community Detection via Online Nonnegative Matrix Factorizations[J]. Acta Electronica Sinica, 2017, 45(9): 2077-2084. DOI： 10.3969/j.issn.0372-2112.2017.09.004.

摘要

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

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.

关键词

Keywords

references

Views

383

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Community Discovery and Evolution Analysis Method for Dynamic Attributed Networks

An Online Approach for Fragment-Based Caching of Dynamic Web Pages (Key Laboratory of High Confidence Software Technologies (Peking University),Ministry of Education,Beijing 100871,China)

Accelerated Algorithm to Incomplete Nonnegative Matrix Factorization

Robust Speaker Verification Under Additive Noise Condition

Community Detection in Heterogeneous Network with Semantic Paths

Related Author

TANG Yong

CHENG Hao

YANG Jia-qi

CHENG Jun-wei

CHENG Qi-wei

HE Chao-bo

北京

北京大学高可信软件技术教育部重点实验室

Related Institution

Vivo Mobile Communication Co., Ltd.

Pazhou Lab

School of Computer Science, South China Normal University

Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Institute of Intelligent Information Processing, Xidian University

School of Computer Science and Engineering, Nanjing University of Science and Technology

⁰