Research On Community Structure Detection And Its Application In Complex Network

Many complex systems can be represented as complex networks,which consist of nodes and edges.By utilizing the theory of complex network,we can better understand,predict and control the behaviors of complex systems.With the deep research of complex network,researchers have found that many real networks have community structure,i.e,the connection within each subgraph is denser and sparser between subgraphs.By studying the community structure,researchers can better understand the characteristics and functions in complex networks.There are three issues about the community structure,including the definition,the detection and the application.In this paper,we study the detection and the application for community structure respectively.The main contributions are described as follows:(1)We propose a fast simulated annealing optimization method,which detects community structure by maximizing modularity.Although many methods based on modularity optimization are proposed,they essentially use a greedy strategy to optimize modularity which may be a local maximum.Because of this,this paper takes advantage of simulated annealing method to optimize modularity.Meanwhile,in order to accelerate the convergence of simulated annealing method,we optimize it from two aspects:(4))Obtain an initial community partition by using the hierarchical clustering method;(4)4))extract a component from a chosen community and move it into another community.Experimental results show that the proposed method can not only obtain a high modularity,but also can improve the efficiency greatly compared with the traditional simulated annealing method.(2)We propose a fast method for dynamic community detection,which first take advantage of the communities at previous time step and the network structure at current time step to construct a small network and detect current communities at the small network.Experimental results show that the proposed method improves the efficiency greatly compared with the traditional method.In addition,we propose a fast method for community mapping which first divides each previous community into a few small modules and constructs a small network based on these modules,and then detects communities on the small network.Since each community can be seen as a union of some modules,the similarity between two communities can be computed by counting their common modules.Experimental results show that the proposed method can not only maintain the quality of communities,but also can improve the efficiency of community mapping stage greately.(3)We propose a method which selects a set of critical nodes from communities.For many traditional methods,they usually select the top 6)influential nodes or 6)unconnected influential nodes as critical nodes.However,the 6)critical nodes may locate in a few communities.For a critical node,it is hard to spread its influence from its community to other communities,so the influene of the 6)critical nodes selected by the traditional methods is limited.In order to maximize the influence of a set of critical nodes,we propose three limited conditions:(4))the node is important;(4)4))the node is unconnected with the known critical nodes;(4)4)4))the node is unconnected with the communities which contain critical nodes.Experimental results show that the critical nodes identified by the proposed method are more influential.(4)We propose a fast link prediction method based on community structure.In real networks,links tend to cluster locally and form community structure,the phenomenon indicates that there is correlation between community structure and link formation.So this paper first proposes a method to obtain many independent samples of community partition and then designs two statistics based on these samples,which predict the link probability within communities and between communities respectively.Experimental results show that compared with the classic SBM model,the proposed method can not only predict the missing links accurately,but also can improve the efficiency greatly.In addition,according to the link probability computed by the proposed method,this paper reveals three link formation mechanisms.Experimental results show that the proposed method can obtain higher accuracy in the test set selected by the three link formation mechanismsThe first two works improve the computational efficiency of the static community detection method and the dynamic community detection method respectively,while the last two works apply the community structure to the critical node identification and link prediction respectively.