Community Detection Based On Label Propagation And Community Integration In Complex Network

Complex network is an abstract form of a variety of complex systems,which has some features such as self-organization,self similarity,attractor,small world,scale-free and so on.The community structure is a set of nodes with many internal connections and less external connections in complex networks.Community detection in complex networks is to divide the networks into several sub networks based on the node connection information and network topology structure,which is helpful to understand the evolution process of networks and explore the potential information in the network.More and more methods on complex network community detection are proposed.For example,evolution algorithm,label propagation algorithm and community integration strategies.However,these algorithms are still not perfect,there are some problems,such as low accuracy,slow detection speed,randomness,easy to come to the local optimum,and the limited resolution of the modularity.Today,the amount of network information is rapidly growing,and the community detection in complex network is gradually tending to large data.Therefore,the research on the community detection method based on large-scale network becomes more and more important.In this thesis,three methods have been presented to solve these above problems,the main work is as follows:1)A label propagation algorithm based on circularly searching core nodes for community detection in small and medium scale networks has been presented.Firstly,search the core nodes circularly and divide the network according to the similarity between the core nodes and its neighbors,so as to reduce the possibility of the small community being swallowed,and increase the diversity of the propagation direction of the label propagation.Then implement the label propagation algorithm,then further divide the network after pre-division,so that the randomness of label propagation algorithm can be reduced.Finally,modify the division result according to the node and community membership degree,and detect communities in the network more accurate.The experimental results show that the proposed algorithm is better than the traditional label propagation algorithm.2)A large-scale network community detection method based on weighted label propagation algorithm is proposed.Firstly,find the sets of core nodes which have great influence on the network according to the node degree.The more the connections betweenthe core nodes and the other nodes,the larger the amount of the information these core nodes receive and transform.Then,according to the similarity of the nodes between the core nodes sets and the nodes degree,assign weights to the nodes in the network.So the label of the nodes with great influence will be chosen prior in the label propagation process,effectively improve the accuracy of the label propagation.Finally,a closeness function of nodes and communities is proposed as the objective function of label propagation strategy.The function combine the number of connections between nodes and communities as well as the degree of the nodes belonging to the neighbor communities.This makes full use of the nodes and edges information in the network.The experimental results show that the algorithm can get better results in large-scale networks.3)A community integration strategy based on an improved modularity density increment for large-scale networks is proposed.Firstly,find the local network core node as well as the potential community centers,and divide the neighbor nodes with higher value than the given threshold of into the core node communities.Then sort the initially formed communities in a descending order according to the number of external connections.An improved modularity density increment based on modularity density is proposed as the objective function.In the process of community integration,consider the neighbor community with few external connections prior to avoid wrong fusion.Finally,incorporate global reasoning into the process of local integration.Then calculate and compare the improved modularity density increment of each pair of communities,to determine whether or not they should be integrated,effectively improve the accuracy of community integration.The algorithm solves the problem of the resolution limit of the most community integration algorithm based on the modularity function.The experimental results show that the proposed algorithm is superior to the existing classical algorithms.