Research On Overlapping Community Detection In Complex Networks

In real life,the majority of complex systems can be abstracted into complex networks,such as biological protein networks,social networks,wireless sensor networks,epidemic spreading networks,etc.Scholars have found that networks not only have the characteristics of free scale?small world and local clustering,but also have the characteristics of community structure.The nodes in community are close connected while the connection betwwen communities is sparse.The nodes in the same community are generally similar in function,which makes the community considered to be helpful to reveal the relationship between the structure and function of the network.Many nodes in the network belong to different communities,which means the producing of overlapping communities.Overlapping is the link between different communities,which can reflect the structure of network more realistic,and is significant to the study of overlapping community.The results and efficiency of the existing community detection algorithms are good enough,but none is perfect.For example,most of the community detection algorithms attempt to divide the whole network,but all the real networks are basically non-scale,means that the majority of nodes are sparse,which in some way may interfere with finding the real community;Some algorithms can divide the community structure,but can not identify the overlapping communities;Some algorithms have good effect on detection the overlapping and non overlapping communities,but are not suitable for large-scale networks.This paper focuses on the research of overlapping community discovery algorithm in complex network.According to the characteristics that the nodes in community are close connected while the connection betwwen communities is sparse,we transformed the community detection problem into finding dense subgraphs in graph,and proposed a top-k limited overlap communities detection algorithm based on the maximum of total density,while satisfying an upper bound on the pairwise Jaccard coefficient between the sets of nodes of the subgraphs.Firstly,we roposed the definition of minimal dense graphs and designed a discovery algorithm of minimal dense graphs,then proposed the overlapping community discovery algorithm Main DS(G,k,a)and Fast DS(G,k,a).In order to finding most of the communities,we proposed an overlap communities detection algorithm based on graph entropy clustering.According to the concept of entropy in information theory,we introduced graph entropy as the standard of module testing.Graph entropy is the depiction of the internal connection and outer link state of the cluster nodes.The lower the graph entropy is,the higher the module degree is,thus we can search local optimal community by minimizing the value of graph entropy.Essentially speaking,this algorithm is a bottom-up seed growth style algorithm,we provided three seed selection solutions:the randon selection?based on degree and based on clustering coefficient.We seted seeds set at the first step,the growth of each seed is independent,one node can participate in the growth of multiple seeds,which made it possible to generate overlapping communities.Finally,its efficiency had been verified through experiments and the results showed that the proposed algorithms were effective.