A Clustering Algorithm Based On Local Information In Social Network

In the real world, a large number of complex systems can be represented and analyzed byabstract social networks. Having discovered the properties of small-world feature andscale-free of social networks, people discover another relevant statistical feature that is thecluster structure, within which the links between nodes are close, but between which nodesconnect to each other are very sparse，reflecting the most fundamental and importanttopological properties of social networks. Social network clustering methods which aim todetect the network clusters being objectively existing, can make a great contribute to analyzethe structures of social network and understand the potential functions and characters ofnetwork. In the past10years, detecting clusters of social networks has made considerableprogress, has been widely applied in the social networks, World Wide Web, biologicalnetworks and many other fields.Firstly，this paper studies the relevant background and theory of social networkclustering, Analyses and summarizes the research state of network clustering methods. On thisbasis, the article explores and researches the algorithms based on local information further,especially analyses the bottleneck factors that affect the performance and effectiveness inLabel propagation algorithm which is short for LPA. In order to improve the clustering speedand quality of network division of LPA, the concept of similarity of nodes’ attributes isintroduced to solve the factors affecting the algorithm, and then an improved labelpropagation algorithm on the basis of the similarity of nodes’ attributes is proposed, calledLPA-SNA for short. Starting from local information of a network, taking into account thesimilarity of the nodes’ attributes information, LPA-SNA takes an almost linear time to detectcluster structures in large-scale data networks. Finally, taking the American College footballnetwork, DBLP co-researchers network as data set, the paper achieves the original labelpropagation algorithm and improved label propagation algorithm based on the similarity ofnodes’ attributes respectively, and compares their performance. Experimental results showthat the label propagation algorithm based on the similarity of nodes’ attributes is moreeffective compared with the original label propagation algorithm, which not only enhancesquality of the network clustering, optimizes the clustering results, but also reduces the time overhead of the algorithm and improves clustering speed.