节点相似度标签传播在社会网络中的应用研究  

Applied research of node similarity label propagation in social networks

作　　者：夏磊[1,2] 张乐君[1] 国林[1] 张勇实[1] 张健沛[1] 杨静[1] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001 [2]大连飞创信息技术有限公司,辽宁大连116023

出　　处：《计算机工程与应用》2014年第14期103-109,共7页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61073043;No.61073041;No.61100008);黑龙江省自然科学基金(No.F200901;No.F201023);高等学校博士学科点专项科研基金(No.20112304110011);哈尔滨市优秀学科带头人基金(No.2010RFXXG002;No.2011RFXXG015);中央高校基本科研业务费专项资金(No.HEUCF061002)

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]