高度重叠社区的社区合并优化算法  

Community merger of optimization algorithm for highly overlapping communities

作　　者：武志昊[1] 林友芳[1] 田盛丰[1] 唐锐[1] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044

出　　处：《北京交通大学学报》2011年第3期116-122,共7页JOURNAL OF BEIJING JIAOTONG UNIVERSITY

基　　金：北京市自然科学基金资助项目(4112046)

摘　　要：当原图转换成边图后,在边图上进行社区发现可以天然地得到重叠社区,然而得到的社区往往相互大面积重叠,甚至相互包含,导致社区模块性质量较低.针对这一问题,在得到边图下重叠社区发现算法结果的基础上,我们将进一步以优化重叠社区模块化质量函数为标准进行社区合并,以获得高质量的重叠社区.本文首先提出一种描述社区间重叠程度的重叠系数,并基于此进一步提出一种构建带权社区图的启发式方法,能够快速有效地完成社区合并的过程.在人工生成网络与真实世界网络上的实验,进一步验证了该算法能够在不削弱边图方法速度优势的前提下,提高高度重叠社区的模块性.Through converting the original graph into the line graph,we can find overlapping communities on the line graph naturally.However,the detected overlapping communities always have low quality on modularity because of the high overlap.To this problem,when detecting overlapping communities on the line graph,we will merge the communities that can optimize the modularity to attain the high-quality overlapping communities.In this paper,first we propose a new index to describe the extent of overlap between communities.Based on this index,we design a heuristic method to execute the merging procedure efficiently by constructing a weighted community-graph.Experimental results on synthetic and real-world networks show that our method is succeeded to lift modularity without reducing the speed advantage of line graph based methods.

关 键 词：数据挖掘 图聚类 重叠社区 社区合并 边图 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]