李 艳,贺 静,武优西

1(河北工业大学 经济管理学院,天津 300401)2(河北工业大学 人工智能与数据科学学院,天津 300401)3(河北省大数据计算重点实验室,天津 300401)

1 引 言

现实世界中存在许多复杂的系统,如人际关系网、捕食者关系网、城市交通网、蛋白质合作网等,这些复杂系统都可以抽象成复杂网络进行分析与研究.复杂系统中的实体用节点表示,而实体间的关系用边表示.复杂网络的一个重要特性是社区结构(也被称为“模块”或“簇”等),它是指网络由若干个社区组成,同一社区内的节点彼此之间连接紧密,而不同社区之间的连接稀疏[1].社区发现研究的目的就是挖掘复杂网络中的社区结构.社区发现能够揭示复杂网络中的群体共性,准确理解网络内部的拓扑结构,从而为利用和改造网络提供指导,推进实际应用研究,所以社区发现已经成为复杂网络研究的热点之一.

社区发现的早期研究侧重于非重叠社区发现,方法假设每个节点有且仅属于一个社区,并且社区彼此不重叠.代表性算法包括基于图分割方法[2]、基于标签传播方法[3]、层次聚类方法[4]、模块度优化方法[5]等.对非重叠社区发现的研究取得了良好的成果,并提出了很多具有代表性的算法.但是现实世界中,通常一个事物具有多种属性,因此一个事物可以归属于多个类别,若将这种现象推广到社区发现中,就导致重叠社区现象.重叠社区发现是指网络中存在属于多个社区的节点,具体……