赵宇红，韩丽文

(内蒙古科技大学 信息工程学院，内蒙古 包头 014010) E-mail：zhaoyuhong35@163.com

1 引 言

真实世界中存在着各种各样的网络，这些网络中的实体可以抽象为节点，而实体间的联系可以抽象为边.为了挖掘这些节点和边的丰富信息，社区发现研究随之而生.社区发现，是指将网络中相似性高的节点划分到个同一社区中，使得社区内节点联系强于社区间联系.社区发现可以为个性化服务、信息推送、疾病传播中断、信息检索等提供数据.2009年之前对于社区发现的研究都集中在同质网络，即将所有的节点和边都看作是同一种.但是现实中的网络大多是异质的，即网络中有多种类型的节点和边，异质信息网络[1]包含更多的信息和更丰富的语义.另一方面，社区具有重叠性是真实社区的一个显著特征，某些节点并不仅存在于单一社区，可能同时属于多个社区，这些节点被称为重叠节点，它们所属的社区被称为重叠社区.对异质网络进行重叠社区发现，能够更加准确的描述网络真实的结构信息，因此研究异质网络重叠社区具有突出的现实意义.

随着社区发现的概念被提出，学者们相继提出了很多社区发现算法，如基于分裂的算法，基于派系过滤的算法，基于局部扩展的算法，基于标签传播的算法等.其中标签传播算法因接近线性的时间复杂度且不需要提前指定社区的个数而被广泛的应用于大规模网络的社区划分.扩展标签传播算法SLPA[2](Speaker-listener Label Propagation Algorithm)通过定……