Research On Overlapping Community Detection Algorithm Based On Large Scale Complex Networks

In recent years,due to the development of social networks and the rise of big data,community detection has become one of the hotspots of complex network science.As one of the basic and important tasks in the research of complex network,community detection is aimed at digging a set of nodes in the network.The nodes are densely connected among their members,and sparsely connected with the rest of the network.However,there is always existence a situation that some nodes may belong to more than one community at the same time in real world networks,which is the overlapping community structure.Therefore,the detection of overlapping community structure is more important and has practical value.With the development of network science,the size of many complex networks can even contain millions of nodes and billions of edges.It is one of the difficulties in the field of overlapping community detection for such large scale complex networks.Based on this,this thesis makes a deep research on the problem of overlapping community detection in large-scale complex networks,proposes an overlapping community detection algorithm based on weak-cliques for large-scale networks.In addition,in order to solve the problem of overlapping community detection in super large scale complex networks with millions of nodes,this thesis also proposes a fast overlapping community detection algorithm based on local neighborhood information for large-scale complex networks.Both two algorithms are used solve the problem of overlapping community detection on large-scale networks,compared with other overlapping community detection algorithms,the proposed algorithms in this thesis are faster and more accurate.The main research works of this thesis are shown as follows:(1)This thesis proposed an overlapping community detection algorithm based on weak-cliques percolation method.The k-clique percolation method is one of the most commonly used detection algorithms for overlapping community structure,the basic idea is to define the community as a set of complete subgraphs that tend to share many of their nodes.The k-clique percolation method needs to detect all the k-clique in the network,however,the k-clique detection is a NP complete problem.Thus,the time complexity based on k-clique percolation method is very high.In order to improve the efficiency and accuracy of overlapping community detection algorithm,we use the local topology information in the network to rapidly mine the weak-clique structure.In this thesis,the weak-clique is defined as a combination of two key nodes and all neighbors shared by them in the networks.Since only the node's local information is used,it is more efficient to detect the weak-clique than to detect k-clique.In the process of percolation,a new similarity measure is proposed to measure the similarity between the two weak-cliques.And the new similarity measure is used to judge whether the two weak-cliques should be merged to improve the accuracy of the algorithm.In the new similarity index,we not only consider the number of nodes that shared between two weak-cliques,but also the number of links between the weak-cliques.Experimental results on the LFR benchmark dataset and the real world network dataset show that,compared with several existing algorithms for overlapping community detection,the overlapping community detection algorithm based on weak-clique percolation method has obvious advantage in terms of both computational efficiency and quality of found communities.(2)This thesis proposed a fast overlapping community detection algorithmbased on local neighborhood information.With the rise of social networks and the development of the internet era,the scales of the current complex networks become more and more huge.In order to detect the overlapping communirty structure in such complex networks with millions of nodes,in this thesis,we propose a fast overlapping community detection algorithm based on local neighborhood information for large-scale networks,which is called OCLN.The basic idea of OCLN algorithm is that we first use the internal and external degree of nodes to fast expanding community,and then computing the belonging coefficient value according to the contribution of the local neighborhood information of each node.Some nodes with lower belonging coefficient are removed from the community to improve the accuracy of the algorithm.Since the whole algorithm uses the local structure of the network,the time complexity of the OCLN algorithm is linear,that is O(n+m),n is the number of nodes in the network,m is defined as the number of edges.Experimental results on synthetic and real world networks demonstrate the competitive performance of OCLN algorithm over other popular overlapping community detection algorithms in terms of both computational efficiency and NMI accuracy.