朱 玲，余本国，冀庆斌

(1.中北大学 理学院，山西 太原 030051；2.海南医学院 医学信息学院，海南 海口 570216；3.山西大学 计算机与信息技术学院，山西 太原 030006)

0 引 言

近年来，网络在很多专业领域已经被广泛应用，网络拓扑可以用来描述自然界中的多种网络系统，例如社交网络、计算机科学网络、电力通信网络等.社区结构是网络的一个基本特征.网络的社区结构性质是指网络中存在着一些聚集程度较高且被称为“社区”的模块[1-2].寻找网络中社区的技术称为社区检测或社区发现，指仅使用网络拓扑中编码的信息来识别社区[3-4].现实网络中的社区可能是重叠或非重叠的[5-6]，本文重点关注非重叠社区检测.非重叠社区检测的结果称为划分或社区划分[5]，指的是将网络的所有节点划成k≥2个互不相交的节点组.

1 相关工作

1.1 社区检测算法

学者们在研究网络社区结构的同时还提出了很多有关社区检测的算法.2002年，Girvan和Vewman提出了GN算法[1]；2004年，Radicchi等在GN算法的基础上提出了边聚类系数算法[7]；2007年，Raghavan等运用了标签传播算法[8]；2004年，Newman提出了Newman快速算法[9]；Newman在提出模块度概念的同时给出了一种基于模块度矩阵的谱算法[2]，2008年，这种谱算法被Leicht和Newman应用到有向网络中[10]；2010年，Guo等[11]用共邻矩阵与增益函数作为网络社区结构划分的目标函数，进一步推导出基于增益矩阵、增量矩阵这两种矩阵的特征值以及特征向量的社区检测划分算法.2014年，Ma等[12]通过判断两个节点与其共享邻居节点能否构成三角形来判断这两个……