一种高效的复杂网络重叠社团挖掘算法

论文摘要

复杂网络的重叠社团挖掘算法用来解决识别复杂网络中重叠社团的问题,有助于获取与了解复杂网络的整体结构特性。由于重叠社团挖掘中一个节点可能属于多个社团,用传统的社团挖掘算法无法识别出同属于多个社团的节点。随着社会和科技的发展,复杂网络的规模越来越大,现有的重叠社团挖掘算法在处理如此大规模的网络时效率较低。因此,需要更快速的算法来更好的应对大型复杂网络中重叠社团挖掘问题。本文提出一种先在整个网络中选取种子,后通过收益函数对种子进行局部优化,发现复杂网络的重叠社团结构的算法。工作主要分为两部分,首先,在整个网络中选取种子,本文提出了两种播种策略:“社团扩张”和“高度节点扩张”。“社团扩张”播种策略使用Louvain算法对网络进行初始划分,将得到的划分结果作为种子集合;“高度节点扩张”播种策略采用度优先的方式选取种子,这里需要注意的是,本文使用的度优先选取种子的方式考虑到已选种子对后续选取种子的影响,在每次确定一个种子之后都对剩余节点的度进行更新。然后,用收益函数对种子集合中的种子依次优化,从每个种子进行扩张。通过收益函数判断邻域节点是否可以加入社团以及社团内部节点是否删减,直到收益函数达到局部最优,确定社团结构。本文提出的算法避免了在挖掘社团的每次迭代中搜索整个网络。本文从理论上对算法的时间复杂度进行分析,并在真实数据集上进行实验,从算法运行时间与实验结果准确性两方面验证算法的性能,且与BigClam算法,OSLOM算法,DEMON算法进行对比。实验结果表明,本文提出的算法中,在通过Louvain算法选取种子时,算法准确率略低于所对比的DEMON算法,但是算法的运行效率高于所对比的三种算法,且明显高于BigClam算法。在使用度优先策略选取种子时,算法的运行效率与准确率均高于所对比的三种算法。本文提出的算法能准确的挖掘出复杂网络中的重叠社团,并具有高效的优点,可以用于大规模复杂网络重叠社团挖掘。

论文目录

文章来源

类型: 硕士论文

作者: 兰小明

导师: 高琳,豆增发

关键词: 复杂网络,重叠社团,社团挖掘,局部优化

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安电子科技大学

分类号: O157.5

DOI: 10.27389/d.cnki.gxadu.2019.002683

总页数: 61

文件大小: 2424K

下载量: 47

相关论文文献

• [1].加强经管学科中算法分析与设计教学的建议[J]. 知识经济 2019(34)
• [2].《算法分析》教学方法探索[J]. 现代计算机 2020(02)
• [3].《算法分析与设计》专题探究式教学改革与实践[J]. 湖北开放职业学院学报 2020(04)
• [4].算法分析与复杂性理论课程案例化教学改革[J]. 计算机教育 2020(04)
• [5].算法分析与设计(双语)课程实践教学模式探索[J]. 中国管理信息化 2017(19)
• [6].应用型人才培养中《算法分析与设计》课程教学方法研究[J]. 科技资讯 2017(04)
• [7].中国古代算法的探究与模型建立[J]. 中华少年 2017(04)
• [8].求离散点最小包围圆在算法初步教学中的案例分析[J]. 中华少年 2017(11)
• [9].算法初步的几个着力点[J]. 高中生学习(试题研究) 2017(09)
• [10].算法分析与设计——分治法的教学方法浅析[J]. 时代教育(教育教学) 2011(10)
• [11].算法即权力:算法范式在新闻传播中的权力革命[J]. 编辑之友 2018(05)
• [12].应用于词法分析器的算法分析优化[J]. 科技经济市场 2017(05)
• [13].超大容量云服务算法分析[J]. 电脑知识与技术 2017(23)
• [14].算法分析与设计课程研究型教学模式探索与实践[J]. 计算机教育 2015(23)
• [15].信息与计算科学专业“算法分析与设计”研究性教学探索[J]. 中国电力教育 2013(01)
• [16].两种常用指纹方向图算法分析及比较[J]. 信息通信 2017(01)
• [17].“算法分析与设计”教学模式探索[J]. 当代教育理论与实践 2011(12)
• [18].“算法分析与设计”课程教学改革和实践[J]. 中国电力教育 2010(16)
• [19].算法分析中概率变化与图形生成[J]. 云南大学学报(自然科学版) 2009(S2)
• [20].数据差异下的连续数据保护恢复算法分析及应用[J]. 微型电脑应用 2020(08)
• [21].基于《算法分析与设计》中计算思维的运用[J]. 牡丹江教育学院学报 2013(01)
• [22].算法分析与设计课程中多媒体技术的应用[J]. 科技风 2009(18)
• [23].图像去雨雪算法分析[J]. 科技风 2019(30)
• [24].“算法分析与设计”课程教学改革与实践[J]. 工业和信息化教育 2017(03)
• [25].浅谈算法分析与设计课程的教学技巧[J]. 福建电脑 2017(09)
• [26].算法分析与设计课程的拓展式教学[J]. 现代计算机(专业版) 2015(24)
• [27].蝙蝠算法研究及应用综述[J]. 计算机工程与应用 2019(15)
• [28].几种常见特殊方阵的算法分析与实现[J]. 无锡职业技术学院学报 2009(05)
• [29].浅谈“贪心方法”的教学经验[J]. 时代教育(教育教学) 2011(11)
• [30].高校学生补考考场分排算法分析及程序设计[J]. 电脑编程技巧与维护 2008(16)

标签：复杂网络论文;  重叠社团论文;  社团挖掘论文;  局部优化论文;