Research On Social Network Community Division Method Based On Clustering Analysis

In recent years, with the development of Web2.0, the social network has attracted more and more scholars to pay attention and study. Among the many properties, community structure is but also one of the most important but also the most significant properties. Community division can not only help us to understand and analyze structure characteristics of the network, but help us to dig out the hidden information from surface data relationships. In the current study, researchers have found many classic partitioning algorithms, such as Girvan-Newman algorithm, Kernighan-Lin algorithm. However, the balance between accuracy and time complexity of community division algorithm is still a major problem.This thesis focuses on studying on the partitioning algorithms of the community structure. This thesis firstly makes a system analysis and comparison of the advantages and disadvantages of the existing partitioning algorithm. On this basis, from the perspective of cluster analysis, this thesis proposes two improved methods to divide the network. They are Community Division Method Based on Node Similarity Clustering,NSCCDM and Genetic Algorithm Clustering Based Community Division Method,GACCDM.In NSCCDM, by the equation by Euclid and the shortest path, construct firstly a new similarity measure between nodes and generate similarity matrix. Then by comparing the similarity between the nodes, make a cluster for nodes. Finally, by using the module function Q, choose the repeated division nodes to be divided into the most appropriate community.In GACCDM, the main idea is based on the genetic algorithm. At first, the algorithm uses the module function Q as a fitness function, in orer to control the evolution of genetic algorithms. In addition, the directional mutation strategy is adopted to slove the defects of random mutation in the genetic algorithms, to accelerate the convergence rate of the algorithm. Finally, by the combination with the topology of the network and the similarity between nodes, make a genetic cluster for nodes, to complete the division of the community.This thesis makes the code realization for the two methods in java language and apply them to the real society network: the Zachary network,the dolphin network and American football network. The experimental results are consistent with the actual network, which also show that the two methods are accuracy and reliability.