Community Detection Based On Evolutionary Algorithm And Node Local Information

The problem of community detection in complex networks is to make use of the information of toplogy relation between nodes to find the community structure in which nodes connect closely within the same community but connected sparsely with other communities.Through the study of these community structures in networks, of, we can better understand the internal structure of complex networks and mining the potential useful information of the nodes. With the continuous development of computer science and technology, the application of the model of complex networks continues to permeate all aspects, from scientific research and data information mining. Therefore, as the important research direction, community detection in recent years have arouse more and more scholars and researchers? attention, the corresponding algorithms such as hierarchical clustering algorithms, spectral clustering and multiobjective optimization method based on evolutionary algorithms. However, at present, these algorithms have problems of low accuracy and slow convergence. At the same time, with the advent of the information age, the complex network scale is also growing and it?s difficult for the existing algorithms to detecte community structure in large scales. Therefore, according to the above problems, three community detection algorithms have been designed and the main work are as follows:1. A Multiobjective Evolutionary Algorithm based on Affinity Propagation(APMOEA) is presented. This method employs an efficient data clustering method, namely affinity propagation algorithm, to get the preliminary partition results of networks with high accuracy in a fast and stable way. And then a multi-objective evolutionary algorithm is employed for a further search to reach the global optimization, thus the algorithm achieves better detection results and converges in a fewer steps..2. A method using local central node and community integration strategy based on label propagation is proposed to solve the large-scale complex network community detection. The label propagation algorithm(LPA) is a semi-supervised learning algorithm for community detection in large-scale networks, which has very low time complexity of O(m). However, the results obtained by LPA have characteristics of randomness, whichis affected by the propagation sequences according to which update the labels of these nodes as these squences are genrerated randomly. Therefore, the proposed algorithm adds a strategy based on the local central nodes and community integration to LPA, which first uses the similarity between the central node and its neighbor nodes to form small local communities, then merges some small communities through the relationship between the central nodes, and finally label all the nodes based on the basis of the thought of the label propagation. The proposed algorithm inherits the advantage of LPA with the low time complexity, and at the same time improves the detection accuracy. The experiments results on the large-scale real networks show that the proposed algorithm superior to the label propagation algorithm.3. A Large-scale community detection method based on node membership grade and sub-communities integration is proposed. Firstly, the proposed algorithm integrate the nodes with high close degree based on the membership function of the local neighbor nodes, which can both improve the accuracy of the existing algorithms and mine the complete sub-graph structure quickly. Then, modify the resulting network based on the membership function of the local nodes and the neighbor community, adjust the parameters of which, the overlapping communities can be detected when non-overlapping communities are being detected accurately. At the same time, the proposed algorithm is appropriate to the problems to detect the large-scale networks using the label propagation framework with low computational complexity. The experiments of the artificial networks and the real networks show the proposed algorithm has better performance than the existing classical algorithm.