Research On Methods For Community Detection In Complex Networks

In a real world,many complex systems can be expressed in the form of complex networks,such as social networks,software networks and biological networks.Currently,the research on complex networks has become a hot spot in the fields of computer science,social science,physics and bioinformatics,and also become an important cross-discipline research field.The research shows that there exists an important network topology structure characteristic in complex networks:community structure with the characteristics of nodes of an intra-community being closely connected and nodes of inter-communities being loosely connected.The community detection of complex networks aims to disclose the really-existing community structure in networks,which has an important theoretical and practice significance in analyzing the characteristics of network topology structure,finding the hidden rules in networks and mastering the evolution process of networks.In recent years,a large number of researchers have proposed many excellent methods for community detection of complex networks which have been applied to some fields in real life.But the current algorithms of community detection still have the defect of low accuracy in community detection,which remains to be further improved and enhanced.Therefore,in view of the deficiency of traditional community detection methods,the researches in this thesis are carried out from four aspects.Firstly,in view of the defects that the community detection methods based on traditional genetic algorithms have strong randomness and weak optimization search capacity in the process of community detection,we proposed community detection method in complex networks based on improved genetic algorithm and local optimization,IGALO.In this method,a modularity function is selected as an objective function,and the label propagation method of one-time iteration is used to initiate population so as to acquire the original population with certain precision;then an anti-destructive one-way crossover strategy is presented to guarantee that the crossover is operated so that the community structure is developed towards the direction of increasing the modularity function;finally,on the basis of considering both the inner connection similarity between nodes and community and the connection compactness between nodes and community,the local optimization mutation strategy of nodes is proposed to ensure the improvement of search efficiency of algorithm.This method overcomes the defect of weak optimization search of traditional algorithms and improves the accuracy of community detection.The algorithm is tested over benchmark networks and real-world networks and compared with several typical algorithms for analysis.The experiment results verify the validity and feasibility of IGALO.Secondly,in view of the defects of the local optimum and weak diversity of set of Pareto-optimal solutions easily caused by multi-objective community detection algorithms,we proposed I-NSGAII,a multi-objective community detection method in complex networks based on diversity evolution strategy and NSGAII.In this algorithm,two objective functions which conflict with each other are optimized at the same time:the function for evaluating the compactness of intra-community and the function for evaluating the looseness of inter-community.And a diversity evolution strategy is proposed to enlarge the search space of the algorithm to prevent set of Pareto-optimal solutions from falling into local optimum.In addition,I-NSGAII adopts locus-based adjacency representation strategy,unified label strategy,one-way crossover strategy and local mutation strategy to improve the optimum search ability of the algorithm.The algorithm is tested over benchmark networks and real-world networks,and compared with several typical algorithms for analysis.The experiment results verify the validity and feasibility of I-NSGAII.Thirdly,in view of the randomness and pre-setting the related threshold of traditional algorithms overlapping community detection method based on label propagation,we proposed overlapping community detection method in complex networks based on multi kernel label propagation,OMKLP.On the basis of analysis of node degree and local covering density,the concept of evaluation value of kernel nodes is presented as well as the detection method of local kernel nodes.After seeking out kernel nodes,the labels of neighbors of kernel nodes are assigned with the same labels as kernel nodes so that the advantage of label amount in local range can be obtained in the process of label propagation,thus reducing the random components.And then,an asynchronous label propagation strategy oriented to overlapping community is proposed to propagate labels.This strategy can rapidly make a distinction between inner nodes and outer nodes of communities so as to acquire the structure of overlapping communities.Finally,the analysis method for overlapping nodes is adopted to analyze and arrange the overlapping nodes.Without pre-setting any threshold parameters,the algorithm can detect the structure of overlapping communities accurately.Therefore,it effectively solves the defects of the traditional label propagation algorithms.The algorithm is tested over benchmark networks and real-world networks,and the experiment results verify the validity and feasibility of OMKLP.Finally,using the advantage of link community detection method in high-degree overlapping networks,the relationship between each link and its neighbor link is analyzed from the local perspective and a link attribution density function and a link attribution orientation function for evaluating the attribution community of each link are proposed.And on this basis,the overlapping community detection method based on link label propagation is designed,OLLP.This method first initializes the label of each link in networks with the label of a node which has higher degree in two nodes connecting the link,and then updates iteratively link labels by analyzing the attribution density and attribution orientation of links.Finally,the links with the same label belong to the same community and the corresponding overlapping nodes will emerge naturally.The algorithm is tested over benchmark networks and real-world networks,and the experiment results verify the validity and feasibility of OLLP.