基于相似度加强Louvain方法的复杂网络社区检测.pdf

信息技术XINXIJISHU2023年第10 期基于相似度加强Louvain方法的复杂网络社区检测付立东2,吴鸿飞*（1.西安科技大学计算机科学与技术学院，西安7 10 0 54；2.西安电子科技大学计算机科学与技术学院，西安7 10 0 7 1)摘要：在针对复杂网络的社区检测问题中，基于模块度的社区划分方法Louvain Method(LM)迭代算法被广泛的应用，但是考虑到该算法在第一次迭代过程中的时间复杂度非常大，为了解决这个问题，文中引入了OLM方法，对复杂网络中的节点利用相似性的度量方法进行处理，从而优化整个网络结构,来更高效地使用该算法识别社区。实验结果表明,提出的OLM方法具有更高的效率和稳定性。关键词：社区检测；社区划分；相似度；LouvainMethod；O L M中图分类号：TP393D0I:10.13274/ki.hdzj.2023.10.003Community detection based on similarity Optimized Louvain Method in complex networksFU Li-dong*-,WU Hong-fei!(1.The School of Computer,Xi an Univ.of Science and Technology,Xi an 710054,China;2.School ofComputer Science and Technology,Xidian Univ.,Xi an 710071,China)Abstract:In the community detection problem for complex networks,the community division method,Lou-vain Method(LM)iterative algorithm based on modularity is widely used,but the time complexity of the al-gorithm in the first iteration process.Thus,in order to solve this problem,this paper introduces the OLMmethod to process the nodes in the complex network by using the similarity measurement method,so as tooptimize the whole network structure and use the algorithm to identify the community more efficiently.Ex-periment results show that the proposed OLM method has higher efficiency and stability.Key words:community detection;community division;similarity;Louvain Method;OLM0 引 言随着互联网大数据时代的到来，网络空间中数据对象的关系变得错综复杂，例如社交网络中感兴趣的人、病毒的传播等,那么分析和研究这些基金项目：国家自然科学基金面上项目（6 17 7 2 394）；陕西省自然科学基础研究计划项目（2 0 2 0 JM-526,2020JM-533）作者简介：付立东（197 3），男，博士，副教授，研究方向为复杂网络计算与分析。*通讯作者：吴鸿飞（1998），男，硕士研究生，研究方向为复杂网络计算与分析。一 12 一文献标识码：A文章编号：10 0 9-2 552(2 0 2 3)10-0 0 12-0 5网络的结构就成为了如今研究的重点，对于复杂网络的研究具有很重要的现实意义。社区检测是复杂网络的一个重要研究课题，社区检测的目的是发现网络中的社区结构2 。大多数情况下,同一个社区中的节点由于其接近性而具有相似的特征。在过去的二十年中,已经发现了不同的社区检测方法，这些方法可以分为两类：基于模块度的社区划分方法和基于节点相似性的社区划分方法3。2 0 0 2 年,Girvan 和New-man基于启发式规则提出著名的社区挖掘方(2)基于相似度加强Louvain方法的复杂网络社区检测法一GN(Girvan-Newman)算法,通过对边介数个迭代阶段需要处理的网络结构,降低了Louvain的反复计算,用自顶向下的方法得到了划分后的算法的时间复杂度。结果表明，OLM算法具有更社区,并且划分的结果很好,但是该算法的计算速高的准确率和稳定性8 度较慢。2 0 0 4年Girvan和Newman针对GN算法1.1相似性度量中无衡量社区划分标准的不足，引人了模块度Q在所提出的 OLM方法的第一步中,本文认为的计算4。目前社区发现算法中计算速度较快给定网络的每个节点都充当一个单独的集群。对的算法是Louvain算法，由VincentD.Blondel等网络的每个节点用p来描述，用9来表示相邻节人在2 0 0 8 年提出,Louvain算法就是一种基于模点的数量。节点p可以与q个相邻节点形成社块度的社区划分方法5,该算法在效率和效果上区,这意味着节点p有q个社区用于其移动。另都表现比较好,并且能够发现层次性的社区结构。一方面，节点P必须选择最佳的相邻节点或社区本文在 Louvain算法的基础上,研究了 Lou-进行移动。为了识别最佳相邻节点或社区，节点vain算法的原理,指出其存在的缺陷,由于该算法p与所有相邻节点连接,对于节点p的每次移动，在第一次迭代过程中的时间复杂度非常大,为了都将计算其皮尔逊相关系数（PCC）。因此,得到解决这一问题,引入了一种新的方法一一基于皮了关于给定网络中节点p的所有邻居的q个PCC尔逊相关系数 PCC（Pe a r s o n C o r r e la t io n C o e f f i-值。节点p基于皮尔逊相关系数的绝对值最大值cient)6的相似性度量进行的优化Louvain方法加入其相邻社区。对每个节点重复应用该步骤，（O p t i mi z e d L o u v a i n M e t h o d），并使用模块度来评直到所获得的社区没有变化。估社区的质量。将OLM算法在真实网络中进行本文用到的相似性度量方法是皮尔逊相关系实验，结果表明，该算法具有更高的准确率和稳数PCC,又称皮尔逊积矩相关系数（Pearsonprod-定性。uct-moment correlation coefficient），在自然科学领1Optimized Louvain Method(OLM)域中，皮尔逊相关系数广泛用于度量两个变量之Louvain算法是一种贪婪优化方法,该算法包间的相关程度,其值介于-1与1之间。括两个阶段,第一个阶段是不断地遍历网络中的两个变量之间的皮尔逊相关系数定义为两个节点，假设每个节点为1个社区,网络中有N个变量之间的协方差和标准差的商：节点，即初始化N个社区，尝试将单个结点加人cov(X,Y)_ E(X-X)(Y-Y)1到能够使模块度提升最大的社区中,直到所有节Px,Y=oXoy点都不再发生变化。第二个阶段是处理第一阶段遍历的结果,聚合每个小社区的节点,并使用这些节点构建一个新的网络,反复迭代这两个阶段,直到网络的模块度最大化。Louvain算法的第一个阶段中,由于遍历整个网络节点相当耗时,因此Louvain算法的缺点就是第一个阶段的时间复杂度很高。本文引人了一种新的方法，优化型Louvain方法(OLM)来识别复杂网络中的社区。首先该算法利用皮尔逊相关系数的相似性度量方法来检测大型网络中的数据,将相似性高的数据添加相同的标签，当对网络中所有数据处理完成之后会得到一个优化后的初始社区，再用Louvain算法对该社区进行划分7 ,优化了Louvain 算法第一J一付立东等(1)其中,cov(X,Y)是协方差;X 是 X 的标准差;Y是Y的标准差;E为数学期望或均值。为了使得皮尔逊相关系数能够应用在检测复杂网络中节点间的相似度，该公式可定义为：E,(Axk-x)(Ayk=r)Px.Y=NoXoY其中,N表示网络中的所有节点；K表示网络中所有节点的其中一个节点;Axk表示在无权图中X节点和K节点是互相连接，当X节点与K节点连接时Axk=1,否则Axk=0;x=Z,Ax/N表示平均值，节点X的标准差公式如下：oX=/Z,(Axk-x)(3)一13 一基于相似度加强Louvain方法的复杂网络社区检测-当相关系数为1时，成为完全正相关,当相关系数为-1时,成为完全负相关，相关系数的绝对值越大,相关性越强；相关系数越接近于0,相关性越弱,相关系数绝对值对相关性强度的影响如表1所示。表1相关强度相关系数绝对值相关强度0.8 1.0极强相关0.6 0.8强相关0.4 0.6中等程度相关0.2 0.4弱相关0.0 0.2极弱相关或无关1.2模块化的优化在进行相似性度量步骤之后，将获得基于PCC优化后的社区,OLM方法的这一步中,本文将找到社区的模块化度量值,模块化度量是目前常用的一种衡量网络中社区稳定度的方法,用于检测社区结构的质量。Newman最早提出了模块度的概念，假设网络被划分为k个社区，那么定义一个kk的对称矩阵e,它的元素e;表示社区i和社区j之间的边的数量,则用矩阵的迹T来表示在相同社区内节点之间的边集合，当社区内部的节点间密集联系，也就是社区划分效果很好时，对称矩阵的迹T也就越高。但同时，如果将网络仅划分为一个社区,那么T的值也为1,因此又定义了一个值;，表示所有连接到社区i的数量。那么模块度的计算公式如下：Q=2Z(其中,A,是整个网络对应的邻接矩阵的任意元素，若节点i与节点之间有连边，则A=1,否则A,=0;m表示了网络的总边数;k;,k,为节点i与节点i的度值;ci,c,为节点i与节点j所在的社区;8(c;,c）是Kronecker函数,当c;=c,时,该值为1,否则为0,当所有节点都归属于同一社区时，Q=0,因此Q的值越大说明网络社区的结构越清晰。2社区的聚合在对网络进行模块度初始优化后，将得到基一14一付立东等于模块化和Pearson 相关系数PCC 度量的初始社区结构。进行多次迭代使网络结构的模块度得到最大化，直到所有节点不再进行移动，意味着模块度优化阶段的结束。算法再次通过相似性度量步骤中获得的节点得到社区，组成新的网络社区结构。不断地重复相似性度量与模块度优化这两个阶段，在更深的层次对社区结构进行优化,直到网络的结构不再发生变化，且没有更大模块化值的社区出现。其中对于每次更深层次的节点聚合，需要将算法前一次划分出的社区重新当作一个节点来考虑，这个节点组合被称为超节点。3实验和结果本文提出的优化Louvain方法在五种不同的真实网络上进行了实验。通过与Louvain算法、GN算法进行比较9,对OLM算法进行了测验与分析。3.1 结果实验结果表明,与 Louvain算法和 GN算法相比,OLM方法具有更大的模块度值，社区划分效果更好。高模块度的方法能够提供最佳的社区结构10 。因此,OLM方法提供了网络中更好的社区结构。该方法得到模块度值如表2 所示表2 模块度值网络LouvainPolbooks0.5212Facebooks0.8353Adjnoun0.2834Football0.5592(4)Karate表2 表明三种方法对应五种网络的模块度值Q。对应的图标如图1所示。真实网络模块度10.50PolbooFacebo.Adjinou.#LouvainOLM.GN图1模块度对比图OLM0.52470.84120.30170.60450.41510.4188#，GN0.50750.81210.08050.59960.4012基于相似度加强Louvain方法的复杂网络社区检测三种方法在五个社区中对应的模块性以及节划分方法相比,OLM的模块度值更高,并且与 GN点数量情况如图2 所示。方法相比，该方法显然更加稳定。Football网络中有115个节点与6 13条边,用模块性和节点数量所提出的0 LM方法得到了10 个社区和0.6 0 450.5的模块度值，结果表明，OLM方法依旧是三个方法中社区划分效果最好的。0105-O-OLMI.Louvain-GN图2 模块度和节点数量三种方法在五个社区中对应的模块性以及边数量情况如图3所示。模块性和边数量0.50441OLM.Louvain-GN图3模块度和边数量从图2-3中可以看出，提出的OLM方法比其他两个算法的模块度值更高，划分的社区效果更好，当面对复杂网络中不同的节点数和边数，OLM所带来的社区划分效果更加稳定。3.2分析在五个真实世界网络上对提出的OLM方法和其他现有方法进行了分析。OLM方法中采用的性能评估标准是模块度，模块度的大小将决定了社区的质量，社区的结构越好，模块度越大。Polbooks网络由10 5个节点和441条边组成。将OLM方法在Polbooks网络中进行测试,最终将网络分为了4个社区,测量得到的模块度为0.5247。提出的OLM方法计算出的模块度高于现有方法。因此与其他现有方法相比,所提出的OLM方法实现的社区结构更好。Facebooks网络由40 39 个节点和8 8 2 34条边组成。在Facebooks网络中应用了OLM方法,得到16 个社区和0.8 412 的模块度。将0 LM与其他方法的模块度值进行对比，实验证明该方法得到的社区结构更好。Adjnoun网络是由112 个节点与42 5条边组成的,用OLM方法计算该网络,得到了6 个社区与0.30 17 的模块度值,将0 LM方法与其他社区一付立东等1121154256133440397888234Karate网络是经典的社区网络,其中有34个节点与7 8 条边，OLM方法将Karate网络划分为5个社区，得到了0.418 8 的模块度值，实验证明，提出的OLM方法具有更高的社区划分效果。从实验角度分析，通过反复改变相似度的闯值，最终发现在皮尔逊相似度值达到0.54时，OLM方法的模块度值最高,如果相似度阈值高于0.54,则会将网络中本该在一个社区的节点忽略，导致社区划分效果不佳，但若相似度阈值低于0.54,则会让更多的节点归于同一个社区,导致划分的社区数量减少,从而降低社区结构的清晰度。同时,通过对复杂网路中节点相似度的处理，解决了用Louvain算法过程中时间复杂度太大的问题，由反复迭代的计算社区模块度变为计算网络节点相似性,加强了社区划分效率,并且提升了社区划分质量，使得OLM实现的模块化价值大于原有方法。根据从网络中获得的初始社区、模块化值和社区质量来评估方法的性能，OLM方法获得的社区结构质量优于其他方法，也更加稳定。4结束语在过去的几年里，有很多方法来检测复杂网络中的社区结构,本文提出了一种基于相似度来加强Louvain算法的社区划分方法一优化Lou-vain方法（OLM）,用于表示复杂网络中的社区结构。本文用一种新的相似性度量,即皮尔逊相关系数(PCC)来开始寻找网络中的社区结构,再使用了模块化度量来评估网络中社区结构的质量。PCC方法发现了两个节点之间的相似性,然后选择具有高PCC值的节点,并与最相似的节点连接。对所提出的OLM方法的性能进行了评估,并与现有方法进行了比较,结果表明OLM方法效果更好,也更加稳定。但由于现实世界网络中会出现大量的重叠社区1,该方法不能有效地解决一个节点同时属于两个或多个社区的情况，导致一15一基于相似度加强Louvain方法的复杂网络社区检测-OLM算法还有一些缺陷可以去改善。另外可以去创建一个能够运用此类算法的平台，让所有想得到引荐功能或数据挖掘功能的用户可以简单地自定义数据集，来实际地应用算法，有效地解决生活问题,所以还需要进一步的实验和探讨。参考文献：1郭拴岐.大数据分析技术的海量网络流量建模与预测分析J.信息技术,2 0 2 1,45（4):10 2-10 6,112.2 Fortunato S.Community detection in graphs J.PhysicsReports,2010,486:75-174.3杨博,刘大有,金弟，等.复杂网络聚类方法J.软件学报,2 0 0 9,2 0(1):54-6 6.4 Newman M E J,Girvan M.Finding and evaluating com-munity structure in networks J.Physical Review E,2004,69(2):2-6.5 Blondel V D,Guillaume J L,Lambiotte R,et al.Fast un-folding of communities in large networks J.Journal ofStatistical Mechanics:Theory and Experiment,2008(10):一付立东等52 60.6张宇镭，党,贺平安.利用Pearson相关系数定量分析生物亲缘关系J.计算机工程与应用,2 0 0 5（33）：79 82.7夏玮,杨鹤标.改进的Louvain算法及其在推荐领域的研究J.信息技术,2 0 17,41(11）：12 5-12 8.8 Lei L I,Yan G,Yang S,et al.Improved Louvain methodwith strategy of se-parating isolated nodes J.Journal ofComputer Applications,2017,33(2):27-33.9徐杨，蒙祖强.基于GN算法的微博社区识别方法J.广西大学学报：自然科学版，2 0 13,38（6）：1413-1417.10杨立文.基于改进的GN算法的社区发现技术D.长春：吉林大学,2 0 13.11许国艳，王诗玉,孙洁.一种基于局部模块度的层次重叠社区发现方法：CN201811024092.1P.2 0 19-02 15.（责任编辑：杨静）(上接第 11 页)5艾琦，王军,任福全，等.基于尺寸自适应深度神经网络的胸部CT图像肺结节检测J.中国生物医学工程学报,2 0 2 1,40(6):6 91-7 0 0.6 Shen W,Zhou M,Yang F,et al.Multi-scale convolutionalneural networks for lung nodule classification C.Inter-national Conference on Information Processing in Medi-cal Imaging.Springer,Cham,2015:588-599.7匡健,洪敏杰,刘星辰，等.基于注意力机制的肺结节分类研究J.计算机应用与软件,2 0 2 2,39（1）：16 3-167.8 Zhu W,Liu C,Fan W,et al.Deeplung:deep 3d dualpath nets for automated pulmonary nodule detection andclassification C.2018 IEEE Winter Conference on Ap-plications of Computer Vision(WACV).IEEE,2018:673-681.9 Chen Y,Li J,Xiao H,et al.Dual path networks EB/OL.(2017-08-01)2017-10-01.https:/arx-iv.0rg/abs/1707.01629.10 Friedman J H.Greedy function approximation:a gradi-ent boostingmachine J.Annals of statistics,2001,29(5):1189-1232.11 Setio A A A,Traverso A,De Bel T,et al.Validation,comparison,and combination of algorithms for automaticdetection of pulmonary nodules in computed tomographyimages:the LUNA16 challengeJ.Medical Image A-nalysis,2017,42:1-13.12 Yan X,Pang J,Qi H,et al.Classification of lung nodulemalignancy risk on computed tomography images usingconvolutional neural network:A comparison between 2dand 3d strategies C.Asian Conference on ComputerVision.Springer,Cham,2016:91-101.（责任编辑：丁晓清）一16 一