融合节点重要性与影响力的重叠社团检测算法.pdf

以重叠社团检测算法 COPRA作为基础,给出了一个结合节点重要性与节点影响力的重叠社团检测算法COPRANNI.首先，使用一种在三角形构成基础上的节点重要性,以此确定节点更新顺序其次，使用Node2vec模型遍历网络生成节点序列,在此基础上利用Skip-gram 模型获得节点的低维向量,然后通过余弦相似度量标准获取相似值将该相似性和重要性融合确定的节点影响力引入到隶属系数中,进行标签传播，待稳定收敛后，最终发现重叠社团通过在多个数据集上进行实验，结果表明：该论文提出的算法在重叠社团EQ质量指标上有较好表现.关键词：三角形构成；社团检测；标签选择；综合影响力中图分类号：TP393文献标识码：A文章编号：2 0 9 5-2 2 9 5(2 0 2 3)0 2-0 134-0 5D0I:10.16559/ki.2095-2295.2023.02.007An overlapping association detection algorithm incorporatingthe importance and influence of nodesLIU Runjia,ZHAO Yuhong,YAO Yue?(1.Information Engineering School,Inner Mongolia University of Science and Technology,Baotou 014010,China;2.Department ofSecurity Engineering,Beijing Vocational College of Labour and Social Security,Beijing 100029,China)Abstract:Inspired by algorithm COPRA,an overlapping community detection algorithm COPRANNI,which combines the importanceand influence of nodes,is proposed.Firstly,according to a node importance method based on triangle composition,the node updateorder is determined.Secondly,the Node2vec model traverses the network to generate node sequences.On this basis,the Skip-grammodel is used to obtain the low-dimensional vector of nodes,and the similarity values are calculated by the cosine similarity measurecriterion.Finally,the node influence defined by the fusion of this similarity and importance is introduced into the affiliation coefficient.During label propagation,the overlapping associations are eventually found when the associations convergence stably.The results of theexperiment on multiple datasets indict that our algorithm performs well on the overlapping association EQ quality metricsKey words:triangle composition;association testing;label selection;comprehensive impactWeb的巨大发展导致了不同网络结构的诞生，尤其是随着网络的不断演进，其网络结构已经演变成一个庞大的复杂网络复杂网络在医药1、交通、谣言控制等领域都得到较广泛的应用和研究，同时复杂网络在物理、数学以及生物2 这些基础性学科上也有了很大的突破当一些网络其结构和属性存在不同时，这些不同的结构和属性也会体现出网络特征的多样性，在一个复杂网络中，节点或顶点代*天基金项目：内蒙古自治区自然科学基金资助项目（2 0 2 0 MS06009).作者简介：刘润佳（19 9 8），女，内蒙古科技大学硕士研究生，研究方向数据挖掘、社区发现.通信作者：e-mail：z h a o y u h o n g 35 16 3.c o m收稿日期：2 0 2 2-0 4-12135刘润佳，等：融合节点重要性与影响力的重叠社团检测算法表对象，链接或边代表对象之间的交互3 网络的拓扑属性和社团结构，对于理解现实世界系统的功能和组织至关重要其中社团结构表达的是网络中节点的聚合群体特性即一组彼此紧密连接但与网络的其余部分分离良好的节点4 社团检测促进了研究者对复杂网络社团结构的研究。如今，复杂网络中的重叠网络同样也是很多研究者关注的重点，对于重叠社团的研究也有很多。GREGORY5提出了针对重叠社团的标签传播算法COPRA,该算法在传播路径和传播影响力2 方面均存在随机性的问题，且在传递过程中一次会传递多个标签，为防止每个节点接收到过多标签进行参数设定，但是在大规模复杂的网络中预设参数很难实现.XIE等人受参数限制的启发提出SLPA算法6 进行重叠社团检测，其在传播过程中，一次只传递一个标签，且社团个数对该算法没有限制，但同样存在标签传递随机性的问题在SLPA基础上，张静宜提出了DSLPA7，解决了标签传播随机性的问题，同时提出MSLPA，该算法让SLPA与模块度进行结合郭峰等8 人在DOCNet算法基础上提出了一种新颖的重叠社团检测算法DOCLLE，该算法分别在初始节点的选择以及标签对应社团的系数计算方法上进行了改进和优化，但忽略了网络结构的稀疏性.赵宇红等9 人在社团检测的节点相似方面提出了新的相似性度量标准，该相似性在节点和元路径2方面使用注意力机制进行计算，提高了社团检测的准确性，但没有考虑节点的个体信息。不同研究者针对标签传播的随机性进行改进，但均没有在标签传播中充分考虑节点的属性信息及节点间关联影响，复杂网络的重叠社团检测仍然是一个开放性问题本文在COPRA算法基础上进行了改进和优化，针对该重叠社团检测算法中初始节点选取和标签传递随机性的问题，给出了一个新颖的社团检测方法通过对节点重要性的量化解决标签传播过程中选择初始节点的随机性，利用节点影响力的度量改善标签传播过程中选取邻居节点标签的随机性，以挖掘更加稳定的重叠社区。1相关知识1.1COPRA算法COPRA算法中引人隶属系数来衡量节点x对社区c的归属程度，隶属系数的计算公式如式（1）所示：bt-1(c,y)b,(c,)：YEN(x)(1)I N(x)I式中：N(）为节点的周围邻居节点所组成的集合；b,（c,x）为轮更新时节点在社区c的归属程度.算法描述如下：a）首先，给网络中任意一个节点x，设置为（cs，1）.b）利用式(1）更新节点的隶属系数b（c).淘汰隶属系数小于1/v的标签，如果这些值均小于1/v,则留下值最大的标签如果标签有多个，随机选择一个之后归一化。c)随着节点对应的社区标签稳定时，认为该算法已经达到收敛；否则将继续进行步骤b).1.2网络嵌入模型网络嵌人将网络的结构或内容用低维的向量来表示，将原有的高维离散特征用低维的连续特征表示，因为低维的向量在机器学习领域有较广泛的使用价值，所以网络嵌人模型被有效的运用到社团检测领域.DeepWalk是最早被用于网络中社团检测领域的嵌人模型，它的主要思想是利用自然语言处理中的Skip-gram模型来获取网络中节点的特征向量.Node2vec模型10 在其模型基础上,对节点走向的方式进行了改进，通过广度遍历和深度遍历生成随机游走序列,能够更好地反映网络结构.Line算法1定义了2 种节点之间的相似性，通过提出目标函数对节点特征进行优化：以上均是针对网络拓扑结构的网络表示学习，对属性的学习有所欠缺随着各种各样的网络出现，网络中节点的属性对于社团划分也极其重要。TriDNR12的方法宗旨是利用结构、属性以及标签信息来进行属性网络的表示学习，该算法融合了DeepWalk以及Doc2vec嵌人节点、文本和标签信息的思想文献13 提出了一个可扩展的特征分解解决方案来推导出嵌入向量，并在任意阶数的近似性之间进行转移文献14 提出了一种新的策略来保证学习的节点表示能够编码来自拓扑结构和节点属性的一致和互补的信息，本文将网络嵌入与标签传播进行了结合，使用Node2vec模型与Skip-gram模型做嵌人，为节点相似性的度量奠定了基础.1362023年6 月第42 卷第2 期内蒙古科技大学学报2算法设计2.1节点重要性和影响力度量1)节点重要性在复杂网络领域中，挖掘节点一般分为单个节点的挖掘以及节点组的挖掘，重要节点的挖掘方法也有很多种在复杂网络中如果一个节点在网络中属于影响力较大的节点,往往会存在一些特征：一种情况是，当网络中的节点与其他节点存在较多连边时，通常会判定这种节点的度会较大；另一种情况是，当网络中的节点与其周围节点交互较多时，往往这类节点同邻居节点所构成的三角形数量也会更多。所以可解释为，网络中的节点存在较大的度，且包含该类节点的三角形个数较多时，往往这类节点有较大可能性属于社区中影响力较大的节点。在以上假设的基础上，提出重要度概念来量化重要性，其是依赖于三角形构成，如式(2）：(eu+ku)-min(e;+k,)11NI(u):十22max(e,+k,)-min(e;-k,)jeVE(2)式中：eu为包含节点u在内的三角形总个数，ku为节点u的度.该算法中当计算完节点u的eu+ku,同时为了使NI(u）取值在0.5 1之间,对该式子进行归一化.2）节点相似性度量节点相似性的概念体现的是节点间联系的相关性，而这种相关性也是对节点影响力的一种体现，本文算法对于节点相似性的量化是通过节点嵌人学习而获得的首先，基于Node2vec模型遍历得到序列;然后，通过Skip-gram学习目标序列获取网络中每个节点的低维向量；最后，获得节点间的相似值是利用了余弦相似指标，相似值的获得可以应用到节点影响力当中.Node2vec模型中给出一个控制游走方向的算法，固定其随机游走的步长为，使用如式（3）分布产生邻居序列：TTuxif(v,x)=E.(3)P(c;=ci-1=v)ZLootherwise在式（3）中：归一化因子用Z来表示，节点v到节点x的转移概率用T来表示。在该模型中的控制随机的游走的方向是通过规定的2 个参数p和q,转移概率公式为T=p.，（t,x)gQu，p.g（t,x）,为带偏置的搜索算子,其公式如式(4)所示:rl/p,dux=0g(t,x)=q,du=1:(4)l1/q,d=2式中：d为从节点t到节点x这个路径距离上的最小值，当d=0,即返v节点本身时为1/p;dw=1即节点t与节点x直接相连时为1；当dw=2即节点t与节点不直接相连为1/q.Node2vec有偏随机游走过程如图1所示：X=1=1/glV=1/q=1/p图1预估走向邻居节点示意图通过以上Node2vec模型生成了网络中的节点序列，然后利用Skip-gram模型训练目标序列获取到节点的向量，此低维向量奠定了相似性的计算基础.下面简要阐述Skip-gram模型的结构特点.Skip-gram首先是在自然语言领域提出的模型，是用一个单词来预测句子该模型也应用到了社团检测领域，模型优化的目标函数如式（5）所示：L=Z log(Context(w)I w).(5)式中：Context（w）可解释为文本中词的上下文，w可解释为当前词，c可解释为语料库，如图2 展示了Skip-gram的模型.inputprojectionoutputW(t-2)W2WW(t-1)2W(t)W2w(t+1)WW(t+2)图2Skip-gram模型框架结构在图2 可以看出，Skip-gram模型由图中所示的3部分组成，从左向右依次是输人层、隐含层和输出137刘润佳，等：融合点重要性与影响力的重叠社团检测算法层，Wi,W分别为之间的权重矩阵该模型的方法可理解为在自然语言中的句子或者文本中，使用其中任何一个单词用其向量表示，使这个向量能够最大可能性预判其周围的单词，当式（6)取得最优值时，此时隐含层的矩阵即为网络中节点的最优和最终特征向量表示：T1(6)Tt=1-C获取到网络中的节点向量之后，用余弦相似度计算节点间的相似性，如式（7）所示：Scosine-101,02n2(v2)21(7)3）节点影响力计算结合节点重要性与节点间相似性度量量化邻居节点的综合影响力，进一步应用在隶属系数计算中使得节点标签的更新更为合理.邻居节点v对节点u的影响力定义如式（8）所示：sim(v,u)NI,(u)=NI(8)max,sim(h,u):heNg(u)式中：NI（u）为节点u的周围邻居节点集合.2.2融合重要性与影响力的算法实现算法的具体步骤如下所述：1）节点重要性和影响力计算首先，设置网络中每个节点主标签以及隶属系数为1.计算每个节点重要性，然后升序排列得到序列S,使用Node2vec模型获得序列，将序列作为嵌人模型的输人，生成节点向量之后，通过相似度计算标准如式（7），来获取节点间的相似性值利用式（8）获得网络拓扑结构中每个节点与其周围节点的综合影响力值：2)标签传播a)首先，节点收到邻居节点传递给它的主标签组成集合，如式（9)所示：ESn=(es(ci,b1),es(c2,b2),*,es(c,b,)/.(9)b）将节点的影响力引人到隶属系数计算中，利用式（10）计算节点u对于社区c的所属程度：e(c,u)=e(c,v)NNI,(u)es(cv,b,)eESN,voN(u),cy=c(10)e(c,v)NNI,(u)es(cv,bv)eESN,voN(u)更新完隶属系数得到新的标签集合ESn，同时删除满足e（c,u）1/I ES%l 的标签,剩余的标签形成集合ESN.c）利用式(11）归一化生成新的标签集合ESs，该集合中隶属系数最大的标签作为主标签L.e(c,u)e(c,u),Ze(c,u)=1.es(c,e)eESNe(c,u)(11)3实验结果与分析3.1实验评价标准SHEN等人提出了针对重叠社团检测结果的衡量标准，所以本文采用扩展模块度（EQ）【15】来评估本文算法社团检测质量的好坏如式（12）所示：EQ=12mQ.Q,le,4,-.2ml(12)LEyjeC在式（12）中：可解释为社团中边的总数,k;,k；为节点Vi,的度，Q;，Q,为这2 个节点对应的社团数量，A，为对应网络的节点组成的邻接矩阵，该指标所取的数据在0 到1之间，该值越接近于1，说明社团检测质量更好，3.2实验数据集实验使用了4个不同规模的网络数据集，分别是CA-GrQc科学合作网络数据集、PGP优良协议网络数据集、condmat论文作者协作网络数据集以及cit-hepph引文网络数据集在表1中展示了数据集包含的节点和边的个数，数据集的具体信息如表1所示：表1真实网络数据集数据集节点边CA-GrQc524214496PCP1068024316condmat23 13393 497cit-hepph34546421.5783.3社区发现结果验证为了验证算法社团检测的有效性，本文算法将COPRA算法以及LPANNI算法作为对比实验，重叠社团检测结果用EQ指标进行评价.COPRA算法运行10 次取平均EQ值，LPANNI算法及本文算法是稳定的社团检测算法，所以这2 个算法是取运行一（责任编辑：师宝萍）1382023年6 月第42 卷第2 期内蒙古科技大学学报次的EQ值实验结果如表2 所示：表2社区发现EQ值比较数据集COPRALPANNICOPRANNICA-GrQc0.463 40.70220.713 9PCP0.57420.686 90.699 1condmat0.54130.505 60.5100cit-hepph0.513 60.566 50.5784表2 展示了各算法在4个网络数据集上的EQ值，重叠模块度EQ的取值越高说明在社团检测过程中准确度越好.COPRANNI算法划分的重叠社团模块化度量值EQ在PGP网络数据集上比LPANNI算法EQ提高了1.7 8%，在CA-GrQc数据集上比LPANNI算法提高了1.6 7%，在condmat数据集上本文算法的EQ值略低于2 个对比算法，在cit-hep-ph数据集上比较好的LPANNI算法提高了2.1%.综上，提出的算法在不同数据集上，都展示出了较好的优势。4结论在传统的重叠社团标签传播算法基础上，针对重叠社团检测提出了融合节点重要性以及综合影响力的算法首先，使用一种基于三角形计算的节点重要性确定节点的更新顺序；其次，综合影响力是结合了节点重要性和节点相似性进行量化；最后，将节点影响力引人到隶属系数的计算中进行标签传播，生成重叠社团通过在不同数据集上进行实验表明了提出的算法在重叠社团检测方面具有良好的性能。在今后将进一步优化算法，引人到有向加权网络中以及动态重叠网络中，满足如今更多的复杂网络结构需要，参考文献：1姚瑶，孙粼希，谢雁鸣，等.真实世界中连花清瘟胶囊（颗粒）治疗下呼吸道感染常见用药方案复杂网络分析J.中医杂志,2 0 2 1,6 2(0 8）：6 6 2.2肖继海，崔晓红,陈俊杰.节点属性和拓扑信息相结合的脑网络聚类模型J.计算机工程与科学,2 0 2 0,42(11):2088.3ZHANG Y,LEVINA E,ZHU J.Community detection innetworks with node features J.Electronic Journal ofStatistics,2016,10(2):3153.4LI X,GAO C,WANG S,et al.A new nature-inspiredoptimization for community discovery in complex networksJ.The European Physical Journal B,2021,94(7):1.5GREGORY S.An algorithm to find overlapping communi-ty structure in networks CJ/European conference onprinciples of data mining and knowledge discovery.Ber-lin,Heidelberg Springer:2007:91.6XIE J,SZYMANSKI B K,LIU X.Slpa:Uncovering o-verlapping communities in social networks via a speaker-listener interaction dynamic process CJ/2011 IEEE11th international conference on data mining workshops.Vancouver,British Columbia,Canada:IEEE,201l:344.7张静宜.基于SLPA的重叠社区检测算法研究D.兰州：兰州大学,2 0 19.8郭峰,尤凯丽，李昕泽.基于节点重要性和局部扩展的重叠社区发现算法J.计算机与数字工程2 0 2 0,48(12):2906.9赵宇红，张凯.一种基于注意力机制的节点相似性度量方法J.内蒙古科技大学学报，2 0 2 1,40（0 2）：17 4.10GROVER A,LESKOVEC J.Node2vec:scalable fea-ture learning for networks C/Proceedings of the 22ndACM SIGKDD international conference on Knowledgediscovery and data mining.San Francisco,California:ACM,2016:855.11TANG J,QU M,WANG M,et al.Line:Large-scaleinformation network embedding CJ/Proceedings of the24th international conference on world wide web.Flor-ence,Italian:IEEE,2015:1067.12PAN S,WU J,ZHU X,et al.Tri-party deep networkrepresentationJ.Network,2016,11(9):12.13ZHANG Z,CUI P,WANG X,et al.Arbitrary-orderproximity preserved network embedding cJ/Proceed-ings of the 24th ACM SIGKDD international conferenceon knowledge discovery&data mining.London,UnitedKingdom:ACM,2018:2778.14GOYAL P,FERRARA E.Graph embedding tech-niques,applications,and performance:A surveyJ.Knowledge Based Systems,2018,151:78.15SHEN H,CHENG X,CAI K,et al.Detect verlappingand hierarchical community structure in networks J.Physica A:Statistical Mechanics and Its Applications,2009,388(8):1706.