基于Jaccard和LPA的社团划分算法
Community division algorithm based on Jaccard similarity algorithm and LPA
  
DOI:
中文关键词:  社团划分;Jaccard相似度;LPA
英文关键词:community division;Jaccard similarity;label propagation algorithm (LPA)
基金项目:国家重点研发计划专项(2017YFB1401302,2017YFB0202200)和国家自然科学基金(61572260、61872196)资助项目
作者单位
崔海涛 南京邮电大学 计算机学院,江苏南京210023 
李玲娟 南京邮电大学 计算机学院,江苏南京210023 
摘要点击次数: 675
全文下载次数: 298
中文摘要:
      社会网络记录网络中各个实体间的关联,社团划分是对社会网络中的节点关系的区分归纳。为了提高社团划分的准确率和效率,基于Jaccard相似度算法和标签传播算法LPA,设计了一种适用于非重叠社团的划分算法JLCD。该算法首先针对Jaccard相似度算法的计算结果中存在较多关联性的节点但相似度为零或无法计算的情况,引入了SimRank算法的思想对Jaccard相似度算法进行了改进,并用改进的Jaccard算法来计算节点相似度从而得到初始社团;然后用LPA算法基于初始社团来完成最终的社团划分,以此解决LPA在初始标签分配上消耗资源大的问题,并提高社团划分的稳定性。海豚社会网络、足球队赛事网络和人工生成数据集的社团划分结果表明:JLCD方法能够有效地对社团结构进行划分,并且具有较高的准确度和较低的时间复杂度。
英文摘要:
      The social networks record the associations between the various entities in the networks,and the community division is the differentiation and the induction of the node relationships in the social networks.To improve the accuracy and the efficiency of the community division,based on Jaccard similarity algorithm and label propagation algorithm(LPA),a community division algorithm JLCD suitable for non overlapping communities is designed.Firstly,the algorithm introduces the idea of SimRank algorithm to improve the Jaccard similarity algorithm in the case that there are many related nodes in the calculation result of Jaccard similarity algorithm but their similarities are zero or cannot be calculated,thus the improved Jaccard algorithm is used to calculate node similarity to get the initial communities.Then,the LPA is used to complete the final community division based on the initial communities,so as to solve the problems that the resource consumption is large in the initial label allocation and improve the stability of the community division.The community division results of dolphin social network,football team match network and artificially generated datasets show that the JLCD algorithm can effectively divide the community structure and has higher accuracy and lower time complexity.
查看全文  查看/发表评论  下载PDF阅读器

你是第3753061访问者
版权所有《南京邮电大学学报(自然科学版)》编辑部
Tel:86-25-85866913 E-mail:xb@njupt.edu.cn
技术支持:本系统由北京勤云科技发展有限公司设计

欢迎访问《南京邮电大学学报(自然科学版)》编辑部!