![点击分享此内容可以赚币 分享](/master/images/share_but.png)
基于相似度加强Louvain方法的复杂网络社区检测.pdf
《基于相似度加强Louvain方法的复杂网络社区检测.pdf》由会员分享,可在线阅读,更多相关《基于相似度加强Louvain方法的复杂网络社区检测.pdf(5页珍藏版)》请在咨信网上搜索。
1、信息技术XINXIJISHU2023年第10 期基于相似度加强Louvain方法的复杂网络社区检测付立东2,吴鸿飞*(1.西安科技大学计算机科学与技术学院,西安7 10 0 54;2.西安电子科技大学计算机科学与技术学院,西安7 10 0 7 1)摘要:在针对复杂网络的社区检测问题中,基于模块度的社区划分方法Louvain Method(LM)迭代算法被广泛的应用,但是考虑到该算法在第一次迭代过程中的时间复杂度非常大,为了解决这个问题,文中引入了OLM方法,对复杂网络中的节点利用相似性的度量方法进行处理,从而优化整个网络结构,来更高效地使用该算法识别社区。实验结果表明,提出的OLM方法具有更高
2、的效率和稳定性。关键词:社区检测;社区划分;相似度;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 S
3、cience 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
4、,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 p
5、roposed 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),男,博士,副教授,研
6、究方向为复杂网络计算与分析。*通讯作者:吴鸿飞(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-m
7、an基于启发式规则提出著名的社区挖掘方(2)基于相似度加强Louvain方法的复杂网络社区检测法一GN(Girvan-Newman)算法,通过对边介数个迭代阶段需要处理的网络结构,降低了Louvain的反复计算,用自顶向下的方法得到了划分后的算法的时间复杂度。结果表明,OLM算法具有更社区,并且划分的结果很好,但是该算法的计算速高的准确率和稳定性8 度较慢。2 0 0 4年Girvan和Newman针对GN算法1.1相似性度量中无衡量社区划分标准的不足,引人了模块度Q在所提出的 OLM方法的第一步中,本文认为的计算4。目前社区发现算法中计算速度较快给定网络的每个节点都充当一个单独的集群。对的算
8、法是Louvain算法,由VincentD.Blondel等网络的每个节点用p来描述,用9来表示相邻节人在2 0 0 8 年提出,Louvain算法就是一种基于模点的数量。节点p可以与q个相邻节点形成社块度的社区划分方法5,该算法在效率和效果上区,这意味着节点p有q个社区用于其移动。另都表现比较好,并且能够发现层次性的社区结构。一方面,节点P必须选择最佳的相邻节点或社区本文在 Louvain算法的基础上,研究了 Lou-进行移动。为了识别最佳相邻节点或社区,节点vain算法的原理,指出其存在的缺陷,由于该算法p与所有相邻节点连接,对于节点p的每次移动,在第一次迭代过程中的时间复杂度非常大,为了
9、都将计算其皮尔逊相关系数(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算法在真实网络中进行本文用到的相似性度量方法是皮尔逊相关系实验,
10、结果表明,该算法具有更高的准确率和稳数PCC,又称皮尔逊积矩相关系数(Pearsonprod-定性。uct-moment correlation coefficient),在自然科学领1Optimized Louvain Method(OLM)域中,皮尔逊相关系数广泛用于度量两个变量之Louvain算法是一种贪婪优化方法,该算法包间的相关程度,其值介于-1与1之间。括两个阶段,第一个阶段是不断地遍历网络中的两个变量之间的皮尔逊相关系数定义为两个节点,假设每个节点为1个社区,网络中有N个变量之间的协方差和标准差的商:节点,即初始化N个社区,尝试将单个结点加人cov(X,Y)_ E(X-X)(Y-
11、Y)1到能够使模块度提升最大的社区中,直到所有节Px,Y=oXoy点都不再发生变化。第二个阶段是处理第一阶段遍历的结果,聚合每个小社区的节点,并使用这些节点构建一个新的网络,反复迭代这两个阶段,直到网络的模块度最大化。Louvain算法的第一个阶段中,由于遍历整个网络节点相当耗时,因此Louvain算法的缺点就是第一个阶段的时间复杂度很高。本文引人了一种新的方法,优化型Louvain方法(OLM)来识别复杂网络中的社区。首先该算法利用皮尔逊相关系数的相似性度量方法来检测大型网络中的数据,将相似性高的数据添加相同的标签,当对网络中所有数据处理完成之后会得到一个优化后的初始社区,再用Louvain
12、算法对该社区进行划分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方法的复杂网络社区检测
13、-当相关系数为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个社区,那
14、么定义一个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,否
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 相似 加强 Louvain 方法 复杂 网络 社区 检测
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。