Research On Overlapping Community Detection Algorithm For Complex Network

Various systems in the real world can be abstracted into complex networks.As the important feature of a complex network,the community structure has a very broad application prospect.A community structure represents a collection of individuals with common attributes,which are largely prevalent in various complex networks.For example,users with common interests in social networks can be regarded as a community.By knowing how to more accurately identify the community structure in a networked system,we can grasp the internal laws of complex systems more deeply.Moreover,it is becoming increasingly important to gain a more comprehensive and profound understanding of network topology.However,the process of community mining is fraught with many problems,such as high computational complexity,difficulty in collecting the data of the entire network,overlapping characteristics between communities,and so on,all of which undermine community detection.Therefore,how to make efficient partitioning decision is a key problem to be solved in community detection research.To this end,this thesis focuses on the following:(1)considering the problems of distributed systems cluster management,communication overhead between nodes,and the challenges of large-scale complex networks to a single machine system memory,this thesis proposes a fast local community detection algorithm LSCD based on label propagation to detect communities in undirected complex networks.The LSCD algorithm uses a parallel sliding window model to partition a large-scale undirected complex network stored in a hard disk,and loads data into the memory according to the need.Then,it identifies the disjoint maximal complete graph(community core structure)in each memory data partition,and assigns similar labels and weights to nodes in the same maximal complete graph,which are then used as the complex network seed nodes at the beginning of a network node label update.In the label propagation phase,the LSCD algorithm adopts a synchronous update strategy and stops updating whenever the label number of all nodes in the complex network is not zero to reduce the number of iterations.(2)Existing solutions are either centralized algorithms or parallel algorithms,and need to load the complete knowledge of the entire network.However,in reality,it is not easy to collect the data of the entire network either because of the large size of the actual network or because of privacy issues.In order to overcome the shortcomings of existing solutions,this thesis proposes an effective distributed community detection algorithm,Dis OS.The algorithm communicates and shares data with neighbors by sending messages,and uses local information in community detection.Experiments on real network data sets and artificial network data sets show that the two algorithms proposed in this thesis have high community detection accuracy and fast detection speed for different types of complex networks,and they can better adapt to community structure detection in real complex networks without any prior knowledge.