基于非负矩阵分解的稀疏网络社区发现算法

金红; 胡智群

doi:10.12263/DZXB.20210950

您当前的位置：

首页 >

文章列表页 >

基于非负矩阵分解的稀疏网络社区发现算法

学术论文 | 更新时间：2025-12-08

- 基于非负矩阵分解的稀疏网络社区发现算法
- The Non-negative Matrix Factorization Based Algorithm for Community Detection in Sparse Networks
- 电子学报 2023年51卷第10期页码：2950-2959
- 作者机构：
  
  1.湖北大学计算机与信息工程学院，湖北武汉430062
  2.北京邮电大学信息与通信工程学院，北京 100088
- 作者简介：
  
  [ "金红女.1984年10月出生，湖北咸宁人.2006年、2009年、2013年分别于武汉理工大学、武汉大学、武汉大学获工学学士、工程硕士和工学博士学位.现为湖北大学计算机与信息工程学院讲师.主要研究方向为图计算、深度学习、异质网络知识发现与推理.E-mail: anya_1024@163.com" ]
  [ "胡智群女.1989年9月出生，湖北黄冈人.2012年、2018年分别于湖北工业大学、北京邮电大学获工学学士和工学博士学位.现为北京邮电大学信息与通信工程学院副研究员、博士生导师.主要研究方向为环境感知与智能控制、车联网、无线通信.E-mail: huzhiqun@bupt.edu.cn" ]
- 基金信息：
  
  国家自然科学基金(61977021);湖北省教育厅科学研究计划项目(Q20211010)
- DOI：10.12263/DZXB.20210950
  中图分类号： TP391;
- 收稿：2021-07-20，
  
  修回：2023-03-06，
  
  纸质出版：2023-10-25
- 稿件说明：
移动端阅览
金红,胡智群.基于非负矩阵分解的稀疏网络社区发现算法[J].电子学报,2023,51(10):2950-2959.

JIN Hong,HU Zhi-qun.The Non-negative Matrix Factorization Based Algorithm for Community Detection in Sparse Networks[J].ACTA ELECTRONICA SINICA,2023,51(10):2950-2959.
金红,胡智群.基于非负矩阵分解的稀疏网络社区发现算法[J].电子学报,2023,51(10):2950-2959. DOI： 10.12263/DZXB.20210950.

JIN Hong,HU Zhi-qun.The Non-negative Matrix Factorization Based Algorithm for Community Detection in Sparse Networks[J].ACTA ELECTRONICA SINICA,2023,51(10):2950-2959. DOI： 10.12263/DZXB.20210950.

摘要

社区结构是复杂网络的重要特征之一，社区发现对研究网络结构有重要的应用价值.基于非负矩阵分解（Non-negative Matrix Factorization，NMF）的社区发现方法是解决社区发现问题的一类基本方法，然而，大多数不能很好地扩展以适用于大型网络，并且在稀疏网络上往往会失败.由于表达复杂网络拓扑结构特征的邻接矩阵在数据矩阵稀疏时，特征向量的局部化导致基于NMF的方法往往无法工作.本文提出一种基于NMF的稀疏网络社区发现算法，尝试提高使用非负矩阵分解方法进行社区发现的准确性以及普适性.本文提出从局部特征向量学习正则化矩阵用来表达原始网络拓扑结构特征，得到的特征矩阵能够很好地发掘数据矩阵隐含的全局结构有更强的特征表达能力.与邻接矩阵相比，正则化数据矩阵克服了由于稀疏或噪声引起的特征向量（或奇异向量）的局部化问题.在人工网络和现实网络中的实验结果显示：与经典的基于NMF的社区发现算法相比，该算法能够发现更准确的社区结构，同时，在稀疏网络上也有较好的表现.

Abstract

Community structure is one of the important characteristics of complex networks. Community discovery has important application value in the study of network structure. Community discovery methods based on non-negative matrix factorization (NMF) are a kind of basic methods to solve the problem of community discovery. However

most of them can not be well extended to large networks

and often fail in sparse networks. Because of the localization of the feature vector when the data matrix of the adjacency matrix is sparse

the NMF based method is often unable to work. This paper proposes a NMF based sparse network community discovery algorithm

trying to improve the accuracy and fitness of NMF based community discovery methods. By learning the regularization matrix from local eigenvectors

it is able to express the topological features of original network. The obtained eigenmatrix can well explore the global structure implied in complex network and has stronger feature expression ability. Compared with adjacency matrix

regularized data matrix overcomes the localization problem of eigenvector (or singular vector) caused by sparse or noise. The experimental results in artificial network and real network show that compared with the classical NMF based community discovery algorithm

this algorithm can find more accurate community structure

and has better performance in sparse network.

关键词

Keywords

references

FORTUNATO S . Community detection in graphs [J]. Physics Reports , 2010 , 486 ( 3 ): 75 - 174 .

NADAKUDITI R R , NEWMAN M E J . Graph spectra and the detectability of community structure in networks [J]. Physical Review Letters , 2012 , 108 ( 18 ): 188701 .

ZHAO Y P , LEVINA E , ZHU J . Community extraction for social networks [J]. Proceedings of the National Academy of Sciences , 2011 , 108 : 7321 - 7326 .

NEWMAN M E , GIRVAN M . Finding and evaluating community structure in networks [J]. Physical Review E , 2004 , 69 ( 2 ): 026113 .

CLAUSET A , NEWMAN M E J , Moore C . Finding community structure in very large networks [J]. Physical Review E , 2004 , 70 : 066111 .

HASTINGS M . Community detection as an inference problem [J]. Physical Review E , 2006 , 74 ( 3 ): 035102 .

LANCICHINETTI A , FORTUNATO S , RADICCHI F . Benchmark graphs for testing community detection algorithms [J]. Physical Review E , 2008 , 78 ( 4 ): 046110 .

FORTUNATO S , HRIC D . Community detection in networks: A user guide [J]. Physics Reports , 2016 , 659 : 1 - 44 .

YE F H , CHEN C , ZHENG Z B . Deep autoencoder-like nonnegative matrix factorization for community detection [C]// Proceedings of the 27th ACM International Conference on Information and Knowledge Management . New York : ACM , 2018 : 1393 - 1402 .

LI Y , SHA C F , HUANG X , et al . Community detection in attributed graphs: An embedding approach [C]// Proceedings of the AAAI Conference on Artificial Intelligence . New York : AAAI , 2018 : 338 - 345 .

AMINI A A , CHEN A , BICKEL P J , et al . Pseudo-likelihood methods for community detection in large sparse networks [J]. Annals of Statistics , 2013 , 41 ( 4 ): 2097 - 2122 .

SANTO A D , GALLI A , MOSCATO V , et al . A deep learning approach for semi-supervised community detection in Online Social Networks [J]. Knowledge-Based Systems , 2021 ( 6 ): 107345 .

SPERLI G . A deep learning based community detection approach [C]// Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing . Limassol : ACM , 2019 : 1107 - 1110 .

XIE Y , GONG M , WANG S , et al . Community discovery in networks with deep sparse filtering [J]. Pattern Recognition , 2018 , 81 : 50 - 59 .

BICKEL P J , CHEN A . A nonparametric view of network models and Newman-Girvan and other modularities [J]. PNAS , 2009 , 106 ( 5 ): 21068 - 21073 .

CHAUDHURI K , CHUNG F , TSIATAS A . Spectral clustering of graphs with general degrees in the extended planted partition model [J]. Journal of Machine Learning Research , 2013 , 23 ( 35 ): 1 - 23 .

NG A Y , JORDAN M I , WEISS Y . On spectral clustering: Analysis and an algorithm [J]. Advances in Neural Information Processing Systems , 2001 , 14 : 849 - 856 .

LUXBURG U V . A tutorial on spectral clustering [J]. Statistics and Computing , 2007 , 17 ( 4 ): 395 - 416 .

ZELNIK-MANOR L , PERONA P . Self-Tuning Spectral Clustering [J]. Advances in Neural Information Processing Systems , 2005 , 17 : 1601 - 1608 .

Gu M , Zha H , Ding C , et al . Spectral relaxation models and structure analysis for k-way graph clustering and bi-clustering [R/OL]. ( 2001 )[2021]. https://citeseerx.ist.psu.edu/doc/10.1.1.10.2657 https://citeseerx.ist.psu.edu/doc/10.1.1.10.2657 .

SHI J B , MALIK J . Normalized cuts and image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2000 , 22 ( 8 ): 888 - 905 .

DING C , HE X , SIMON H D . On the equivalence of nonnegative matrix factorization and spectral clustering [C]// Proceedings of the 2005 SIAM International Conference on Data Mining . Philadelphia : Society for Industrial and Applied Mathematics , 2005 : 606 - 610 .

SAADE A , KRZAKALA F , ZDEBOROVÁ L . Spectral Clustering of Graphs with the Bethe Hessian [J]. Advances in Neural Information Processing Systems , 2014 , 1 : 406 - 414 .

DHILLON I S , GUAN Y Q , KULIS B . Kernel k-means, spectral clustering and normalized cuts [C]// Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . New York : ACM , 2004 : 551 - 556 .

ZHANG Z Y , WANG Y , AHN Y Y . Overlapping community detection in complex networks using symmetric binary matrix factorization [J]. Physical Review E , 2013 , 87 ( 6 ): 062803 .

NEPUSZ T , PETROCZI A , NEGYESSY L , et al . Fuzzy communities and the concept of bridgeness in complex networks [J]. Physical Review E , 2008 , 77 ( 1 ): 016107 .

BRUNET J P , TAMAYO P , GOLUB T R , et al . Metagenes and molecular pattern discovery using matrix factorization [J]. Proceedings of the National Academy of Sciences , 2004 , 101 ( 12 ): 4164 - 4169 .

Saade A , Lelarge M , Krzakala F , et al . Clustering from sparse pairwise measurements [C]// 2016 IEEE International Symposium on Information Theory (ISIT) . Piscataway : IEEE , 2016 : 780 - 784 .

ZHANG P . Robust spectral detection of global structures in the data by learning a regularization [EB/OL]. ( 2016 )[2021]. https://arxiv.org/abs/1609.02906 https://arxiv.org/abs/1609.02906 .

KRZAKALA F , MOORE C , MOSSEL E , et al . Spectral redemption in clustering sparse networks [J]. Proceedings of the National Academy of Sciences of the United States of America , 2013 , 110 ( 52 ): 20935 - 20940 .

COJA-OGHLAN A . Graph partitioning via adaptive spectral techniques [J]. Combinatorics, Probability and Computing , 2010 , 19 ( 2 ): 227 - 284 .

QIN T , ROHE K . Regularized spectral clustering under the degree-corrected stochastic blockmodel [EB/OL]. ( 2013 )[2021]. https://arxiv.org/abs/1309.4111 https://arxiv.org/abs/1309.4111 .

KUANG D , YUN S , PARK H . SymNMF: Nonnegative low-rank approximation of a similarity matrix for graph clustering [J]. Journal of Global Optimization , 2015 , 62 ( 3 ): 545 - 574 .

ZHANG Z Y , WANG Y , AHN Y Y . Overlapping community detection in complex networks using symmetric binary matrix factorization [J]. Physical Review E , 2013 , 87 ( 6 ): 062803 .

ZHANG Y , YEUNG D Y . Overlapping community detection via bounded nonnegative matrix tri-factorization [C]// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . New York : ACM , 2012 : 606 - 614 .

ADAMIC L A , GLANCE N . The political blogosphere and the 2004 US election: Divided they blog [C]// Proceedings of the 3rd International Workshop on Link Discovery . New York : ACM , 2005 : 36 - 43 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于改进的非负矩阵分解技术的抗运动干扰心电信号感知方法

基于流式分析的大规模网络重叠社区发现算法

非负矩阵分解算法综述

基于贝叶斯阴阳机的2kb/s NMF-WI语音编码算法