邱少明,於 涛,杜秀丽,陈 波

(1.大连大学 通信与网络重点实验室,辽宁 大连 116622; 2.岭南师范学院 信息工程学院,广东 湛江 524048)

0 概述

网络是由节点和连线构成,表示不同对象之间的相互联系。在现实生活中,存在蛋白质网络[1]、神经网络[2]、社会网络[3]等各种类型的网络,不同的网络具有不同的结构和属性,而不同的属性也会表现出不一样的特征。随着对网络研究的进一步深入发现网络中存在一种特殊的拓扑结构,其主要特点是在该网络结构内的节点联系非常紧密,在网络结构之间的节点联系相对稀疏,研究人员将该结构特征初步定义为网络社团现象[4]。社会网络的社团宏观结构体现了网络成员之间的联系,反映了成员之间的关系属性,可以被定义为社会成员之间紧密相连的集合。

目前,社团划分方法主要包括基于模块度的社团划分方法、基于图划分的社团划分方法和基于层次聚类的社团划分方法。基于模块度的社团划分方法由NEWMAN于2004年提出[5],其核心是一种分层贪婪算法,如Fast-Unfolding算法[6],可以快速实现对社团的划分,但容易陷入局部最优,不适用于大规模的网络社团划分。基于图划分的社团划分方法[7]如Kernighan-Lin算法[8]、谱平分算法等,均是经典的图谱理论划分算法,需要预知社团数目才可实现社团划分。基于层次聚类的社团划分方法[9]尽管具有较好的社团划分效果,但是聚类标准的选取对划分质量影响较大。

在此基础上,文献[10]提出局部社团检测算法,通过不同的隶属函数进行动态检测,但其是针对局部社团进行划分,忽略了网络全局特性,对网络整体结构的判断不够准确,容易陷入局部最优。……