Research On Complex Network Community Detection Based On Graph Regularization

There are many complex networks in the real world,such as social networks,biological networks,brain networks and information networks.Community structure is one of the most important inherent properties in complex networks.Generally,a community is a set of nodes that have more internal connections than external connections and at the same time community structure also exhibits the consistence of the properties.Community structure is closely related to the functions,properties,organizational structure and dynamic behavior of complex networks.Thus,mining such structure from complex networks is essential for analyzing and exploring the behavior of many networked systems.Recently,with the rise of complex network theory,community structure receives a lot of attentions and many community detection methods have been developed.Due to the complexity of complex network,many current community detection methods show their inability to detect the intrinsic communities in complex networks.Firstly,it is known that missing,meaningless or even erroneous links are ubiquitous in real world networks and these perturbations make the community structure become vague and hard to detect.Besides,network topological information and node attribute information are often both available in real networks.But they may not be consistent because of noise and interference in the networks.Thus,it is technically challenging to effectively combine these two types of valuable albeit orthogonal information.Finally,complex networks are usually very sparse and noisy.As a result,the current methods are incapable of handling noise in networks.It is obvious that integration of prior information and network topology holds a great potential for community identification.However,most current semi-supervised community detection approaches cannot make full use of the priors,and they usually need many priors to get satisfying results.Thus,how to fully use the priors to improve the detection performance becomes a challenge.Above all,network noise,the combination of network topological information and node attribute information,and prior information fully utilization become three main problems in current community detection methods.The key to solve these problems is how to mine the robust intrinsic structure free from the noise,or make full use of the existing information,such as node attribute information and prior information.It is well-known that graph regularization provides an effective information fusion tool.The existing information is encoded by adding different graph regularization terms to penalize closeness of the nodes,thus obtain robust network partition result.This thesis focuses on the study of community discovery in complex networks.The above problems are solved in the framework of graph regularization perfectly.The main work and innovations are shown as follows:(1)As for the inability to handle noise in networks and identify the vague community structure accurately.It is the first attempt to apply the low-rank learning method for the community detection problem and a low-rank subspace learning based network community detection algorithm is proposed.The key idea is to find the lowest rank representation of all node vectors jointly in the geodesic space using low-rank decomposition strategy.Then the low-rank coefficient matrix obtained by low-rank decomposition strategy is transformed to the association graph in the subspace.At last,a graph regularization term is introduced into the framework of non-negative matrix factorization,considering both original adjacency matrix and subspace learning.The experiment results show that the low-rank subspace learning based network community detection algorithm outperform the other methods.(2)As for the difficulty to combine network topological information and node attribute information which may not be consistent because of noise and interference in the networks,a robust community detection method for attribute networks based on dual graph regularization is proposed.This method makes full use of network topology and node attribute information,considering node attribute matrix,adjacent matrix regularization and attribute correlation regularization into the non-negative matrix factorization framework.Besides,L2,1-norm is used to suppress the noisy links and the outlier node attributes.Thus,a new dual graph regularized robust nonnegative matrix tri-decomposition model is developed and a set of solution methods and iterative updating rules are derived.Experimental results show the competitive performance of the proposed method over the state-of-the-art approaches.(3)As current community detection methods by network topology alone show their inability to handle noise in networks and previous semi-supervised community detection methods are often either dedicated or insufficient to exploit the limited priors.A novel link constraint reliability learning method(LCRL)for semi-supervised community detection is developed.To the best of our knowledge,in semi-supervised community detection problem,it is the first attempt that we utilize the given pairwise constraints and their relationships with network topology to deduce new underlying constraints from the links of original network by assessing their reliability level.As a result,LCRL can have more community identification power than the existing approaches which only consider the given constraints,by benefitting from the derived Cannot-Link constraints.Finally,Must-Link constraint priors based regularization and Cannot-Link constraint priors based regularization are both introduced into the non-negative matrix factorization framework.Experimental results illustrate the effectiveness of our method.