Graph Clustering Algorithms And The Application In Social Network

With the rapid development of information network, the amount of data in the real world is growing exponentially, and the big samples, update quickly, noisy. Therefore, it is important to how to extract useful information from the data, how to mining the community structure in large datas, and how to improve the efficiency. Clustering (or classification) is a hot research topic in mathematics、computer science、 management science and other fields, and it has a wide application in the fields such as pattern recognition, data analysis, communication, biology and business etc. Graph clustering, to analyze the real network by the graph theory, it is one of the important techniques in data mining, and provides a method for the analysis of massive data, and is widely applied to social fields, such as pattern recognition、neural network、genetic network and electronic commerce. Different from ordinary numerical clustering, the clustering based on graph theory has its own particularity, the similarity between data objects in dataset is often expressed by a graph.The social network is popular worldwide with the arrival of the era of Web2.0. With the development of micro-blog, community, space, social networking sites gradually plays an important role in the people’s daily entertainment. As we are familiar with the Facebook and "Renren" also has more than million registered users. Social network data, a large amount of data, and the social network at the same time as a new direction in data mining, attracting more and more attention of researchers, community structure discovery has become an important research direction of social network, but how efficient mining of community structure, has not been fully resolved.Based on such problems, this paper will combine the community structres problems with the graph clustering algorithm, with two of global and local steps to level mining complex network overlapping community structure in social networks, and the introduction of the real data. The main contribution of this paper is as follows:(1) This paper first describes the research background, significance and research situation at home and abroad of the social network, summarizes the algorithm in social network about the community structure and the typical graph clustering algorithms, and analyses the advantages and disadvantages of them.(2) Through the overlapping community heuristic algorithm of mining, GL algorithm is proposed for global and local a new combination, the algorithm first global division of generating candidate seed set, and seed set of local cohesion, dig out the overlapping community structure. (3) Design and implementation of the above algorithm, and its application to network clustering in karate club network and the dolphin family network analysis from the real world benchmark data sets.Based on the data sets for validation, the improved algorithm makes the clustering process is faster, the clustering result is more clear, the proposed algorithm is reasonable and effective, the GL algorithm is proposed in the paper compared with traditional algorithm analysis.