基于Jaccard和LPA的社团划分算法

Community division algorithm based on Jaccard similarity algorithm and LPA

社会网络记录网络中各个实体间的关联,社团划分是对社会网络中的节点关系的区分归纳。为了提高社团划分的准确率和效率,基于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.