一种混合的动态社区发现算法

白伊史,翟海霞,刘 园

(河南理工大学 计算机科学与技术学院,河南 焦作 454003) E-mail：liuaspire@163.com

1 引 言

社区结构是复杂网络具有的重要特征之一.根据社区结构是否随时间变化,可将社区发现算法分为动态社区发现算法和静态社区发现算法.而在实际情况中,网络用户的注册与注销活动、社交用户之间的关注与取关以及互动等等都与时间因素密切相关[1].因此研究复杂网络中的动态社区发现算法更具现实意义.

增量式社区发现算法利用网络的历史快照具有的社区结构针对网络的增量变化局部调整社区结构,从而快速得到当前时间片网络的社区划分结果.目前,增量式社区发现”算法已成为主流的动态社区发现算法[2-6].然而,该类算法存在两个问题：一是含累积历史快照社区划分结果中存在的误差;二是当社区演变剧烈时,对增量的处理会增加计算成本,制约算法性能.尽管针对增量式动态社区发现算法开展了大量研究,但是该类算法中由累积误差引起的社区划分结果准确率问题和增量处理引起的性能问题仍然是开放问题.

针对增量式动态社区发现算法存在的问题,本文提出了一种混合的增量式动态社区发现算法,利用模块度增量算法和标签传播算法进行社区划分.该算法将社区的动态变化分为剧烈演变和非剧烈演变两种情况.为了减少增量处理,对于剧烈演变的情况,将对应的网络快照看作独立的网络划分社区.对于非剧烈演变的情况,则采用增量的方式划分社区.在社区划分过程中同时采用了基于模块度优化的Louvain算法和标签传播算法进行社区结构调整,在保留Louvain算法性能优势的同时,利用标签传播算法提高社区的分辨率,即识别小社区的能力.

2 相关工作

在动态社区发现算法[7]中,主要包括基于聚类的算法和基于增量的算法.对于基于聚类的动态社区发现算法,Chen等人[8]提出了一种用于动态网络聚类的多周期MK-均值算法,Liu等人[9]提出了一种基于谱聚类和度校正的全局社区检测方法.基于聚类的算法时间复杂度较高,为了提升算法效率,研究人员提出了增量社区发现算法.郭等人[10]提出了一种基于密度聚类的增量动态社区检测算法.Zhao等人[11]提出了一种通过处理子图来检测社区的增量方法.

基于模块度优化的算法也被应用到增量式社区发现[12],Louvain算法便是其中之一.该算法具有检测社区速度快、准确性高等优点,但也存在不容易辨别出某些特殊小社区的缺点,即存在分辨率局限性问题.Held等人[13]提出了Louvain-dyn算法,该算法仅对增量节点及其邻居节点进行划分,虽然提升了社区划分的效率,但却降低了社区划分的准确率.胡北辰[14]提出一种自适应的动态社区发现算法,该算法重点关注相邻社区的节点变化,针对不同的变化提出不同的增量处理策略对当前时间片网络进行社区划分.Meng等人[15]提出一种基于模块度优化的动态社区检测算法,该算法对Louvain算法进行改进使其适应动态网络,从动态网络中获取平滑演化的社区结构.

上述基于Louvain的动态社区发现算法仍然存在分辨率局限性问题,降低了每个时间片网络社区划分的准确性,存在较大的累积误差.该类算法在进行动态社区发现时对网络中的增量逐一进行处理,忽略了增量之间的联系,无法自适应的检测社区.此外,当网络发生剧烈演变会产生较多增量,而单独对每个增量进行处理则会增加计算成本,制约算法的性能.

3 Louvain算法问题分析及改进

本文用图G=(V,E)表示复杂网络,其中V是节点集合,E是边集合,v和e分别表示单个的节点和边.t时刻的网络快照用Gt表示,Gt的社区结构用CGt表示.

本节在复杂网络图的基础上分析Louvain算法存在的问题并给出解决方法.

3.1 Louvain算法问题分析

Louvain算法包括模块度优化和网络聚合两个阶段[16].在模块度优化阶段,首先将网络中的每一个节点作为独立的社区构造初始网络,然后随机选取网络中的某一节点,针对此节点计算将该节点加入某邻居节点所在社区后的模块度增量：若最大模块度增量大于0,则将该节点加入最大模块度增量对应的社区;反之,则该节点保持原社区不变.重复此过程,直到遍历完网络中的所有节点,并且每个节点的社区归属不再改变为止.在网络聚合阶段,首先根据模块度优化阶段的社区划分结果构建压缩图：将每个社区分别压缩成一个超节点,社区内部边为超节点的自边,社区间的边为相应超节点之间的连边.将每个超节点看作一个独立的社区,按照模块度优化的方法进行社区结构调整,直至所有节点无法改变社区归属时停止.此时的社区划分结果为Louvain算法最终的社区划分结果.

Louvain算法在网络聚合阶段的社区划分实质是在进行社区合并.每一个超节点其实是包含若干节点的一个子图,Louvain算法仅仅依据模块度增量合并社区的做法,没有考虑到合并后社区内部的紧密性,这可能会将本应属于不同社区的节点划分到一个社区内.

此处,以派系网络为例说明这一问题.派系是由若干节点构成的完全图.图1(a)中的网络就由16个派系构成.按照Louvain算法思想,在模块度优化阶段,16个派系划分为16个社区得到的模块度最大,所以将每个派系划分为一个社区,得到图1(b)所示的包含16个社区的网络图;然后将16个社区分别压缩成超节点,构造新网络,得到图1(c)所示的压缩图;在网络聚合阶段,每两个相邻的派系被划分到一个社区,最终得到图1(d)所示的包含8个社区的社区结构,两个派系之间仅有一条边相连,故而社区内部紧密性不强.若把每个派系作为一个社区,则每个社区内部紧密性都很强.因此,Louvain算法在网络聚合阶段仅根据模块度增量进行社区合并的做法并不合理.

图1 派系网络社区划分结果Fig.1 Results of the division of the faction network community

3.2 改进的Louvain算法

针对Louvain算法在网络聚合阶段存在社区划分不合理的问题,本文结合标签传播算法对Louvain算法的网络聚合阶段进行了改进.在网络聚合阶段的社区合并过程中,除了考虑模块度增量因素,还要衡量社区合并后新社区内部的紧密性.只有在模块度和紧密性两项因素同时满足要求时,才进行社区合并.

本文利用标签传播算法对2个社区进行紧密性检查.首先对超节点解压缩,将其恢复为节点和边.然后将涉及紧密性检查的所有节点和相关联的边看作独立的网络,给每个节点初始化唯一的标签并进行标签传播.最后,根据标签传播结果进行紧密性检查.在传播结束后,若两个社区中有标签相同的节点,则认为两个社区连接紧密,适合合并;反之,则认为两个社区连接不紧密,不能合并.

为了避免标签传播中的随机性影响社区划分结果的稳定性,本文在文献[17]原有标签传播策略的基础上引入了新的传播策略,描述如下：

标签传播策略1.若在邻居节点中出现最多的标签同时有多个,则计算这些标签所属节点与当前节点的共同邻居,根据策略2进行标签更新.

标签传播策略2.若与当前节点拥有共同邻居数最多的节点只有一个,则选择此节点的标签更新当前节点;否则,按策略3更新当前节点的标签.

标签传播策略3.从与当前节点拥有共同邻居数最多的节点中随机选择一个节点对应的标签更新当前节点.

算法1. Louvain-INA 算法

输入：由超节点构成的社交网络图Gc=(Vc,Ec)

输出：社区划分

1.将Gc中的每个超节点vc作为一个独立的社区,并计算此时社区划分的模块度←cur_mod;

2.while(true)

3. for eachvcinVcdo

4. 计算vc加入各个邻居社区后的模块度增量;

5. 将最大模块度增量对应的社区加入Clist;

6. matched=false;

7. while(Clist!matched andClist!null)

8. if最大的模块度增量>0

9.C←Clist.get(i)

10.V′←Dec(vc)∪Dec(C);

11. 对V′中的节点进行标签传播;

12. ifDec(vc)和Dec(C)中存在拥有相同标签的节点

13.vc加入社区C;

14. matched=true;

15. else

16. 将C从Clist中删除;

17. end if

18. end if

19. end while

20.end for

21.new_mod←当前社区划分的模块度;

22.if new_mod-cur_mod<θ

23. break;

24.else

25. cur_mod=new_mod

26.end if

27.end while

算法1展示了改进后的网络聚合阶段的算法,记为Louvain-INA算法.以图2虚线框内的超节点为例说明根据Louvain-INA算法融合社区的过程.首先超节点进行解压缩,得到局部网络图;然后对该局部网络进行标签传播,标签传播完成后进行紧密性检查.由于两个超节点分别解压缩并进行标签传播后得到的节点中没有标签相同的节点,所以两个超节点连接不紧密,不能合并为一个社区.由上述过程易知,每个超节点都不加入邻居社区,而做为独立社区存在,最终得到正确的社区划分结果.

图2 划分超节点Fig.2 Partitioning super nodes

4 混合的动态社区发现算法

本文根据网络的演变程度采用不同的方式划分社区.对于网络剧烈演变的情况,将当前时间快照看作静态网络,采用改进的Louvain算法划分社区;对于网络的非剧烈演变,则在改进的Louvain算法基础上设计增量社区发现算法,以增量的方式划分社区.

4.1 社区演变程度分析

社交网络在不同时间的演化程度是不同的.当网络演化程度较小时对应的网络增量较少,在历史社区划分结果的基础上根据网络增量调整社区结构,可以节省社区划分的时间,提升社区划分性能.当网络演变程度较剧烈时会产生过多的网络增量,若此时仍在历史划分结果的基础上进行增量式社区划分,不仅会因为调整过多的增量而导致时间复杂度增加,而且还会在历史划分结果的基础上累积误差.

要解决由于网络剧烈演变而导致的社区划分过程中计算复杂度和累积误差增加的问题,必须对社区网络的演变程度加以区分,针对不同的演化程度采取不同的社区划分方法.为此,本文定义了网络演变度.

定义1.网络演变度.描述相对于t-1时刻,t时刻网络的演变程度,记β(t).

β(t)=1-|St|/|Vt-1|

(1)

β(t)根据式(1)计算.在该式中,St表示t时刻变化的节点集合.本文认为,如果β(t)≤0,则表示Gt相对于Gt-1发生了剧烈演变,此时的节点增量和边增量较多.为减少这些增量对社区划分的计算复杂度和累积误差的影响,将当前时间片网络看作静态网络,采用改进后的Louvain算法划分社区.在β(t)>0的情况下才采用增量的方式划分社区.

4.2 增量式社区发现

当β(t)>0时,本文认为从t-1到t时刻网络经历了非剧烈演变,此时应采用增量式的社区划分方法.网络演变表现为节点的变化和边的变化.节点和边的变化分为两种情况,一是新节点或边的出现,二是已有节点或边的消失.社区内增加边或社区间减少边不会导致社区结构发生改变[18],因此本文只考虑可能会对社区结构造成影响的增量,并将其分为4种类型：1)新节点出现;2)已有节点消失;3)与已有节点关联的新边出现;4)非消失节点关联的边消失.

为便于处理这4种增量,本文引入了摇摆节点的概念统一从节点的角度入手处理这4种变化.引入摇摆节点之后,对4种增量引起的社区结构的调整就转变为摇摆节点所属社区结构的调整.

定义2.摇摆节点.社区归属可能发生改变的节点称为摇摆节点.

在进行增量社区划分时,必须先筛选摇摆节点.为此,引入了引力节点和动摇社区的概念.引力节点成对出现,试图将对方吸引到自己所在的社区.动摇社区结构可能保持不变,也可能发生变化.动摇社区可能发生分裂,由一个社区演变为多个社区;也可能发生社区融合,与其它社区部分或者全部融合.

定义3.引力节点.社区之间新增加的边所关联的已有节点即为引力节点.

1http：//www.sociopatterns.org/datasets/

定义4.动摇社区.文献[19]提出,如果一个度为1的节点在社区中消失,则该社区结构不变.除此之外,将存在消失边的社区称为动摇社区.

摇摆节点收集策略描述如下：

收集策略1.所有新出现的节点全部视为摇摆节点,加入摇摆节点列表.

收集策略2.将动摇社区中的全部节点视作摇摆节点,全部加入摇摆节点列表.

收集策略3.将引力节点视作摇摆节点,加入摇摆节点列表.

增量社区动态划分方法首先初始化社区结构,将每个摇摆节点视作独立社区,非摇摆节点则保持原社区;然后根据模块度优化算法对摇摆节点进行社区划分,具体过程如算法2所示.将上一步划分出的社区压缩成超节点,生成由超节点构成的社交网络图;最后,利用Louvain-INA算法对包含超节点的社交网络图进行社区结构调整,形成最终的社区划分结果.

算法2. Louvain-IMO算法

输入：Gt,Ns//根据CGt-1及Gt收集的摇摆节点列表Ns

输出：由超节点构成的社交网络图Gc

1.θ=0.001;

2.new_mod←Gt-1时刻的社区划分模块度,cur_mod←0

3.while(Ns!null and(new_mod-cur_mod≥θ))

4. cur_mod=new_mod;

5. for eachvinNs

6. 计算v加入各邻居社区后的模块度增量;

7. if 最大的模块度增量>0

8. 将v加入最大模块度增量对应的社区;

9. 将v不在Ns的邻居节点加入Ns;

10. else

11. 将v从Ns中删除;

12. end if

13. end for

14. new_mod←当前社区划分的模块度;

15.end while

16.将每个社区压缩为一个超节点,构建压缩图Gc;

17.returnGc

算法2展示了引入摇摆节点后利用模块度优化进行社区结构调整并生成由超节点构成的社交网络图的过程.在第8行中,当模块度增量最大的社区不止一个时,节点将随机选择一个社区加入.算法3展示了基于Louvain算法和标签传播算法构造的混合式动态社区发现算法.

算法3.基于Louvain的改进动态社区发现算法

输入：Gt-1,Gt,CGt-1

输出：CGt

1.计算演化程度β(t);

2.ifβ(t)≤0

3.Gc←Louvain-MO(Gt);

4. Louvain-INA(Gc);

5.else

6.Ns←根据CGt-1及Gt收集的摇摆节点列表Ns;

7.Gc←Louvain-IMO(Gt,Ns);

8. Louvain-INA(Gc);

5 实 验

本文采用实验的方法来评价本文方法.通过和Louvain-dyn算法、基于模块度的QCA算法[19]、DABP[20]及DCDID算法[21]比较在真实数据集和人工数据集上的执行结果来验证本文方法的正确性和有效性.

5.1 数据集

本次实验选择了来自不同场景的4个真实动态数据集和10个人工动态数据集.4个真实数据集分别是RM数据集[22]、安然邮件数据集Enron[23]、来自SocioPatterns1的CW数据集和PS数据集.10个人工数据集中有6个是根据动态LFR基准模型[24]生成,生成的参数分别为：混合参数mu取0.1到0.6的6个小数,节点数为1000,平均度为10,最大度为20,时间片网络数为20.另外4个人工数据集则来自Greene数据集[25].4个数据集的时间片网络数都为5,每个数据集的初始时间片网络包含1000个节点,节点的最大度为50,平均度为15;包含33个社区,社区内部的边数和总边数的比为10%.

记来自Greene数据集的4个数据集分别为Greene-1、Greene-2、Greene-3和Greene-4.Greene-1只包含出生和死亡事件,在每个时间片有10%的社区通过现存社区移除的节点创建,10%的社区被删除;Greene-2只包含合并和分裂事件,在每个时间片有10%的社区被拆分,10%的社区被两两合并;Greene-3只包含扩张和收缩事件,在每个时间片随机选择10%的社区扩张或收缩成它大小的25%;Greene-4包含间歇社区,在每个时间片有10%的社区消失,并在下一时间片重新出现.

5.2 实验环境及评价指标

实验中采用Qms值以及运行时间来评估算法的性能.Qms根据式(2)计算.在该式中,|s|表示时间片网络总数,Qi表示时间片网络i对应的社区划分的模块度Q值[26].Qms越高表示算法的效果越好.

(2)

实验中涉及的所有算法均用python语言实现,且在相同的windows10系统下执行.该系统采用Intel Core i5-7300 CPU,配置8GB的内存空间.

为避免随机性,所有的算法均在相应的数据集上独立运行100次,然后计算平均结果.

图3展示了算法在不同数据集上的Qms值对比.由图可知,在基于LFR生成的人工数据集上,本文算法在mu取不同值时所产生的每个数据集上得到的Qms值都是最高的,其次是Louvain-dyn算法和DABP算法.在Greene数据集上本文算法得到Qms值也明显高于其他对比算法,其次是QCA算法.Louvain-dyn算法和DCDIID算法则不相上下.在4个真实数据集上,本算法和Louvain-dyn算法的Qms值明显高于其它3个对比算法.其中,本算法的Qms值要明显高于Louvain-dyn算法的Qms值.

图4展示了算法在不同数据集上的运行时间.由图4(a)可知,在LFR数据集上在mu取0.1到0.5的5个不同值对应的子集上,本文算法的运行时间均少于Louvain-dyn算法.只有在mu=0.6时,本文算法的运行时间略长于Louvain-dyn算法.由图4(b)可知,在Greene数据集上本算法的运行时间明显少于其它算法.本文算法在数据集Greene-1、Greene-2、Greene-3和Greene-4的运行时间分别比Louvain-dyn算法和QCA算法降低了约76%和97%,比DCDID算法和DABP算法降低了约56%和98%.由图4(c)可知,本算法和Louvain-dyn算法在所有真实数据集上的运行时间要比其它对比算法少.虽然在CW、Enron和Rm数据集上本算法的运行时间比Louvain-dyn算法稍长,但是本算法在所有真实数据集上的Qms值却优于Louvain-dyn算法.

图3 算法在不同数据集上的Qms值对比Fig.3 Comparison of the Qmsvalue of the algorithm on different datasets

图4 算法在不同数据集上的运行时间(秒)对比Fig.4 Comparison of the running time(s)of the algorithm on different datasets

6 结束语

本文提出了一种混合的动态社区发现算法来应对增量式动态社区发现算法存在的误差累积和算法复杂度受网络增量影响的问题.对于产生增量较多的网络剧烈演化,该方法直接将对应的网络快照看做完整网络,采用静态方法划分社区.而对于产生增量较少的非剧烈演变,则采用增量式方法发现社区.在社区发现过程中,同时采用标签传播算法和基于模块度优化的Louvain算法,在利用Louvain算法性能优势的同时,利用标签传播算法弥补其在社区分辨率方面的不足.在未来工作中,将研究跨网络的社区发现.