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

当原图转换成边图后,在边图上进行社区发现可以天然地得到重叠社区,然而得到的社区往往相互大面积重叠,甚至相互包含,导致社区模块性质量较低.针对这一问题,在得到边图下重叠社区发现算法结果的基础上,我们将进一步以优化重叠社区模块化质量函数为标准进行社区合并,以获得高质量的重叠社区.本文首先提出一种描述社区间重叠程度的重叠系数,并基于此进一步提出一种构建带权社区图的启发式方法,能够快速有效地完成社区合并的过程.在人工生成网络与真实世界网络上的实验,进一步验证了该算法能够在不削弱边图方法速度优势的前提下,提高高度重叠社区的模块性.

Community merger of optimization algorithm for highly overlapping communities

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.