基于链接密度聚类的重叠社区发现算法  

Density-Based Link Clustering Algorithm for Overlapping Community Detection

作　　者：朱牧[1] 孟凡荣[1] 周勇[1] 

机构地区：[1]中国矿业大学计算机科学与技术学院,江苏徐州221116

出　　处：《计算机研究与发展》2013年第12期2520-2530,共11页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2012AA011004);国家自然科学基金项目(50674086);高等学校博士学科点专项科研基金项目(20110095110010);江苏省研究生科研创新计划项目(CXZZ12_0934)

摘　　要：为了能够更加有效地发现社会网络中具有重叠性的社区结构,提出一种基于链接密度聚类的重叠社区发现算法DBLINK.该算法首先以网络中的边集为对象,将其划分为若干个互不相连的链接社区,再将所得到的链接社区转化为最终的节点社区,隶属于不同链接社区边的交点即为网络中的重叠节点.由于DBLINK采用基于密度的算法对边集进行聚类,将不满足一定条件的边孤立出来,使其不隶属于任何链接社区,因此可以避免社区结构过度重叠的现象发生,从而提高了重叠社区发现的质量.实验结果表明,DBLINK不仅具有较好的时间效率,而且在社区发现的质量方面也优于其他几种代表性的重叠社区发现算法.For detecting overlapping communities efficiently and effectively in various real-world social networks, we propose a novel density-based link clustering algorithm called DBLINK. The proposed algorithm firstly partitions the edge set of the network into disjoint link communities, which will be then transformed into the final node communities. The overlapping nodes will be linked with the edges that are assigned into different link communities. Furthermore, for obtaining the overlapping community structure with high quality and without excessive overlap, DBLINK utilizes the density- based algorithm as the clustering method for the edge set, which has the ability of identifying the isolated edges that are not satisfied with certain conditions and assigning them into no-link community. An empirical evaluation of the method using both synthetic and real datasets demonstrates that DBLINK not only has satisfying time efficiency, but also plays better performance than the state-of-the-art methods at the community detection quality aspect.

关 键 词：社会网络 社区结构 链接密度聚类 社区发现 DBLINK 重叠社区 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]