基于节点相似性的加权复杂网络BGLL社团检测方法①

贾郑磊,谷 林,高智勇,谢军太

1(西安工程大学 计算机科学学院,西安 710048)

2(西安交通大学 中国西部质量科学与技术研究院,西安 710049)

现实世界中许多系统都可以用复杂网络表示,社团结构是复杂网络的重要特征之一,研究社团结构能够帮助了解网络的内部结构及特性,评估和预测网络的功能.目前研究者们提出的社团检测算法大多面向无权网络,主要分为全局算法[1-10]和局部算法[11-15],而对于加权网络中社团结构检测的研究还相对较少.全局算法能够较均衡地利用各节点间信息,但是一般时间复杂度较高,只能实现局部收敛;局部算法一般具有较低的时间复杂度,但是检测结果容易受到起始点及随机传播过程的影响.同时,在许多现实复杂网络系统中,节点往往具有多个属性,使得节点可能属于多个社团,这种重叠现象使得能够充分利用全局和局部信息的重叠社团检测方法具有更大的实用价值.

目前,已有的全局算法和局部算法均各有优缺点.

基于全局信息的模块度优化社团检测算法最早是文献[1,2]提出的基于边介数的GN分裂算法以及衡量指标模块度,但是算法的时间复杂度较高;文献[4]提出贪婪最大化模块度的FN凝聚算法,在一定程度上降低了算法的时间复杂度;文献[6]提出了基于模块度增益的层次性贪婪BGLL算法,该算法在稀疏网络上的时间复杂度是线性的,适用于大型网络,是目前最优的模块度优化算法.但传统方法无法直接实现重叠社团的准确检测,易受节点顺序影响,存在分辨率限制[10]以及缺乏重叠结构检测手段.

基于局部信息重叠社团检测经典算法是文献[11]提出的LFM算法,但是该方法基于随机种子节点,划分结果质量取决于种子节点.文献[12]提出基于说话者—听话者动态交互模式的改进的标签传播算法(SLPA),该方法能够同时发现重叠结点和重叠社团,但是算法结果并不稳定.

目前仍缺乏能够兼顾重叠与层次、时间复杂度与计算准确度的稳定性高的方法.

本文针对加权复杂网络中的重叠社团检测问题,首先利用节点重要度重构网络,然后运用加权BGLL算法,以模块密度增益作为迭代终止条件,最后结合加权节点与社团相似度实现重叠社团检测,并与传统BGLL算法和目前性能较好的SLPA算法进行准确率分析对比,探讨本文所提方法的优势.

1 BGLL加权网络重叠社团检测及其改进

1.1 改进的BGLL社团检测算法

BGLL算法在稀疏网络上具有时间复杂度线性的优势,算法结果稳定,社团检测结果较准确,计算简单且易于实现,使该算法具有较大的应用空间和较高的应用价值.

本文在BGLL算法的基础上进行了改进,针对节点顺序敏感问题以及分辨率限制提出了加权节点重要度计算方法和升序排序策略并增加模块密度作为算法终止条件,在充分利用全局和局部信息的同时,提高了算法的运算准确度和寻优排序速度.

设节点i的度为d(i),权值为w(i),聚集系数为c(i),加权节点重要度为I(i)w,计算方法如下:

α在0到1之间,实验发现当α为0.5时能较好的兼顾节点权重和网络聚集程度,故α取值为0.5.

对于加权网络,模块度增益采用增强模块度增益[6],设m为网络中所有边的权重和,ki为节点i上所有边的权重和,ki,in为节点i到某社团中所有节点的边的权重和,∑in为某社团内部节点间连边的权重和,∑tot为某社团中节点与网络中所有节点连边的权重和,ΔQw为模块度增益,计算方法如下:

对于加权网络,模块密度采用通用模块密度[14],设k为社团个数,V为社团i内节点个数,diin为社团i内节点连边的权重和,diout为社团i内点与社团i外节点的边的权重和,D为模块密度,计算方法如下:

参数λ在0～1之间,调节λ可以分析复杂网络的拓扑结构和层次结构: 若λ为0.5则表示D为模块密度,若λ为0则表示D为比率割集,若λ为1则表示D为比率关联.本文使用模块密度,因此采用λ为0.5.

1.2 改进的Jaccard相似度

为了充分利用全局和局部信息,采用局部相似性度量Jaccard系数来衡量节点间的相似度.针对重叠社团检测问题,提出了加权节点间相似度计算方法以及加权节点与社团相似度计算方法.

节点间的加权相似度在无权Jaccard节点间相似度[15]的基础上考虑了节点间相关权重,设节点i的邻居集合为nbs(i),节点j的邻居集合为nbs(j),wih,wjh为两节点与两节点公共邻居节点h的边权,节点i和节点j的无权Jaccard节点间相似度为J(i,j),节点i和节点j的加权Jaccard节点间相似度为Jw(i,j),计算方法如下:

设节点i为网络中节点,节点j属于社团C,节点i与社团C间的加权Jaccard相似度为Jw(i,C),计算方法如下:

1.3 重叠结构判断

用于判断网络中的节点与社团是否存在重叠结构,实现方式如下: 将改进的BGLL社团检测算法运算得到的社团检测结果进行网络中各节点与各社团加权Jaccard相似度计算,根据计算结果的值判断是否检测到重叠结构.如果对以上运算的结果直接进行重叠结构判断,设γ是网络内各节点与各社团加权Jaccard相似度计算结果,节点i为网络内任意节点,Cj,Ck是改进的BGLL社团检测算法检测结果中的社团,γ的计算如下:

然后用γ和给定的阈值r比较,有两种情况:

如果γ小于等于给定的阈值r,表示检测到重叠点,就把当前节点保存到对应的社团中.如果γ的值大于r,则表示没有检测到重叠结构.实验发现,当节点或连接关系较多时,为了在较大层次上检测到重叠社团且在一定程度上避免过重叠,r取0.1结果较好,故采用r=0.1.

2 DBGLLJ加权重叠社团检测算法

为了在加权复杂网络中检测出重叠社团,详细的DBGLLJ算法设计如算法1.

算法1.DBGLLJ加权重叠社团检测算法(1)社团初始化: 把每个节点单独作为一个社团;(2)节点预处理: 根据节点重要度对节点排序;(3)第一阶段:1)根据节点重要度序列遍历各节点;2)遍历当前节点的邻居节点序列;3)计算各邻居节点加入当前节点所在社团前后的模块度增益,选取邻居节点中模块度增益最大值并记录对应邻居节点;4)若最大模块度增益大于0,则进行社团合并,从原社团中删除该邻

居结点,进行步骤(3)的2);若最大模块度增益不大于0,则从步骤(3)的1)遍历下一节点;若节点序列遍历完,则进入第二阶段;(4)第二阶段:1)计算上一次迭代社团检测结果的模块密度;2)把上次迭代检测出的社团作为节点从步骤(1)到步骤(3)重新开始迭代;3)计算迭代后的模块密度,如果迭代前后的模块密度增益大于0,则继续进行步骤(4);如果模块密度增益不大于0,则结束迭代,执行步骤(5);(5)重叠结构检测:1)根据改进的Jaccard相似度计算原始网络节点间相似度;2)在检测结果的基础上,根据节点间加权Jaccard相似度计算各节点与迭代后各社团的加权Jaccard相似度;3)根据预设的重叠点检测阈值得到重叠检测结果;(6)算法结束.

上述算法既可以检测非重叠社团,还可以判断是否检测重叠结构,如果判断为检测到重叠结构,就把当前加权重叠社团检测结果保存并展示出来,如果仅仅检测非重叠社团,则可简化该算法,省略第(5)步.

3 实验分析

实验分别以LFR基准网络、真实网络为测试数据集验证本文所提DBGLLJ方法的有效性,设置与传统BGLL算法以及较好的SLPA算法的对比实验;并在现实复杂机电系统因效性网络进行了应用.

3.1 评价指标

采用改进的标准化互信息NMI[16]来衡量和比较基于LFR基准网络的重叠社团算法的精度,NMI越大说明算法精度越高;采用扩展模块度Qov[17]衡量和比较真实网络中重叠社团算法的准确度,Qov越大说明算法准确度越高,实验发现p为30时指标使用效果较好,反应灵敏且计算效率较好,在此p取30.

3.2 LFR基准网络实验

经典的LFR基准网络[11]参数意义见表1.

表1 参数意义

LFR网络参数设置如下: 网络规模N为1000;平均节点度k为20,最大节点度maxk为50;节点度和社团规模幂律分布参数分别为t1=2,t2=1.设置两组不同的社团规模参数以生成两种网络: 较小规模网络的minc=10,maxc=50;较大规模网络的minc=20,maxc=100.混合参数u从0变化到0.7,间隔为0.1,测试不同混合程度下算法的社团检测效果.

对于重叠网络,设置om=5,节点数为1000的网络中设置重叠节点数on从0到500变化,间隔为50,测试不同重叠程度下的社团检测效果.

当进行社团检测时,自动把当前社团检测结果保存到文件中,图1是分别在较小规模非重叠网络、较大规模非重叠网络以及较小规模重叠网络上的对比算法的评估指标NMI的结果,从图1可以看出,对于非重叠社团检测而言,所提的DBGLLJ方法克服了传统BGLL算法倾向发现较大规模社团的弊端,且在混合度小于等于0.6时具有最高的检测准确度;而对于重叠社团检测而言,所提算法的准确度也均优于其他两个对比算法.

图1 LFR基准网络社团检测效果对比

3.3 真实网络检测实验

采用了美国空手道网络Zachary[1]、海豚社交关系网络Dolphins[18]、美国大学生足球比赛网络Football[1]以及加权Zachary网络[19].各网络的节点规模n、边数目m、度平均k、原社团个数v、对比算法检测后对应社团个数v’以及评估指标Qov结果如表2.

表2说明在真实网络中,所提的DBGLLJ算法均具有较高的Qov,且社团检测结果在社团规模较小时具有更高的准确性.

3.4 现实复杂机电系统因效性网络应用实验

为真实准确可靠评估复杂机电系统服役质量状态,研究复杂机电系统内部结构,有必要对系统内各变量因效性网络进行社团结构检测.网络的节点表示现实系统各物理部件的关键指标,网络的边表示指标间的关联强度.网络的初步构建结果为自环全连接因效性网络,但在现实世界中,复杂网络多为稀疏网络,即＜＜N-1,也常有的特点,网络的关联强度Wr、度平均k以及聚集系数C如表3,由表知Wr=0.5时网络的聚集效果较好,因此去掉了网络的自环并截取了Wr>0.5的关联强度边进行社团检测.

最终的机电系统网络包括157个节点和782条边.将DBGLLJ算法应用于实际的复杂机电系统网络,模块度Q[2]、扩展模块度Qov、社团检测个数v以及重叠点个数o具体结果见表4.

从表4可知,该检测结果模块度较高(在0.3-0.7之间较好),重叠模块度为0.927,重叠比例为7.9%,在此范围内该算法重叠检测效果较好,结果可信.检测结果展示如图2.

以图2所示的较大社团10为例,将社团内各节点及其对应变量(表5)与实际复杂机电系统对比分析,发现该算法的检测结果较符合系统内部结构关系,与实际情况下的系统的强弱社团情况接近,检测结果较好,且重叠点具有较高的参考价值,能够为进一步进行网络评估和预测提供较准确的数据支持.

4 总结

目前,对于加权复杂网络重叠社团检测的算法还较少,且检测效果和算法稳定性欠佳,如何充分利用全局和局部信息进行准确的重叠社团检测具有重要意义.传统的BGLL算法具有稀疏网络时间复杂度线性、较大规模非重叠社团检测准确度较高的优势,但是对节点顺序敏感、存在分辨率限制、缺乏重叠检测手段,无法实现加权复杂网络的重叠社团的准确检测.

表2 真实网络检测结果Qov对比

表3 复杂机电系统网络系数

表4 现实复杂机电系统网络DBGLLJ算法结果

图2 现实复杂机电系统重叠网络检测整体结果图

表5 现实复杂机电系统社团10

为了实现加权复杂网络重叠社团的准确检测,本文提出的DBGLLJ算法利用了传统BGLL算法未能充分利用的局部信息和全局信息,针对节点顺序敏感问题提出加权节点重要度计算方法和升序排列策略,提高了寻优排序效率和检测准确性;针对分辨率限制问题增加模块密度作为迭代终止条件,改善了分辨率问题;针对重叠社团检测提出运用改进的Jaccard相似度衡量原始网络各节点与改进的BGLL算法社团检测结果中各社团的相似性,并根据阈值检测得到了重叠结构.实验表明,所提的DBGLLJ算法的社团检测精度得到提高,能够检测出重叠结构,且重叠社团检测结果较优.将该算法应用于实际复杂机电系统进行分析,结果较满意.