郑少强,赵中英,2,3,冯慧子,李 超,2

1(山东科技大学 计算机科学与工程学院,山东 青岛 266590) 2(中国科学院 深圳先进技术研究院,广东 深圳 518055) 3(桂林电子科技大学 广西可信软件重点实验室,广西 桂林 541004) E-mail:zyzhao@sdust.edu.cn或 lichao@sdust.edu.cn

1 引 言

社会网络是指个体间交互形成相对稳定的社会关系,这种关系通常被形式化表示成图的形式,图中节点表示个体,边表示个体之间存在的某种联系.社区是社会网络最重要的组成单元结构,也是分析社会网络规律、性能等方面重要的参考依据.所谓社区发现,是指把网络中联系紧密或具有相似特征的节点划分为一个簇,即同一社区内部节点间链接稠密,不同社区之间的链接稀疏.研究网络的社区结构有助于揭示网络的组织结构、拓普信息等特性,具有十分重要的意义[1],因此,社会网络中的社区发现引起学术界与产业界学者的广泛关注[2-4].

目前,针对社区发现的研究方法层出不穷,依据采用的求解策略问题,可分为基于优化的社区发现方法和基于启发式的社区发现方法.基于优化的方法是通过设置目标函数来实现社区划分,代表性方法有谱方法和模块性最大化方法[5-7]等;基于启发式策略的方法是通过设置启发式规则寻找最优社区划分,代表性算法有GN算法[8]和WH算法[9]等.此外像基于层次聚类的社区发现方法也能有效划分社区结构,但这种方法一般具有较高的时间复杂度,不适用大规模网络挖掘.2007年,Raghavan等人[10]提出一种基于标签传播……