Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (11): 3203-3210.DOI: 10.11772/j.issn.1001-9081.2020020260

• Data science and technology • Previous Articles     Next Articles

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

CHENG Qiwei1, CHEN Qimai1, HE Chaobo2, LIU Hai1   

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

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

成其伟1, 陈启买1, 贺超波2, 刘海1   

  1. 1. 华南师范大学 计算机学院, 广州 510631;
    2. 仲恺农业工程学院 信息科学与技术学院, 广州 510225
  • 通讯作者: 贺超波(1981-),男,广东河源人,副教授,博士,CCF高级会员,主要研究方向:数据挖掘、社会计算;hechaobo@foxmail.com
  • 作者简介:成其伟(1997-),男,广东江门人,硕士研究生,CCF会员,主要研究方向:数据挖掘、机器学习;陈启买(1965-),男,湖南衡阳人,教授,硕士,主要研究方向:数据挖掘、机器学习;刘海(1974-),男,湖南张家界人,副教授,博士,CCF会员,主要研究方向:文本挖掘、深度学习
  • 基金资助:
    教育部人文社会科学研究青年基金资助项目(19YJCZH049);广东省自然科学基金面上项目(2019A1515011292);广州市科技计划项目(201807010043)。

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

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

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

CLC Number: