郑文萍，乔艳超，杨贵

（1.山西大学 计算机与信息技术学院，山西 太原 030006；2.山西大学 计算智能与中文信息处理教育部重点实验室，山西 太原 030006；3.山西大学 智能信息处理研究所，山西 太原 030006）

0 引言

现实世界中的复杂系统可以建模为复杂网络如社交网络、科研协作网络、蛋白质相互作用网络等，其中节点代表系统个体，边代表个体间的联系［1］。社区结构是复杂网络的重要特征之一。发现真实网络中的社区结构有助于了解实体之间的相互作用，深入理解和分析复杂系统的群体特征和结构特征。如发现社交网络中有相似兴趣爱好的用户群体、科研协作网络中具有相似研究兴趣的学术团体、蛋白质相互作用网络中行使生物功能的蛋白质复合体等。鉴于此，社区发现算法已被广泛应用个性化兴趣推荐、社会网络分析、蛋白质功能预测等诸多领域［1-3］。

目前已经有许多成功的非重叠社区发现算法用来检测网络中社区间没有共同节点的社区结构。然而在真实网络中，有些节点可能有多个社区归属，如在线社交网络中的用户可能属于不止一个兴趣爱好团体、科研协作网络中一个科学家可能归属于多个研究领域、蛋白质相互作用网络中大部分蛋白质属于多个蛋白质功能复合体，发现复杂网络中的重叠社区得到了越来越多的关注。目前已有的重叠社区发现算法主要包括基于派系过滤的、基于标签传播的和基于局部扩展的重叠社区发现算法等。……