融合节点重要性与影响力的重叠社团检测算法.pdf
《融合节点重要性与影响力的重叠社团检测算法.pdf》由会员分享,可在线阅读,更多相关《融合节点重要性与影响力的重叠社团检测算法.pdf(5页珍藏版)》请在咨信网上搜索。
1、以重叠社团检测算法 COPRA作为基础,给出了一个结合节点重要性与节点影响力的重叠社团检测算法COPRANNI.首先,使用一种在三角形构成基础上的节点重要性,以此确定节点更新顺序其次,使用Node2vec模型遍历网络生成节点序列,在此基础上利用Skip-gram 模型获得节点的低维向量,然后通过余弦相似度量标准获取相似值将该相似性和重要性融合确定的节点影响力引入到隶属系数中,进行标签传播,待稳定收敛后,最终发现重叠社团通过在多个数据集上进行实验,结果表明:该论文提出的算法在重叠社团EQ质量指标上有较好表现.关键词:三角形构成;社团检测;标签选择;综合影响力中图分类号:TP393文献标识码:A文
2、章编号: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 0
3、14010,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 t
4、o 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
5、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
6、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、交通、谣言控制等领域都得到较广泛的应用和研究,同时复杂
7、网络在物理、数学以及生物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 网络的拓扑属性和社团结构,对于
8、理解现实世界系统的功能和组织至关重要其中社团结构表达的是网络中节点的聚合群体特性即一组彼此紧密连接但与网络的其余部分分离良好的节点4 社团检测促进了研究者对复杂网络社团结构的研究。如今,复杂网络中的重叠网络同样也是很多研究者关注的重点,对于重叠社团的研究也有很多。GREGORY5提出了针对重叠社团的标签传播算法COPRA,该算法在传播路径和传播影响力2 方面均存在随机性的问题,且在传递过程中一次会传递多个标签,为防止每个节点接收到过多标签进行参数设定,但是在大规模复杂的网络中预设参数很难实现.XIE等人受参数限制的启发提出SLPA算法6 进行重叠社团检测,其在传播过程中,一次只传递一个标签,且
9、社团个数对该算法没有限制,但同样存在标签传递随机性的问题在SLPA基础上,张静宜提出了DSLPA7,解决了标签传播随机性的问题,同时提出MSLPA,该算法让SLPA与模块度进行结合郭峰等8 人在DOCNet算法基础上提出了一种新颖的重叠社团检测算法DOCLLE,该算法分别在初始节点的选择以及标签对应社团的系数计算方法上进行了改进和优化,但忽略了网络结构的稀疏性.赵宇红等9 人在社团检测的节点相似方面提出了新的相似性度量标准,该相似性在节点和元路径2方面使用注意力机制进行计算,提高了社团检测的准确性,但没有考虑节点的个体信息。不同研究者针对标签传播的随机性进行改进,但均没有在标签传播中充分考虑节
10、点的属性信息及节点间关联影响,复杂网络的重叠社团检测仍然是一个开放性问题本文在COPRA算法基础上进行了改进和优化,针对该重叠社团检测算法中初始节点选取和标签传递随机性的问题,给出了一个新颖的社团检测方法通过对节点重要性的量化解决标签传播过程中选择初始节点的随机性,利用节点影响力的度量改善标签传播过程中选取邻居节点标签的随机性,以挖掘更加稳定的重叠社区。1相关知识1.1COPRA算法COPRA算法中引人隶属系数来衡量节点x对社区c的归属程度,隶属系数的计算公式如式(1)所示:bt-1(c,y)b,(c,):YEN(x)(1)I N(x)I式中:N()为节点的周围邻居节点所组成的集合;b,(c,
11、x)为轮更新时节点在社区c的归属程度.算法描述如下:a)首先,给网络中任意一个节点x,设置为(cs,1).b)利用式(1)更新节点的隶属系数b(c).淘汰隶属系数小于1/v的标签,如果这些值均小于1/v,则留下值最大的标签如果标签有多个,随机选择一个之后归一化。c)随着节点对应的社区标签稳定时,认为该算法已经达到收敛;否则将继续进行步骤b).1.2网络嵌入模型网络嵌人将网络的结构或内容用低维的向量来表示,将原有的高维离散特征用低维的连续特征表示,因为低维的向量在机器学习领域有较广泛的使用价值,所以网络嵌人模型被有效的运用到社团检测领域.DeepWalk是最早被用于网络中社团检测领域的嵌人模型,
12、它的主要思想是利用自然语言处理中的Skip-gram模型来获取网络中节点的特征向量.Node2vec模型10 在其模型基础上,对节点走向的方式进行了改进,通过广度遍历和深度遍历生成随机游走序列,能够更好地反映网络结构.Line算法1定义了2 种节点之间的相似性,通过提出目标函数对节点特征进行优化:以上均是针对网络拓扑结构的网络表示学习,对属性的学习有所欠缺随着各种各样的网络出现,网络中节点的属性对于社团划分也极其重要。TriDNR12的方法宗旨是利用结构、属性以及标签信息来进行属性网络的表示学习,该算法融合了DeepWalk以及Doc2vec嵌人节点、文本和标签信息的思想文献13 提出了一个可
13、扩展的特征分解解决方案来推导出嵌入向量,并在任意阶数的近似性之间进行转移文献14 提出了一种新的策略来保证学习的节点表示能够编码来自拓扑结构和节点属性的一致和互补的信息,本文将网络嵌入与标签传播进行了结合,使用Node2vec模型与Skip-gram模型做嵌人,为节点相似性的度量奠定了基础.1362023年6 月第42 卷第2 期内蒙古科技大学学报2算法设计2.1节点重要性和影响力度量1)节点重要性在复杂网络领域中,挖掘节点一般分为单个节点的挖掘以及节点组的挖掘,重要节点的挖掘方法也有很多种在复杂网络中如果一个节点在网络中属于影响力较大的节点,往往会存在一些特征:一种情况是,当网络中的节点与其
14、他节点存在较多连边时,通常会判定这种节点的度会较大;另一种情况是,当网络中的节点与其周围节点交互较多时,往往这类节点同邻居节点所构成的三角形数量也会更多。所以可解释为,网络中的节点存在较大的度,且包含该类节点的三角形个数较多时,往往这类节点有较大可能性属于社区中影响力较大的节点。在以上假设的基础上,提出重要度概念来量化重要性,其是依赖于三角形构成,如式(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
15、.5 1之间,对该式子进行归一化.2)节点相似性度量节点相似性的概念体现的是节点间联系的相关性,而这种相关性也是对节点影响力的一种体现,本文算法对于节点相似性的量化是通过节点嵌人学习而获得的首先,基于Node2vec模型遍历得到序列;然后,通过Skip-gram学习目标序列获取网络中每个节点的低维向量;最后,获得节点间的相似值是利用了余弦相似指标,相似值的获得可以应用到节点影响力当中.Node2vec模型中给出一个控制游走方向的算法,固定其随机游走的步长为,使用如式(3)分布产生邻居序列:TTuxif(v,x)=E.(3)P(c;=ci-1=v)ZLootherwise在式(3)中:归一化因子
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 融合 节点 重要性 影响力 重叠 社团 检测 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。