Research Of Community Detection Algorithm Based On Label Propagation And Non-negative Matrix Factorization

In the context of the rapid development of the Internet,complex network research has become a popular research direction.Complex networks usually have some nodes with similar attributes or close relationships.The community detection method analyzes the connections between nodes in the complex network.It divides the nodes into different communities to obtain the community network structure.Community detection algorithms can be divided into disjoint community detection algorithms and overlapping community detection algorithms.The traditional nonnegative matrix factorization(NMF)algorithm divides disjoint communities by decomposing the network's adjacent matrix.However,the adjacent matrix only reflects the relationship between each node and its immediate neighbor nodes.The nodes in the same community are often not just direct neighbor relationships.Based on the research of NMF algorithm,we propose two algorithms,one is the disjoint community detection algorithm LPNMF(Label Propagation on Non-negative Matrix Factorization),the other one is overlapping community detection algorithm Link NMF(Non-negative Matrix Factorization on Link-graph).(1)The community detection algorithm LPNMF based on non-negative matrix factorization: the label propagation algorithm is used to divide the network into communities and obtain the modularity.In the community structure obtained by the label propagation algorithm,if two nodes belong to the same community,the value of modularity is added to the element value in the adjacent matrix to enhance the relationship between these nodes.Because label propagation algorithm has the characteristics of high efficiency and instability,we get multiple communities through multiple label propagation,strengthen the relationship between nodes in the same community each time,and then perform non-negative matrix decomposition on the new matrix to get the final community structure of the network.(2)Link NMF,an overlapping community detection algorithm based on nonnegative matrix factorization:firstly,we transform the network into an edge graph,obtain the adjacent matrix of the edge graph.Secondly,similar to LPNMF algorithm,the label propagation algorithm is used to increase the value of the elements belonging to the same community in the adjacency matrix of the edge graph,and then the new matrix obtained by the adjacent matrix of the edge graph and the label propagation algorithm is decomposed by NMF,and the edge partition result is obtained.Finally,the edge graph is restored to the original network.In the membership matrix detected by LPNMF,threshold parameters are set to filter out redundant overlapping nodes and obtain the final overlapping community structure of the network.Experiments are carried out on multiple data sets to compare with multiple algorithms.The result shows that the two algorithms proposed in this paper can obtain high-quality community division results on disjoint networks and overlapping networks.