Community Detection In Complex Networks Based On Gaussian Mixture Model And Non-negative Matrix Factorization

The advent of the computer age has incited an increasing interest in the fundamental properties of real-world networks. Many complex systems can be represented by networks, of which their fundamental components and their relationship represent vertex and edge, respectively. In recent years, community detection of complex networks has attracted many researchers’ attention. Many complex networks, such as Internet, citation network, transportation network, email network, social networking services and biochemical networks, all have community structure. Loosely speaking, community structure refers to the internal nodes connect more closely, and the connection between community relatively sparse. Community structure can deepen our understanding for some phenomena. There are many applications in community detection, from social network analysis to image segmentation, from protein interaction network to circuit layout problem. In online social network, community detection methods support their core services. Their general function, like friend recommendation, personalized recommendation, etc; all need find community structure quickly in large data set. For the past few years, many community detection algorithms are introduced, such as the method based on graph partition, the method based on modularity maximization, the method based on statistics inference and mathematical model, the algorithm based on hierarchical clustering, etc.The community detection on complex networks is very similar to the clustering analysis. Based on the in-depth study of community detection methods on complex networks, Gaussian Mixture Model is applied to community detection on complex networks. In addition, non-negative matrix factorization(NMF) is also applied to community detection on complex networks. This algorithm is very convenient and it needs little storage space. Then NMF provided us a new way to process large-scale data. The main works in this paper are as follows:1. The basic theory of ant colony optimization(ACO) algorithm is studied. As a single objective optimization problem, ACO only has one objective function, and usually confines the solution in the specific range. When the objective is inappropriate, the method may be fail, such as the resolution limit. We introduced multiple objectivestrategies, combined with ACO algorithm. The method can produce a set of Pareto-Optimal solutions.Verify the effectiveness and accuracy of this method in three real-world networks.2. We have studied Gaussian Mixture Model(GMM) and use this popular model to deal community detection problem. Conventional GMM use maximum likelihood estimation(MLE) to do parameter optimization.MLE is a kind of local search, and is sensitive to initial values, is apt to plunge into local minimum, then it cannot get the optimal solution. Against this shortcoming, we firstly use k-means to get a rough idea of the clustering center. We use the result to initialize the parameter. Experiment demonstrate that this method can get better parameter.3. The overlapping community phenomenon in complex networks is studied and we use non-negative matrix factorization(NMF) algorithm to deal with community detection problem. The traditional model of NMF for community detection has disadvantage, the optimization of parameters of this method is not accurate and hard to search the optimal solution, through discretizing the parameter value range, then traverse to get the optimal values of parameters. In this paper, we use genetic algorithm to optimize the parameters, and can find the optimal solution, to get the optimal community structure. And this method can detect the abnormal vertex and overlapping node, and is suitable for large-scale data.This research is supported by the by the Program for New Century Excellent Talents in University(No. NCET-12-0920), the Program for New Scientific and Technological Star of Shaanxi Province(No. 2014KJXX-45), the National Natural Science Foundation of China(Nos. 61272279, 61001202 and 61203303), the Fundamental Research Funds for the Central Universities(Nos. K5051302049, K5051302023, K5051302002 and K5051302028) and the Fund for Foreign Scholars in University Research and Teaching Programs(the 111 Project)(No.B07048).