基于改进对称二值非负矩阵分解的重叠社区发现方法

doi:10.11772/j.issn.1001-9081.2020020260

计算机应用 ›› 2020, Vol. 40 ›› Issue (11): 3203-3210.DOI: 10.11772/j.issn.1001-9081.2020020260

基于改进对称二值非负矩阵分解的重叠社区发现方法

成其伟¹, 陈启买¹, 贺超波², 刘海¹

1. 华南师范大学计算机学院, 广州 510631;
2. 仲恺农业工程学院信息科学与技术学院, 广州 510225

收稿日期:2020-03-10 修回日期:2020-06-10 出版日期:2020-11-10 发布日期:2020-06-24
通讯作者: 贺超波(1981-),男,广东河源人,副教授,博士,CCF高级会员,主要研究方向:数据挖掘、社会计算;hechaobo@foxmail.com
作者简介:成其伟(1997-),男,广东江门人,硕士研究生,CCF会员,主要研究方向:数据挖掘、机器学习;陈启买(1965-),男,湖南衡阳人,教授,硕士,主要研究方向:数据挖掘、机器学习;刘海(1974-),男,湖南张家界人,副教授,博士,CCF会员,主要研究方向:文本挖掘、深度学习
基金资助:
教育部人文社会科学研究青年基金资助项目（19YJCZH049）；广东省自然科学基金面上项目（2019A1515011292）；广州市科技计划项目（201807010043）。

Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization

CHENG Qiwei¹, CHEN Qimai¹, HE Chaobo², LIU Hai¹

1. School of Computer Science, South China Normal University, Guangzhou Guangdong 510631, China;
2. School of Information Science and Technology, Zhongkai University of Agriculture and Engineering, Guangzhou Guangdong 510225, China

Received:2020-03-10 Revised:2020-06-10 Online:2020-11-10 Published:2020-06-24
Supported by:
This work is partially supported by the Youth Foundation of Humanities and Social Sciences of Ministry of Education (19YJCZH049), the Surface Program of Natural Science Foundation of Guangdong (2019A1515011292), the Science and Technology Planning Program of Guangzhou (201807010043).

摘要/Abstract

摘要： 针对复杂网络社区结构具有重叠性的问题，目前已提出许多不同类型的解决方法，其中基于对称二值非负矩阵分解（SBNMF）的重叠社区发现方法是具有代表性的方法。然而，SBNMF在面对社区内部链接稀疏的网络时，其重叠社区发现性能低下，为此提出一种基于改进SBNMF（ISBNMF）的重叠社区发现方法。首先利用对称非负矩阵分解得到的因子矩阵构建社区内部链接稠密的新网络，然后再使用基于Frobenius范数的SBNMF模型对新网络的邻接矩阵进行分解，最后通过网格搜索法或梯度下降法得到可以显式指示节点的社区隶属关系的二值矩阵。在人工合成的和真实的网络数据集上进行大量实验，结果表明ISBNMF的社区发现性能优于SBNMF和其他代表性方法。

关键词: 复杂网络, 重叠社区发现, 对称二值非负矩阵分解, 网格搜索, 梯度下降

Abstract: To solve the problem of overlapping community detection in complex networks, many types of methods have been proposed, and Symmetric Binary Nonnegative Matrix Factorization (SBNMF) based overlapping community detection method is one of the most representative methods. However, SBNMF performs poorly when dealing with complex networks with sparse links within communities. In view of this, an Improved SBNMF (ISBNMF) based overlapping community detection method was proposed. Firstly, the factor matrix obtained by the symmetric nonnegative matrix factorization was used to construct a new network with dense links within communities. Then, the SBNMF model based on Frobenius norm was used to factorize the adjacency matrix of the new network. Finally, a binary matrix that can explicitly indicate the community membership of nodes was obtained by means of grid search method or gradient descent method. Extensive experiments were conducted on synthetic and real network datasets. The results show that ISBNMF performs better than SBNMF and other representative methods.

Key words: complex network, overlapping community detection, Symmetric Binary Nonnegative Matrix Factorization (SBNMF), grid search, gradient descent

中图分类号:

TP274

成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.

CHENG Qiwei, CHEN Qimai, HE Chaobo, LIU Hai. Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization[J]. Journal of Computer Applications, 2020, 40(11): 3203-3210.

参考文献

[1] GIRVAN M,NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of United States of America,2002,99(12):7821-7826.
[2] CHEN N,LIU Y,CHAO H C. Overlappingcommunity detection using non-negative matrix factorization with orthogonal and sparseness constraints[J]. IEEE Access,2017,6:21266-21274.
[3] LI W,XIE J,XIN M,et al. An overlapping networkcommunity partition algorithm based on semi-supervised matrix factorization and random walk[J]. Expert Systems with Applications,2018,91:277-285.
[4] ROSE P C P,MALATHY N. Detecting overlappingcommunities based on weak cliques in the social networks[J]. International Journal of Pure and Applied Mathematics,2018,119(12):13659-13668.
[5] ZHU J, CHEN B, ZENG Y. Community detection based on modularity and k-plexes[J]. Information Sciences,2020,513:127-142.
[6] LI P, CHIEN I, MILENKOVIC O. Optimizing generalized PageRank methods for seed-expansioncommunity detection[EB/OL].[2019-05-26]. http://postersession.ai.s3.amazonaws.com/aa33813d-9513-4f66-8a0e-475154cdcb9e.pdf.
[7] 赵学华, 杨博, 陈贺昌, 等. 一种高效的随机块模型学习算法[J]. 软件学报,2016,27(9):2248-2264. (ZHAO X H,YANG B, CHEN H C, et al. Fast learning algorithm for stochastic blockmodel[J]. Journal of Software,2016,27(9):2248-2264.)
[8] CAO X, WANG X, JIN D, et al. Identifying overlappingcommunities as well as hubs and outliers via nonnegative matrix factorization[J]. Scientific Reports,2013,3:No. 2993.
[9] ZHANG Z, WANG Y, AHN Y Y. Overlappingcommunity detection incomplex networks using symmetric binary matrix factorization[J]. Physical Review E:Statistical,Nonlinear,and Soft Matter Physics,2013,87(6):No. 062803.
[10] 胡丽莹, 郭躬德, 马昌凤. 基于对称非负矩阵分解的重叠社区发现方法[J]. 计算机应用,2015,35(10):2742-2746. (HU L Y,GUO G D,MA C F. Overlappingcommunity discovery method based on symmetric nonnegative matrix factorization[J]. Journal of Computer Applications,2015,35(10):2742-2746.)
[11] SHI X,LU H,JIA G. Adaptive overlappingcommunity detection with Bayesian nonnegative matrix factorization[C]//Proceedings of the 2017 International Conference on Database Systems for Advanced Applications,LNCS 10178. Cham:Springer,2017:339-353.
[12] JIN H,YU W,LI S. Graph regularized nonnegative matrix trifactorization for overlappingcommunity detection[J]. Physica A:Statistical Mechanics and its Applications,2019,515:376-387.
[13] YE F, CHEN C, ZHENG Z, et al. Discrete overlappingcommunity detection with pseudo supervision[C]//Proceedings of the 2019 IEEE International Conference on Data Mining. Piscataway:IEEE,2019:708-717.
[14] VANDAELE A,GILLIS N,LEI Q,et al. Coordinate descent methods for symmetric nonnegative matrix factorization[EB/OL].[2019-11-06]. https://arxiv.org/pdf/1509.01404.pdf.
[15] KUANG D,DING C,PARK H. Symmetric nonnegative matrix factorization for graph clustering[C]//Proceedings of the 2012 SIAM International Conference on Data Mining. Philadelphia, PA:SIAM,2012:106-117.
[16] WANG F,LI T,WANG X,et al. Community discovery using nonnegative matrix factorization[J]. Data Mining and Knowledge Discovery,2011,22(3):493-521.
[17] ZHANG Z,LI T,DING C,et al. Binary matrix factorization for analyzing gene expression data[J]. Data Mining and Knowledge Discovery,2010,20(1):No. 28.
[18] YAN C,CHANG Z. Modularized tri-factor nonnegative matrix factorization forcommunity detection enhancement[J]. Physica A:Statistical Mechanics and its Applications, 2019, 533:No. 122050.
[19] MCAULEY J,LESKOVEC J. Learning to discover social circles in ego networks[C]//Proceedings of the 25th International Conference on Neural Information Processing Systems. Red Hook, NY:Curran Associates Inc.,2012:539-547.
[20] LANCICHINETTI A,FORTUNATO S,KERTÉSZ J. Detecting the overlapping and hierarchicalcommunity structure incomplex networks[J]. New Journal of Physics,2009,11:No. 033015.
[21] 姚新亮, 钟诚. 识别高质量重叠社区的高效算法[J]. 小型微型计算机系统,2016,37(3):412-416. (YAO X L,ZHONG C. Efficient algorithm for identifying high quality overlappingcommunity[J]. Journal of Chinese Computer Systems,2016,37(3):412-416.)
[22] SHEN H,CHENG X,CAI K,et al. Detect overlapping and hierarchicalcommunity structure in networks[J]. Physica A:Statistical Mechanics and its Applications,2009,388(8):1706-1712.

基于改进对称二值非负矩阵分解的重叠社区发现方法

Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.
[2]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.
[3]	王锦凯, 贾旭. 基于迁移孪生非负矩阵分解的静脉识别算法[J]. 计算机应用, 2021, 41(3): 898-903.
[4]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[5]	王锦凯, 贾旭. 基于加权正交约束非负矩阵分解的车脸识别算法[J]. 计算机应用, 2020, 40(4): 1050-1055.
[6]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.
[7]	刘昱阳, 李龙杰, 单娜, 陈晓云. 融合聚集系数的链接预测方法[J]. 计算机应用, 2020, 40(1): 28-35.
[8]	王西龙, 王继成, 罗成, 田秀霞. 时间尺度与选择倾向性协同作用下的演化博弈模型[J]. 计算机应用, 2019, 39(6): 1824-1828.
[9]	张希, 朱利, 刘路辉, 詹杭龙, 卢艳民. 基于多层网络的银行间市场信用拆借智能风险传染机制[J]. 计算机应用, 2019, 39(5): 1507-1511.
[10]	杨雄, 姚蓉, 杨鹏飞, 王哲, 李海芳. 以脑电图子序列特征向量为节点的脑网络分析方法[J]. 计算机应用, 2019, 39(4): 1224-1228.
[11]	樊玮, 谢聪, 肖春景, 曹淑燕. 基于组合类别空间的随机游走推荐算法[J]. 计算机应用, 2019, 39(4): 984-988.
[12]	刘正铭, 马宏, 刘树新, 李海涛, 常圣. 融合节点描述属性信息的网络表示学习算法[J]. 计算机应用, 2019, 39(4): 1012-1020.
[13]	邱宁佳, 丛琳, 周思丞, 王鹏, 李岩芳. 结合改进主动学习的SVD-CNN弹幕文本分类算法[J]. 计算机应用, 2019, 39(3): 644-650.
[14]	罗靖宇, 唐宁九. 基于边划分理论的谣言传播模型[J]. 计算机应用, 2019, 39(11): 3409-3414.
[15]	杜航原, 裴希亚, 王文剑. 面向属性网络的重叠社区发现算法[J]. 计算机应用, 2019, 39(11): 3151-3157.