Research On Key Technology Of Community Detection Based On Non-negative Matrix Factorization

With the development of network science,humans discover that various complicated system in reality can be modeled by complex networks,such as protein interaction networks,paper cited networks,and political networks.As an important characteristic of complex networks,community structure plays a crucial role in understanding the structural properties of the target network and forecasting its inside behaviors.Therefore,community detection is a popular topic in the area of social network analysis.In order to efficiently and accurately detect the community structure in complex networks,researchers propose five types of community detection algorithms: clique percolation,line graph and link partitioning,local expansion and optimization,fuzzy detection,agent-based and dynamical algorithms.Due to the high-dimensional and sparse nature of realistic complex networks,non-negative matrix factorization algorithm is considered to be the most promising community detection method.The researchers have proposed a large number of community detection algorithms based on non-negative matrix factorization.Albeit some of them have achieved good performance,the existing algorithms can't yield satisfactory results for the following two reasons.Firstly,they ignore the impact of the NMF algorithm itself on the performance.Secondly,the lack of observation information in the network cause community structure to be obscure.For the above problems,this paper proposes the following innovation:1)This paper proposes SNMF-based community detectors with ? and ?-controlled and multiplicative update rules for addressing the problem of community detection.Experiments on large-scale data sets show that the proposed community detection algorithm outperforms traditional SNMF-based ones.2)This paper proposes a second-order proximity method based on point-wise mutual information.In view of the lack of observed data due to various reasons in reality,this paper proposes a method of using second-order proximity information to compensate for the lack of first-order proximity information.3)This paper proposes a community detection algorithm based on point-wise mutual information.Firstly,the algorithm reconstructs the network with the first-order and second-order proximity.Then,using the SNMF algorithm with the graph regularization to detect the community based on the reconstructed network.The experimental results show that the performance of the proposed community detection algorithm based on point-wise mutual information is superior to the most advanced community detection algorithms.