基于集聚系数的链接社区发现方法  

Link communities detection on clustering coefficient

作　　者：王志超[1] 于剑[1] 柴变芳[1,2] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044 [2]石家庄经济学院信息工程系,石家庄050031

出　　处：《南京大学学报（自然科学版）》2013年第4期448-455,共8页Journal of Nanjing University（Natural Science）

基　　金：北京市自然科学基金项目面上基金(4112046)

摘　　要：提出一种基于节点集聚系数的链接社区发现方法LCDCC(link communities detection on clustering coefficient),该方法假设社区是网络中的稠密子图,利用网路节点的集聚系数及重叠度发现链接社区.LCDCC可更直观地识别重叠社区;与基于相似度矩阵的聚类方法、统计推理等方法相比,LCDCC可精确地在网络规模的线性时间内发现高浓度链接社区,同时可识别多种角色的节点,如重叠点、桥节点、叶子点等.在人工网络和真实网络上的实验表明,LCDCC可以快速有效的发现有意义的重叠社区结构.We proposed a method,named LCDCC,for link communities detection on clustering coefficient.Based on the assumption that community is a dense subgraph in the network,LCDCC uses the clustering coefficient and overlapping degree of each vertex in the network to detect link communities,which makes it more intuitive to recognize overlapping communities.Compared with the methods based on similarity matrix and the methods based on statistics inference,LCDCC can detect dense link communities in linear time complexity more precisely.In addition,it can recognize the vertices with different kinds of roles,such as overlapping vertices,bridge vertices,and outliers.Experimental results on real-world and synthetic networks show that LCDCC can find meaningful overlapping communities quickly and efficiently.

关 键 词：集聚系数 链接社区 重叠社区 社区发现 

分 类 号：TU998.1[建筑科学—市政工程]