节点度与邻域相似度标签传播算法.pdf

随着信息化的高速发展，研究复杂关系型数据统计性质的网络科学正在兴起.如果将一个网络视为由节点与边构成的拓扑图，某些子图出现内部连接密集，而在外部连接稀疏的情况，即“高内聚，低耦合”，则通常认为其存在较为紧密的聚类关系，进而将这些子图称为一个社区.社区发现是网络科学的重要研究方向，对探索网络的特性、揭示网络潜在规则和改善网络行为具有指导性作用.标签传播算法（label propagation algorithm,LPA）1作为社区发现中的主要算法应运而生，基于信息传播的思想，同时具备时间复杂度低、所需网络结构的先验信息少等优势，但同时也存在因为标签更新过程中随机度过高而导致的准确率不高、迭代结果不稳定的问题.针对上述问题，学者们提出了多种改进算法，一般思路是改变原算法中的随机传播策略，通过度量节点重要性进行传播顺序的优化.翟镇新等2提出LLPA算法，引入LeaderRank算法计算节点影响力，减少资源“逆流”；贾慧娟等3提出COPRA-S算法，计算节点连接社区强度，通过桥梁节点的设计，防止标签过度传播；Lu等4提出LPANNI算法，度量邻居节点影响力NNI作为定义标签更新顺序的依据.以上算法均未考虑邻域相似度对设计标签更新顺序规则的重要性.本研究受到LLS5度量指标的启发，提出一种基于节点度与节点邻域相似度的标签传播算法（local link similarity-label propagation algorithm,LLS-LPA），通过量化邻域网络中的重叠率与节点度值，生成新的节点标签更新规则，引入标签传播算法可解决随机性过高的问题.通过在不同数据集上的实验结果表明，LLS-LPA算法在一定程度上消除了随机传播策略对社区划分精度的影响，提升了网络中信息传播的有效率.1标签传播算法标签传播算法是基于图结构数据的半监督式学习算法，用于寻找网络中存在的社区，其基本思想是利用网络中的拓扑结构信息，采用信息传播的方式，不断在目标节点和邻居节点中传递标签信息，在完成一次传递后根据多数原则更新所有节点的标签，反复迭代，直至算法收敛得到社区划分结果.其更新节点度与邻域相似度标签传播算法林欣，吴玉芹，冯玮，范业仙*（宁德师范学院信息与机电工程学院，福建宁德352100）摘要：标签传播算法是一种典型的社区发现算法，针对其传播过程中存在由于随机性过高而导致的准确率不高、迭代结果不稳定等问题，提出基于节点度与邻域相似度的标签传播算法，对传播策略进行改进，引导算法进入良性的路径依赖中.在真实网络和人工网络中的实验结果表明，基于节点度与邻域相似度的标签传播算法在大规模网络社区发现方面不仅具有精度及稳定性的优势，而且提高了对网络混合参数的宽容度，具有一定的应用价值.关键词：标签传播算法；社区发现；节点度；邻域相似度；路径依赖中图分类号：TP391文献标识码：A文章编号：2095-2481（2023）03-0254-06收稿日期：2022-11-02*通信作者：范业仙(1980-),女,副教授.E-mail:基金项目：福建省自然科学基金项目(2020J01430)；福建省大学生创新创业训练计划项目(S202210398020)；宁德师范学院校级专项资助计划科研项目（2022ZX312）.第 35 卷第 3 期2023 年 9 月宁德师范学院学报(自然科学版)Journal of Ningde Normal University（Natural Science)Vol.35 No.3Sept.2023第3期林欣，等：节点度与邻域相似度标签传播算法操作为li=argmaxjN()i()lj,l.（1）式中：N()i表示节点i的所有邻居节点集合；li表示当前待更新节点的标签；lj表示节点i的邻居节点j的标签；()lj,l为克罗内克函数，若输入值相等，则输出0，否则输出1.在更新标签步骤中，有同步更新与异步更新两种方式.同步更新是指节点在t次迭代时的标签更新由其邻居节点当前时刻的标签决定，异步更新则指邻居节点t时刻的标签决定了节点在（t 1）次迭代时的标签更新情况.由于同步更新方式在使用中容易出现标签震荡不收敛而致使的多次划分结果不同的情况，故多数学者采用异步更新的方式.标签传播算法的时间复杂度为O()N，线性的时间复杂度使得其适合应用于大型网络的社区发现工作中.但在更新标签过程中使用的随机策略，可能会因为一个小的错误而触发“多米诺骨牌”效应，在投票更新标签时陷入错误的路径依赖，导致与真实网络的社区划分结果存在巨大出入，造成社区划分精度下降.2基于节点度与邻域相似度的标签传播算法2.1标签更新策略经典LPA算法对所有节点一视同仁，标签的更新次序完全随机，计算量小，因而在时间复杂度方面的表现极佳.可事实上，正如社会网络中意见领袖的作用一样，在信息传播过程中，“中心节点”的传播效益远高于一般“偏远节点”.通过引入LLS指标度量节点传播效益，优先从“中心节点”开始传播，能在更大程度上将信息传递至整个网络中，更加充分地利用网络信息，提升社区发现结果的准确度.此外，根据路径依赖模型，改变原算法中的随机更新策略还能引导算法通过正反馈进入良性循环，降低潜在的沉没成本，减少资源浪费.在更新次序规则的生成中，文中算法使用LLS指标作为排序依据，LLS指标结合Jaccard系数，以节点邻域相似度和节点度为主要研究对象，量化节点传播效益，具体计算公式分别为sim()b,c=|n()b n()c|n()b n()c|,如果节点b和节点c没有连边；1，如果节点b和节点c有连边.（2）LLS()i=b,cn()i(1 sim()b,c).（3）式中：n()i表示节点i的邻居节点；sim(b,c)0,1，随着sim值的增大，局部网络拓扑重叠率提升，节点与其邻居节点的相似度也越大，进而失去其在网络中独特作用，可替代性提升，结构重要性降低.节点的邻居节点数量越多，邻居间的拓扑相似度越低，即说明该节点的不可替代性愈强，传播效益愈高.2.2算法实现本研究提出的LLS-LPA算法首先根据LLS指标计算网络中各节点的度与邻域相似度，得到降序数组.在经典LPA算法的思路上将更新过程中随机排序的节点序列替换为上述数组，对图进行迭代传播计算，得到最后结果.改进算法LLS-LPA引入的LLS指标能够帮助原算法找到传播效益最高的节点优先开始传播，消除原算法中采用随机更新策略造成的影响，改变算法的路径依赖性，使其进入预期的良性循环，从而达到更优的划分结果.LLS-LPA算法具体描述见表1.-255宁德师范学院学报(自然科学版)2023年9月表1LLS-LPA算法输入：网络G=V,E，V表示节点集合，E表示边集合，最大迭代数T输出：网络的社区划分结果C=C1,C2,C3,Ck3实验结果与分析实验运行于CPU型号为AMD Ryzen 5 2500U、运行内存8 GB、Windows10、64位操作系统并安装有Python3.9 编程环境下集中式图计算工具NetworkX的PC机.对比算法包括选用同步更新标签LPA算法、异步更新标签ASYNC-LPA算法和LPANNI算法.由于标签传播算法具有一定的随机性，为保证样本数据对总体数据的代表性，根据中心极限定理的思想，将算法运行100次后取结果均值.3.1实验数据本研究分别在6个真实网络上进行实验，包括空手道俱乐部网络（Zachary Karate Club）、美式足球队网络（American Football）、蛋白质网络（Human Proteins(Stelzl)）、社交平台Facebook用户关系网络（Facebook(NIPS)）、美国电力网络（US Power Grid）和PGP算法用户交互网络（Pretty Good Privacy），均为无向无权图，具体信息见表2.表2真实网络数据集IDR1R2R3R4R5R6网络名称KarateFootballHuman proteins(Stelzl)Facebook(NIPS)PowerArenas-pgp节点数341151 7062 8884 94110 680边数786136 2072 9816 59424 316真实网络是现实网络的数学建模，除真实网络外，文中还使用了Lancichinetti等6提出的LFR基准网1.for eachvinVdo2.根据式(1)和式(2)计算节点度与邻域相似度3.end for4.对上步返回数组进行降序排序，得到有序数组5.初始化网络节点标签6.设置算法迭代次数t=17.whilet Toriteration_stop=True:8.for eachVtV9.for each inVt的邻居节点10.按照多数原则投票选出标签，当多个标签出现次数使用随机策略选取11.更新标签12.end for13.end for14.t=t+115.如果每个节点的标签收敛至某个值，算法结束16.end while17.return C-256第3期林欣，等：节点度与邻域相似度标签传播算法络.LFR是一种用于生成基准网络的算法，能够调整网络结构参数，由于其具有先验的社区结果，因而常用于比较不同社区发现算法的划分精度，具体参数设置见表3.表中：n表示创建图形中的节点数量；1表示图中度分布的幂指数；2表示图中社区规模分布的幂指数；dmin表示节点度的最小值；dmax表示节点度的最大值；Cmin表示最小社区数；Cmax表示最大社区数；表示网络混合系数，0,1，值越大则表示网络中的社区结构越模糊，反之则越清晰.表3人工网络参数设置IDN1N2n1 0002 00012321.51.5dmin510dmax1515Cmin2040Cmax50500.350.800.350.803.2评价指标3.2.1平均模块度模块度7是用于评价社区发现算法的经典指标，能够直观反映出社区的结构强度，其值越接近1，则认为社区划分算法的效果越好，计算公式为Qavg=12Ni,j V(Aijdidj2N)()li,lj（4）式中：N表示总边数；A表示网络中所指的邻接矩阵，若节点i和节点j有连边，则Aij=1，否则Aij=0；di与dj分别表示节点i和节点j的度；lj和lj表示节点i和节点j的标签，若li=lj，()li,lj=1，反之()li,lj=0.3.2.2模块度标准差模块度标准差是用于衡量算法迭代稳定性的指标，是一个期望值为0的随机变量，其值越小，代表算法结果越稳定，计算公式为Qstd=i=1t()Qi Qavg2t.（5）式中：t表示算法迭代次数；Qi表示时刻i的模块度.3.2.3标准化互信息和调整兰德系数标准化互信息（normalized mutual information,NMI）和调整兰德系数（adjusted rand index,ARI）是评价聚类精度的经典指标，在网络科学常用于已知社区划分结果的情况.NMI0,1，若划分结果越接近原始结果，则NMI值越大，反之越小.ARI则用于测量在社区划分相同的情况下，社区内节点相同的概率.一个总节点为n的网络G，A=a1,a2,ak表示先验社区划分结果，B=b1,b2,bk表示算法划分结果.NMI和ARI的计算公式分别为NMI=2ijnijlg(nijnbidj)ibilg()binjbjlg()bjn；（6）ARI=ij(nij2)-i(ai2)j(aj2)/(n2)12 i(ai2)+j(aj2)-i(ai2)j(aj2)/(n2).（7）3.3实验过程与结果分析3.3.1真实网络实验大多数真实网络社区划分的结果是未知的，无法使用精度指标评价，故实验采用模块度指数衡量算法性能.4种算法在6个真实网络中的具体表现见表4.Qavg表示模块度平均值，Qstd表示模块度标准差，N表示平均划分社区数量.对照表2可知，在网络规模较小，即先验信息不足的情况下（如R1），随机选择策略使得经典标签传播算法在模块度的平均值和标准差上的指标更好；但随着网络规模的扩大，可以发现LLS-LPA算法的平均模块度较其他算法具有5%25%的提升，方差趋于稳定，且由于LLS-LPA算法度-257宁德师范学院学报(自然科学版)2023年9月量了节点度与邻域相似度，改变了原算法的传播策略，从传播效益高的节点开始传播，网络总体信息流通性加强，故可见在模块度提升的前提下，LLS-LPA还可以划分出更高精度的社区.表4真实网络指标结果IDR1R2R3R4R5R6LPAQavg0.354 70.583 10.412 80.764 10.627 80.738 1Qs000000N3.011.0289.09.01 308.02 059.0ASYNC-LPAQavg0.355 70.585 80.458 50.794 80.594 60.730 6Qstd0.006 50.000 20.000 20.000 00.000 00.000 0N3.411.2292.310.01 435.51 964.9LPANNIQavg0.399 10.601 10.447 40.795 00.615 00.662 0Qs000000N3.011.0293.010.01 344.02 254.0LLS-LPAQavg0.246 40.589 60.484 40.795 20.740 90.803 0Qstd0.007 40.000 20.001 00.000 10.000 00.000 2N2.410.5169.79.6704.4921.03.3.2人工网络实验4种算法在人工网络N1中的表现如图1，其中横轴为网络混合系数，在自变量两端即)0,0.35(0.8,1的范围内，网络特征处于极度明显或模糊状态，缺乏对比度，故不予列出.当值为0.350.50，各算法识别社区的准确度有了显著的提升，就平均而言，LLS-LPA算法的表现最佳，LPANNI算法居其次，同步更新和异步更新的LPA算法最弱.当值为0.350.80时，网络间各节点的联系趋于分散，难以形成社区结构，故各算法表现都不佳，但如图1（a）所示，LLS-LPA算法存在NMI值，在较为极端的条件下仍然能正确发现部分社区，相较于其他算法具有优越性.a)NMIARIb)a)NMI指标b)ARI指标图1不同算法在N1网络上的精度实验N2网络相较于N1网络大幅提升了网络规模，将服从幂律分布的网络人为地提升复杂度，减少有效信息，在这样的网络上进行精度实验，社区发现工作的难度在一定程度上提升.不同算法在N2网络上的精度实验如图2.算法整体精度降低，更加难以划分出正确的社区，但改进算法LLS-LPA由于计算了每一个节点在网络上的重要程度，有效地考虑了网络的拓扑信息，精确利用了网络节点信息，更加适用于大型网络，因而在划分精度上仍优于其他算法.a)NMIARIb)a)NMI指标b)ARI指标图2不同算法在N2网络上的精度实验-258第3期林欣，等：节点度与邻域相似度标签传播算法4结语本研究提出基于节点度与邻域相似度的标签传播算法LLS-LPA，通过量化指标LLS对网络中的节点进行排序，采用传播效益最大化策略，使信息在网络中按照传播效益降序传播.实验结果表明，改进算法解决了原始算法中采用随机策略带来的一系列问题，与LPA、ASYNC-LPA和LPANNI算法相比，本算法准确度、效率更高.但仍存在一些不足：1)节点信息计算的时间复杂度高，算法运行时间较长，采样不够充分，未来可以尝试使用分布式图计算框架如MapReduce、Spark等提升实验效率；2)只在无向无权图上进行了验证，而节点自身信息（如喜好、立场等）和边指向信息也具有挖掘价值，今后将上述信息应用于社区发现算法.参考文献：1 RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks J.Physical Review E,2007,76(3):361062 翟镇新,於跃成,谷雨.融合LeaderRank和标签传播的社区发现算法 J.计算机与数字工程,2021,49(5):942-946.3 贾慧娟,刘园,史爱静,等.一种基于标签传播的重叠社区发现算法 J.小型微型计算机系统,2022,3(4):6.4 LU M,ZHANG Z,QU Z,et al.LPANNI:Overlapping community detection using label propagation in large-scale complex networksJ.IEEE Transactions on Knowledge and Data Engineering,2018,31(9):1736-1749.5 阮逸润,老松杨,王竣德,等.基于领域相似度的复杂网络节点重要度评估算法 J.物理学报,2017,66(3):9.6 LANCICHINETTI A,FORTUNATO S.Community detection algorithms:A comparative analysis J.Physical Review E,2009,80(5):56117.7 NEWMAN M E.Modularity and community structure in networks J.Proceedings of the National Academy of Sciences,2006,103(23):8577-8582.Label propagation algorithm based on the node degree andneighborhood similarityLIN Xin,WU Yu-qin,FENG Wei,FAN Ye-xian*(College of Information and Mechanical&Electrical Engineering,Ningde Normal University,Ningde,Fujian 352100,China)Abstract：The label propagation algorithm is a typical community detection algorithm.To address the problems of low accuracy and unstable iteration results due to high randomness in its propagation process,the LLS-LPA algorithm based on node degree and neighborhood similarity is proposed to improve the propagation strategy and guide the algorithm into benign path dependence.Experimental results in real networks and artificialnetworks show that the LLS-LPA algorithm not only has the advantages of accuracy and stability in large-scalenetwork community detection,but also improves the tolerance of network hybrid parameters.Key words：label propagation algorithm;community detection;node degree;neighborhood similarity;path dependency责任编辑郭涓-259