A Overlapping Community Discovery Algorithm Based On Node Split

With continuous developing of complex network and rapid increase of socialcommunication technology、the widely used of social network site，make the research aboutcomplex social network went further, the discovery of community structure had big effect onthe research and analysis on complex network, so the research of the community discoveryhad gradually become a hot spot in the study of the complex network.First in this paper, found out the detailed analysis and summary about the developmentprocess of the evolution model of complex networks and the basic theory and the mainfeatures of the complex networks, according to the research object of this paper, studied aboutthe basic characteristics and related theory of the community structure which contained incomplex network. Analyzed and summarized on the main ideas and features of the existingcommunity discovery algorithm.Based on the analysis of the discovery algorithms on overlapping communities, CONGAalgorithm, introducing edge clustering coefficient instead of the edge betweenness and pointbetweenness in algorithm as the reference variable, according to the defect that the algorithmhas a high time complexity and cannot be applied to large networks. While combined theinitial node selected method in the CONGA algorithm, used the edge betweenness and pointbetweenness to find the starting position of the algorithm in the same time to reduce theiteration times of executions., computed nodes split betweenness by edge clusteringcoefficient, for the node which need to split, selected the best split mode by the informationcentrality. By using the local variable edge clustering coefficient as the reference node split onthe basis of CONGA algorithm, reduced the times of loop iterations in the algorithmimplementation process, thus reduced the time complexity of the algorithm.Finally use the data sets which based on real network to design the algorithm simulationexperiment, evaluated the algorithm on the community divided effect and the efficiency in theimplementation. The experiment suggests algorithm which put forward in this paper canimprove the execution efficiency, and obtain fine results of community division.