基于传播影响力的重叠社区划分算法
2018-07-04谭文安陈雅雯潘义博
谭文安,陈雅雯,潘义博
(1.上海第二工业大学 计算机与信息工程学院,上海201209;2.南京航空航天大学 计算机科学与技术学院,南京211106)
0 引言
随着信息技术的迅速发展,复杂网络研究逐渐成为学术界的热点。社区结构与小世界性、无标度性并列,是复杂网络最重要的特性之一,同一社区内部节点之间联系密切,不同社区之间的节点联系稀疏[1]。
目前已有的社区发现算法根据划分所得的社区是否存在重叠节点,可分为重叠社区和非重叠社区。早期的研究多为非重叠社区发现,即将完整的网络拆分成若干个互不相交的子网,较经典的有FN算法(Fast-Newman Algorithm)[2]、GN算法(Girvan-Newman Algorithm)[3]和LPA(Label Propagation Algorithm)算法[4]等。之后涌现了许多经典算法的改进算法,Jin等[4]采用结构相似度取代了GN算法中边介数的概念,从而有效降低了算法的时间复杂度;Zhang等[6]与Peng等[7]分别针对LPA算法的缺陷进行了改进。
随着对复杂网络的深入研究,人们发现大多数真实网络中的节点与社区之间可能并不是简单的“非此即彼”关系,对重叠社区的研究更具有现实意义。为此,Palla等[8]提出了CPM(Clique Percolation Method)算法,该算法通过搜索邻接团来挖掘重叠社区。Gregory等[9]提出COPRA算法(Community Overlap PRopagation Algorithm),对传统LPA算法进行修改,使之适用于重叠社区发现。Lancichinetti等[10]提出LFM算法(Local Fitness Method),该算法通过局部扩展的方法进行重叠社区发现。Shen等[11]提出了基于极大团的凝聚式层次聚类方法,将极大团视为社区的基本单元,用于发现网络中的重叠社区结构。Meghanathan等[12]提出了基于邻域重叠的贪婪社区挖掘算法,以邻域重叠度的递增顺序依次迭代删除网络的边,并以模块度值为算法优化目标。……
