The Non-negative Matrix Factorization Based Algorithm for Community Detection in Sparse Networks

JIN Hong; HU Zhi-qun

doi:10.12263/DZXB.20210950

您当前的位置：

首页 >

文章列表页 >

The Non-negative Matrix Factorization Based Algorithm for Community Detection in Sparse Networks

PAPERS | 更新时间：2025-12-08

- The Non-negative Matrix Factorization Based Algorithm for Community Detection in Sparse Networks
- ACTA ELECTRONICA SINICA Vol. 51, Issue 10, Pages: 2950-2959(2023)
- 作者机构：
  
  1.湖北大学计算机与信息工程学院，湖北武汉430062
  2.北京邮电大学信息与通信工程学院，北京 100088
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(61977021);Scientific Research Project of Education Department of Hubei Province(Q20211010)
- DOI：10.12263/DZXB.20210950
  CLC： TP391;
- Received：20 July 2021，
  
  Revised：2023-03-06，
  
  Published：25 October 2023
- 稿件说明：
移动端阅览
金红,胡智群.基于非负矩阵分解的稀疏网络社区发现算法[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Motion-Robust Electrocardiogram Signal Sensing Based on Modified Non-Negative Matrix Factorization

A Streaming-Based Overlapping Community Detection Algorithm in Large-Scale Network

A Survey on Algorithms of Non-Negative Matrix Factorization

2kb/s Bayesian Ying-Yang Waveform Interpolative Speech Coding Based on Non-Negative Matrix Factorization

Related Author

CHEN Hui-jie

CAO Ye-tong

LI Fan

LIU Xiao-chen

XIE Huan-ran

LI Hui

ZHANG Jian-peng

CHEN Fu-cai

Related Institution

College of Computer Science, Beijing University of Technology

School of Computer Science and Technology, Beijing Institute of Technology

School of Computer Science and Technology, Shandong University

Institute of Information Technology, Information Engineering University

Department of Electronic EngineeringTsinghua UniversityBeijing 100084China

⁰