基于改进的Jaccard相似系数矩阵的社团划分算法  

Community division algorithm based on improvedJaccard similarity coefficient matrix

作　　者：张猛 李玲娟[1] ZHANG Meng;LI Lingjuan(School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

机构地区：[1]南京邮电大学计算机学院,江苏南京210023

出　　处：《南京邮电大学学报（自然科学版）》2018年第6期96-102,共7页Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition

基　　金：国家自然科学基金(61302158;61571238)资助项目

摘　　要：社会网络结构反映了网络中个体节点行为的区域特点以及群体之间的关联性。为了提高社团划分的效率和准确性,设计了一种新的基于改进的Jaccard相似系数矩阵的社团划分算法IJ-CD。该算法首先对社会网络的Jaccard相似系数矩阵中的零元素进行处理得到改进的Jaccard相似系数矩阵;然后基于谱平分法思想将改进的矩阵标准化,并选取适当的特征向量维数;最后应用K-means聚类算法划分社团。基于三个经典社会网络数据集的社团划分实验结果表明:IJ-CD算法不仅在社团结构不很明显时也能很好划分出社团,而且能有效地提高社团划分的准确性和降低时间复杂度。The social network structure reflects the regional characteristics of individual node behavior andthe relevance among groups in the network. To improve the efficiency and the accuracy of the communitydivision,a new community division algorithm based on the improved Jaccard similarity coefficient matrix isdesigned,called the IJ-CD. The algorithm improves the zero elements in the Jaccard similarity coefficientmatrix of the social network to obtain the improved Jaccard similarity coefficient matrix;standardizes theimproved matrix based on spectral bisection method;chooses appropriate eigenvector dimension,and uses K-means algorithm to divide the community. Experimental results based on three classic social networkdata sets show that IJ-CD algorithm can divide the community well even when the community structure isnot very obvious,and improve the accuracy of the community division and reduce the time complexity.

关 键 词：社团划分 Jaccard相似系数 谱平分法 K-MEANS算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]