王寒蕊,丁岱宗,张 谧

(复旦大学 软件学院,上海 200438)

长期以来,社区检测一直是数据挖掘领域的一个研究热点.该任务旨在基于仅由节点和边构成的图数据,将相似的节点聚集到社区当中,完成节点-社区隶属关系的分配,期望社区内点的连接相比社区外更密集.例如在论文引用关系网络中,相似方向的论文会被分到同一小组[1,2];在网页超链接网络中,相似内容的网页将被聚集[3].该任务在刻画图数据的社区分布形态的同时,也影响了很多其他图学习任务的发展,例如图表示学习和图链路预测任务等.

目前的社区检测算法主要分为两类:非重叠式和重叠式的社区检测[4,5].非重叠式社区检测的目标是识别不相交的社区,但社区不相交的假设在很多数据集上是难以成立的.例如在社交网络中,一个人可能因为身份或兴趣的多样而同时归属于多个社区.因此社区间存在相交关系,这种重叠式的社区分布在假设上更合理[6].重叠的假设意味着社区检测算法需要对每个节点学习更多的信息,因而带来了更高的复杂性挑战.近几年很多研究工作[2,4,5,7]都着眼于重叠式的社区检测,证实了重叠式的社区建模能带来更精准的结果.

随着图数据的多样化和复杂化,不论是非重叠还是重叠的社区分布,这类传统的平坦式社区分布形态已经不能很好的描述复杂图数据的社区分布,复杂网络中的社区结构通常是分层的[8].针对这个问题,之前……