Abstract: In recently years, detecting communities of social networks has made considerable progress, and has been widely applied in the social networks, World Wide Web, biological networks and many other fields. For the hot issues of community detection in social network, firstly the correlate clustering algorithms based on local information are studied and summarized. Secondly, the label propagation algorithm that is short for Label Propagation Algorithm（LPA） is researched and analyzed in-depth, in order to solve the drawback of the algorithm which the network partition is always not optimal due to the random strategy of LPA, this paper introduces the concept of similarity of node attributes, and proposes label propagation algorithm on the basis of the similarity of node attributes called LPA-SNA（Label Propagation Algorithm based on the Similarity of Node Attributes） for short. Finally, taking the American College football network, DBLP co-researchers network as data set, the paper achieves the original label propagation algorithm and improves label propagation algorithm based on the similarity of node attributes respectively, and compares their performance. Experimental results show that the label propagation algorithm based on the similarity of node attributes is more effective compared with the original label propagation algorithm, which not only enhances quality of the network clustering, optimizes the clustering results, but also reduces the time overhead of the algorithm and improves clustering speed.

Key words: social networks, communities, local information, label propagation, similarity of node attributes

摘要： 近年来，社会网络簇结构挖掘取得了长足的进展，广泛应用在社会网、生物网和万维网等领域中。针对当前研究社会网络簇结构挖掘的热点问题，重点研究基于局部信息的聚类算法，并进行分析总结；对标签传播算法（LPA）进行深入研究与分析，针对该算法中由于随机策略而导致网络划分并非最优的缺陷，引入节点属性相似度的概念，提出LPA-SNA算法；采用美国大学足球赛程网络、科学家合著网络作为数据集，分别实现LPA算法与LPA-SNA算法，并对它们的性能进行比较。实验结果表明LPA-SNA较之原始的LPA算法，提高了网络聚类的质量，优化了聚类效果，同时降低了算法的时间开销，提高了算法聚类速度。

关键词: 社会网络, 簇结构, 局部信息, 标签传播, 节点属性相似度