种子节点贪婪扩张的重叠社区发现方法

李 艳,贺 静,武优西

1(河北工业大学 经济管理学院,天津 300401)2(河北工业大学 人工智能与数据科学学院,天津 300401)3(河北省大数据计算重点实验室,天津 300401)

1 引 言

现实世界中存在许多复杂的系统,如人际关系网、捕食者关系网、城市交通网、蛋白质合作网等,这些复杂系统都可以抽象成复杂网络进行分析与研究.复杂系统中的实体用节点表示,而实体间的关系用边表示.复杂网络的一个重要特性是社区结构(也被称为“模块”或“簇”等),它是指网络由若干个社区组成,同一社区内的节点彼此之间连接紧密,而不同社区之间的连接稀疏[1].社区发现研究的目的就是挖掘复杂网络中的社区结构.社区发现能够揭示复杂网络中的群体共性,准确理解网络内部的拓扑结构,从而为利用和改造网络提供指导,推进实际应用研究,所以社区发现已经成为复杂网络研究的热点之一.

社区发现的早期研究侧重于非重叠社区发现,方法假设每个节点有且仅属于一个社区,并且社区彼此不重叠.代表性算法包括基于图分割方法[2]、基于标签传播方法[3]、层次聚类方法[4]、模块度优化方法[5]等.对非重叠社区发现的研究取得了良好的成果,并提出了很多具有代表性的算法.但是现实世界中,通常一个事物具有多种属性,因此一个事物可以归属于多个类别,若将这种现象推广到社区发现中,就导致重叠社区现象.重叠社区发现是指网络中存在属于多个社区的节点,具体可分为:a)派系过滤方法,此类方法认为社区是由多个内部连接紧密的全连通子图组成,定义为k-派系,每个k-派系只属于一个社区,但一个节点可以属于多个k-派系,因此能够发现重叠节点,代表方法包括CPM算法[6];b)基于标签传播的方法,初始化时给每个节点分配唯一的标签,通过迭代更新节点的标签和对标签的隶属度,直到标签不再变化,标签相同的节点划分到同一社区,具有多个标签的节点即为重叠节点,代表方法包括COPRA算法[7];c)基于链接的方法,将聚类对象转换为网络中的边(或称为“链接”),对边进行非重叠的划分,由于节点通常有多条边以其为端点,转换成节点社区时便能发现重叠节点,代表方法包括LINK算法[8];d)基于局部社区优化和扩张的方法,此类方法从局部社区出发,基于优化函数逐步扩张,多个扩张之间会形成交叉区域,由此发现重叠社区结构,代表方法包括LFM算法[9]和GCE算法[10].除上述方法外,还有一些比较经典的方法,比如Gregory 等人[11]提出的CONGA算法,通过节点自身分裂出克隆节点,在分裂节点间添加虚边来发现重叠节点.

基于局部社区优化和扩张的方法,利用网络中局部拓扑结构信息优化局部函数来发现社区结构,因为不需要知道网络的全局拓扑结构,所以对当下节点数越来越多的大型网络表现出一定的优势.种子的选择是基于局部社区优化和扩张方法挖掘社区结构的基础,会影响挖掘质量.Lancichinetti等人[9]提出的LFM算法与Coscia等人[12]提出的DEMON算法都是通过随机选择节点作为种子来扩张社区,不可避免的造成社区发现结果不稳定的情况;而Lee等人[10]提出的GCE算法是在LFM算法上做了改进,通过经典的Bron-Kerbosch算法[13]挖掘网络中的k-派系作为种子,相对于节点,派系的位置是固定的,避免了社区发现结果不稳定的问题,但种子的选择依赖于参数k的选择;Shen等人[14]提出的EAGLE算法选择网络中的极大派系作为种子,忽略次要极大派系,但选择派系作为种子的时间复杂度很高.

本文选择基于点度中心性定义的局部最大度节点作为种子节点来扩张社区,得到的社区质量高,避免了结果不稳定的情况.

2 种子节点贪婪扩张的重叠社区发现算法

本文针对当前局部社区优化和扩张方法种子选择复杂度高和社区发现结果不稳定的问题,提出了一种种子节点贪婪扩张的重叠社区发现算法(Seed Greedy Expansion,SGE),该算法分为两个部分,第一部分利用网络节点的拓扑特征点度中心性寻找种子,第二部分通过基于适应度函数的贪心策略扩张种子为自然社区.

2.1 种子选取

在实际的网络中,通常有一些度很大的节点,称为“中心节点”.这类节点与其他节点联系密切,信息传播能力强,通常位于网络中节点连接较为紧密的区域,且比较分散的分布于整个网络[15],这与社区的定义相符合,为此本文选择这些节点作为种子.节点的中心性可以反映其在网络中的重要性[16].研究人员给出度量中心性的指标包括点度中心性、特征向量中心性、接近中心性和中介中心性等,其中只有点度中心性的计算只需要网络的局部连接信息,其余方法都需要完整的网络拓扑信息.

通常,一个网络可以用无向图G=(V,E)表示,其中V={v1,v2,…,vn}表示网络中的n个节点,E={e1,e2,…,em}表示网络中的m条边.

定义1.点度中心性:节点的度数即为其点度中心性,用Cd(vi)表示,即:

Cd(vi)=d(vi)

(1)

其中d(vi)是节点vi的度数

定义2.局部中心节点:当节点的中心性不小于其所有邻居节点的中心性时,该节点称为网络的局部中心节点.

使用点度中心性来度量网络中节点的中心性时,局部中心节点是局部最大度节点.给定图G中的节点vi,如果节点vi的度大于或等于其所有邻居节点的度,则节点vi是局部最大度节点.局部最大度节点有以下性质:在图G中,vi和vj是两个局部最大度节点,如果d(vi)≠d(vj),则vi和vj不相邻[16].

局部最大度节点中心度大,大部分都分散在网络中,只有当两个局部最大度节点具有相同度数时它们才相邻,所以本文选择局部最大度节点作为种子.具体算法如算法1所示.首先将所有节点标记为0,找到节点集合中度最大的节点放入种子节点集合中,如算法1第2-8行所示;然后将局部最大度节点及其邻居节点标记为1并移出节点集合,如算法9-10行所示;迭代寻找下一个种子,直到所有节点都被标记并移出节点集合.

当网络中存在若干个同时满足度最大的节点,取其中一个.假设一对节点vi和vj同时为度最大的节点,因为度数相同所以vi是vj的邻居,因为社区之间的连接是稀疏的,所以如果vi和vj都被选为种子,由它们扩张形成的社区很可能近似重复.所以在算法1中,当vi被标记为种子时,vj作为vi的邻居也会被标记并从V中移除,所以只选择节点vi作为种子加入到集合S中.

算法1能够找出分布在网络中的局部最大度节点并作为种子,这些种子节点的度未必是网络中最大的,但它们很好的分布在各个社区中,通过扩张这些局部最大度节点发现的自然社区不仅局部性良好,而且社区发现结果覆盖率高.

2.2 局部扩张发现自然社区

对于种子集合S中的每个种子,本文通过迭代添加其邻居节点到社区来发现自然社区.用于扩张社区的方法有很多,包括R方法[16],适应度函数方法[9,10]和标签传播[7]等.Lancichiinetti等人[9]定义的适应度函数方法在合成数据和真实数据集上都提供了良好的结果,所以本文采用适应度函数方法.

定义3.对于网络G=(V,E)中的某个社区C,其适应度f(C)定义为:

(2)

定义4.节点v的适应度f(v)可由公式(3)得到,具体表示为:

(3)

在第一部分找到种子集合后,对种子进行基于适应度函数的贪心策略扩张,即通过对包含种子的临时社区添加或者删除节点达到社区适应度函数的最大值.具体算法如算法2所示.将种子加入临时社区C,首先计算其所有邻居节点的适应度,得到适应度最大的邻居节点vmax,把它加入到临时社区C中,如算法2第2-10行所示;然后清洗社区中具有负适应度的节点,将其从社区中移除,如算法2第12-14行所示,虽然每次循环都会加入最大适应度的邻居节点,但新节点的加入会改变整个社区的结构,此时每个节点对新临时社区的适应度将会更新,因此清洗社区就变得有意义;继续迭代扩张临时社区,直到添加任何节点进去都会降低适应度,由此得到最终社区,将其放入社区集合中,然后继续迭代扩张下一个种子,直到所有种子都被扩张.

从算法中可以看出,在扩张的每次迭代中,更新后的社区都需要重新计算社区内节点及其邻居节点的适应度,这大大增加了计算复杂度,所以本文对算法2进行了优化.

(4)

(5)

如果vi和vj之间有边,则dij为1,否则为0.

2.3 时间复杂度分析

假设网络G=(V,E)包含n个节点m条边,算法1根据节点的点度中心性寻找种子,最坏的情况下找到n个种子,时间复杂度为O(n);假设算法1找到k个种子,算法2依次扩张每个种子,任意一个种子进行社区扩张时,假设有s个节点加入该社区,每一个节点加入社区后都要清洗社区,所以算法2的时间复杂度为O(ks2),s表示平均社区节点规模,最坏的情况s等于n,此时所有的节点在一个社区内,k等于1,时间复杂度为O(n2);所以最坏的情况下SGE算法的时间复杂度为O(n2).

3 实 验

本文选取了人工模拟网络数据集和真实网络数据集进行了实验,对比了当前有代表性的重叠社区发现算法,用于发现重叠社区的分裂方法CONGA、基于标签传播的方法COPRA、基于局部社区优化和扩张的方法LFM算法,验证SGE算法的性能有所提升.

3.1 实验数据

3.1.1 人工模拟网络数据集

表1 LFR基准网络参数说明
Table 1 Parameter description of LFR reference network

参数说明取值NkkmaxCminCmaxOnOmμτ1τ2网络中节点数目网络的平均节点度网络的最大节点度最小社区节点数目最大社区节点数目网络中重叠节点数目重叠节点所属社区数目混合参数度序列的负指数社区规模分布的负指数{1000,5000}155020500.1N[2,8]{0.1,0.3}-2-1

本文采用由Lancichinetti等人[17]提出的LFR模型,LFR基准测试网络通过调节参数来控制生成网络的拓扑结构,性质接近真实网络,并且在生成网络时生成社区,以便将算法的社区发现结果同生成的社区进行对比,验证算法的准确性和性能.LFR模型中参数设置如表1所示,其中混合参数μ取值范围为(0,1],是网络中社区内部节点与外部节点连接的概率,μ越大,表示社区结构越不明显.实验根据N∈{1000,5000},μ∈{0.1,0.3},Om∈[2,8]生成28个LFR基准测试网络.

3.1.2 真实网络数据集

本文选取了5个不同类型、不同规模的真实网络,网络说明如表2所示.

表2 真实网络说明
Table 2 Description of real network

数据集节点数边数说明KarateDolphinFootballEmailPower3462115113349417815961654516594空手道俱乐部网络海豚社会网络美国大学生足球网络电子邮件网络美国电网

3.2 评价指标

3.2.1 人工模拟网络数据集评价指标

对于人工模拟网络,社区结构是已知的,通常采用规范互信息指标NMI(normal mutual information)[18]来比较社区发现结果与真实网络社区划分结果的相似度,其计算方式如公式(6)所示:

(6)

其中,N是网络中节点数目,CA是标准社区划分结果,CB是算法社区划分结果,C是混合矩阵,行对应A的社区发现结果,列对应B的社区发现结果,Cij表示节点既属于A划分的第i个社区又属于B划分的第j个社区,Ci·和C·j分别是矩阵C第i行和第j列的和.

3.2.2 真实网络数据集评价指标

对于真实网络,由于实际社区结构未知,通常采用模块度函数Qov(overlapping modularity)[19]来作为评价指标,如公式(7)所示:

(7)

NMI和Qov的取值范围均为[0,1],值越大,说明社区发现结果越好.

3.3 实验结果

SGE有一个参数α,取值为0.9到1.5,步长为0.1.其他算法的参数设置如下:CONGA的参数是社区的数量c,需要根据模块度函数值确定;COPRA的参数为标签长度v,取值为2到8,步长为1;LFM的参数为α,取值为0.9到1.5,步长为0.1.分别选取各参数下最大的NMI值和Qov值作为最终结果.

3.3.1 人工模拟网络数据集实验结果

本文在生成的28个LFR基准测试网络上进行实验,选取各参数下NMI值最大的情况作为最终结果,实验结果如图1所示,纵坐标是NMI值,横坐标是重叠节点所属社区的数目Om值.

从图1可以发现,随着重叠节点所属社区数量Om的增加,发现社区结构变得越来越困难,4种算法的NMI值都呈现下降趋势,但是SGE算法下降的幅度小于其他算法.从图中还可以发现,SGE算法和LFM算法的社区发现结果优于COPRA算法和CONGA算法,这是因为基于局部社区优化和扩张的方法发现自然社区过程仅与网络局部拓扑结构有关,与整个网络的全局拓扑结构无关,具有一定的优势.对比SGE算法和LFM算法可以发现,LFM算法与SGE算法的结果相差不多,并且有时高于SGE算法,这是因为LFM算法是随机选择种子然后扩张社区,所以它的结果也是不稳定的,通常在实际的网络中,短时间内社区的结构是稳定的,比如人际关系网络中,在一段时间内某个朋友圈的结构是稳定的,在这一点上SGE算法要优于LFM算法.虽然LFM算法有时会优于SGE算法,但SGE算法是稳定的,所以更适合网络的研究与应用.

图1 人工模拟网络对比实验结果Fig.1 Comparison experiment results of artificial simulation network

综上所述,SGE算法相对于CONGA算法、COPRA算法和LFM算法能够在人工模拟网络上得到稳定且较高质量的社区发现结果.

3.3.2 真实网络数据集实验结果

在5个真实网络数据集上进行实验,分别选取各参数下最大的Qov值作为最终结果,实验结果如表3所示.

表3 真实网络对比实验结果
Table 3 Comparison experiment results of real network

算法CONGACOPRALFMSGEKarateDolphinFootballEmailPower0.4140.5010.4730.2250.4590.4220.6110.5420.4590.5460.6610.6360.5980.4620.5550.6420.6870.6100.4840.596

从表3中可以看出,SGE算法在大部分数据集上得到的Qov值都是最好的,其次是LFM算法、COPRA算法、CONGA算法,这与4种算法在模拟数据集上的表现基本一致.虽然5个真实网络大小不同、稀疏程度不同,但是SGE算法都能够得到质量较高的重叠社区结构,表现出一定的优势.例如在Dolphin数据集上,SGE算法Qov值取得了0.678,而其他三种算法均不能达到该性能.

4 总 结

本文提出了一种种子节点贪婪扩张的重叠社区发现方法SGE,该方法分为两个部分,第一部分根据网络的局部连接信息寻找网络中的局部最大度节点作为种子,第二部分基于适应度函数贪婪扩张每一个种子,并在每次加入一个新节点到社区中时清洗社区.本文选取了人工模拟网络数据集和真实网络数据集,并在这些数据集上与CONGA算法、COPRA算法、LFM算法等具有代表性的重叠社区发现方法进行对比性实验,实验结果验证SGE算法的性能有所提升.