Research On Non-overlapping Communities Dividing Algorithms In Social Networks

With the rapid development of the Internet, social networks are becoming increasingly large and complex. Social networks are the complex network which consists of people and relationship between people. The structure of communities is a common feature in complex social networks, which is that nodes contact closely in the same community, and nodes contact sparsely in the different communities. The process that Finding small sub-network based on clustering nodes depending on relationship between nodes in the whole network is called "detecting communities" or "finding communities". The style of communities, which have been divided, has two categories of "non-overlapping communities" and "overlapping communities", depending on whether all nodes belong to more than one community situation. Community’s structure of social network could be applied to multiple scenes: recommending friends in the same community, recommending the similar goods for people in the same community.As social networks have the general characteristics of complex networks, people often model social networks based on complex networks, and do some research. How to divide network efficiently and accurately in a complex social network, is the starting and ending point for research on the problems of finding communities in complex network. In this field of research, many scholars put forward many classic algorithms: GN algorithm, spectral bisection algorithm, random walk algorithm, label propagation algorithm, CPM algorithm and EAGLE algorithm.However, in recent years, because social networks are developing exponentially, many classical algorithms will meet more challenges. This paper is focused on the problem of divising network into non-overlapping communities, and propose three algorithms to solve the above problem depending on the different features of social networks.(1) In a small and kown network, this paper put forward ECFM algorithm(Easy Community Finding based on Matrix Algorithm) to solve the problem of finding non-overlapping communities in complex network. This algorithm satisfies the near-linear time complexity, while the algorithm has higher accuracy in a small network. But there are two shortcomings in this algorithm: this algorithm need to specify the number of community networks at start of the algorithm.(2) In the small or middle network, this paper proposes GKNM Algorithm(Genetic K-Means based on Normal Matrix Algorithm) to overcome the shortcomings of ECFM Algorithm, which is based on the thought of Genetic Algorithm and Clustering Algorithm.The algorithm has significantly more than the previous classical algorithm in enhancing the accuracy of the division, but this algorithm cost more time to run, because this algorithm adopting Genetic Algorithm. Moreover, the algorithm selects Normal matrix as clustering model, so, in large networks, this algorithm will run lowly.(3) In large and complex networks, this paper puts forward CMLPA algorithm(Multiple Label Propagation based on Clique Algorithm), which utilizes the characteristics of ultra-low time complexity in the LPA algorithm, and the multiple label propagation model. This algorithm not only is similar to the "LPA" algorithm on the time complexity of the algorithm as near-line, but also is higher than some of the other algorithms on the accuracy of the results. Meanwhile, the CMLPA algorithm follows the computing framework of Pregel, so this algorithm can run perfectly under Spark big data framework.