Research On Community Detection Algorithm Based On Modularity And Non-negative Matric Factorization

In recent years,research in the field of network science has been continuously expanded,and people have gradually discovered that many complex phenomena in nature and even human society can be displayed in the form of complex networks,such as social networks,power grids,citation networks,protein molecular interaction networks,and transportation networks.By modeling the complex network and digging into the hidden community relationships,we can better understand its structure and function.Understanding complex networks provide a great theoretical basis for practical application problems such as information diffusion,recommendation systems,and disease control.Community structure is an important way to understand complex networks,because it is a major topological property of complex networks.It has attracted the attention of a large number of scholars at home and abroad.How to effectively conduct community detection is a research hotspot in complex networks.People have proposed a series of effective community detection algorithms for this problem.Commonly used community detection algorithms can be divided into graph segmentation-based methods,hierarchical clustering-based methods,and modular optimization-based algorithms,which all have achieved good results when used in practical applications.In real life,most complex networks tend to have the characteristics of high-dimensional sparseness,and with the increase of network scale,this characteristic becomes more and more significant.Non-negative matrix factorization(NMF)obtains an interpretable non-negative matrix by decomposing the sparse matrix,and then performs cluster analysis on the non-negative data to effectively detect the fuzzy community structure.Therefore,many community detection algorithms based on non-negative matrix factorization have been successfully applied to high-dimensional sparse complex networks.However,most existing methods based on non-negative matrix factorization have some limitations: 1)Only the first-order topology of the network is used,and the second-order similarity of nodes is not considered,resulting in a lot of useful information being ignored;2)Ignore the important characteristic of the mesoscopic structure of the network,which is an important basis for reflecting the structural characteristics of the community.In response to these problems,this paper restructures the network structure to retain more network information,and on the basis of non-negative matrix factorization,adds the constraints of micro and mesoscopic structures to maximize modularity and node similarity in the community.The main contributions of this article include the following 3 points:(1)Propose a new community detection model(MNMF?cd)based on modularity and NMF.The weighted combination of the first-order and the second-order similarity matrix is used to reconstruct the network structure,and the reconstructed network is used as the decomposition target of the NMF algorithm,which not only makes the community detection of the network more obvious but also avoids the lack of network topology information caused by the sparse matrix.On this basis,the micro-graph regularization constraints and the mesoscopic community structure constraints are considered.The added graph regularization constraints can capture the similarity of the nodes,and the modularity constraints can better preserve the community structure and improve the accuracy of the community division results.(2)An effective iterative update algorithm is proposed to solve the parameters of the model,and the theoretical proof of the correctness and convergence of the algorithm is given,as well as the sensitivity analysis of hyper-parameters.(3)MNMF?cd is evaluated on nine real data sets,and compared with other two latest NMF-based algorithms and three classic community detection algorithms,it proved the rationality and effectiveness of the algorithm in this paper.