用于社团分析的差异性度量方法  

Vertex dissimilarity in community discovery

作　　者：孙正[1] 宋文军[1] 王崇骏[1] 谢俊元[1] 

机构地区：[1]计算机软件新技术国家重点实验室南京大学计算机科学与技术系,南京210093

出　　处：《南京大学学报（自然科学版）》2010年第5期528-534,共7页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(60503021;60721002;60875038);江苏省科技支撑计划(BE2009142;BE2010180);教育部重点项目(108151)

摘　　要：在经典的社团发现算法中,相似性往往作为聚类方法的标准而存在.本文从当前社团发现研究的顶点相似性的反面出发,提出顶点差异性,并且提出了从顶点自身出发,从一个顶点出发两种差异性度量方法;根据提出的顶点差异性,应用于当前的常用社团发现算法,得出结果进行对比分析.Community discovery,which is an important application of data mining in social network analysis,is used to divide the network into distinct groups through detecting the relationship between vertices and edges.Within these groups there are many connections between vertices,but between groups there are fewer.This property can reflect the inner structure of the network.Clustering algorithm frequently uses similarity as a standard in its clustering progress.Based on the inverse of vertex similarity,we put emphasis upon using dissimilarity between vertices to find all the communities in the network.There are also two methods to measure the dissimilarity,respectively based on the vertex itself and the other vertex in the network.Applying the two kinds of dissimilarity to the classic Girven-Newman algorithm（GN）,we discover two improved GN algorithms,and in the end,compare results of the two methods according to the current community discovery algorithms.We show that,in some cases,can greatly improve the efficiency of the our method.Our algorithms are meaningful for the future research on community discovery.

关 键 词：顶点差异性 社团发现 社会网络分析 

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