基于图分割的关键节点挖掘算法研究

论文摘要

本文以网络鲁棒性最小化为图分割目标,进行关键节点挖掘,寻找对于维持网络结构有重要意义的节点。此问题在实际应用中有重要意义,识别网络中的重要节点,能让我们在传染病网络中更好地控制疾病传播,在电力网中更高效地维护基础设施等。由于关键节点挖掘在实际中的重要价值,其成为了复杂网络研究中的热点问题。本文深入分析了网络鲁棒性的性质,并提出了规划反向目标算法。之后改进了鲁棒性指标的定义,并基于新定义提出了一种新的关键节点挖掘算法。本文的主要研究内容和创新点如下:(1)本文深入分析了网络鲁棒性的定义和性质。证明了网络鲁棒性的取值范围,证明了其最优序列特性和结合律。最优序列特性表明最优序列每次选取的节点必定在网络当前的最大连通分支中。结合律表明了在符合最优序列特征的条件下,可以用网络各部分的结果直接计算合成网络的结果。(2)基于网络鲁棒性的分析,提出了规划反向目标算法。规划反向目标算法中引入了社团发现方法,先探测网络的结构,将网络中的节点分为社团内部节点和社团边缘节点。根据节点类型的不同,然后进行关键节点挖掘。最后使用移除节点序列优化方法对已获得结果进行优化,得到最终结果。此方法和其他常见方法相比,取得了较好的结果。(3)本文指出传统鲁棒性指标的不足,提出了新鲁棒性指标的定义,并证明了新鲁棒性指标的各种性质。网络鲁棒性标准主要关注网络的最大连通分支,没有考虑到节点之间的差异,其不能很好地应用于有节点权重的网络。新网络鲁棒性考虑了节点权重。本文深入分析了新网络鲁棒性的取值范围特点、最优序列特征、结合律等特性,并比较了其与原有网络鲁棒性在这些特性上异同。证明了两种定义的兼容性。(4)基于新网络鲁棒性指标,本文提出了新反向目标算法,从而能更好地挖掘出网络中的关键节点。新反向目标算法将最小化关键连通分支重要性作为贪心目标。在多个实际网络和模型网络中,新反向目标算法都获得了较好的结果。本文分析了实验结果差异产生的原因。从概率论的角度,证明了在网络趋于无穷大时,在任意的网络结构下,在任意的节点权重随机分布下,对于任意的节点移除序列,其新网络鲁棒性值收敛到原有网络鲁棒性值。

论文目录

摘要

abstract

第一章绪论

1.1 研究工作的背景与意义

1.2 关于图分割与关键节点挖掘的研究现状

1.3 本文的主要贡献与创新

1.4 本文结构安排

第二章复杂网络相关理论和技术

2.1 图分割问题

2.2 网络鲁棒性

2.2.1 鲁棒性概念和意义

2.2.2 网络鲁棒性的相关研究

2.3 关键节点挖掘算法

2.3.1 随机选取

2.3.2 节点中心性方法

2.3.3 CI指数

2.4 社团划分算法

2.4.1 Kernighan-Lin算法

2.4.2 简单模块度最大化算法

2.4.3 基于边介数的方法

2.5 本章小结

第三章网络鲁棒性分析与其最优化关键节点挖掘

3.1 网络鲁棒性

3.1.1 网络鲁棒性的定义

3.1.2 网络鲁棒性的取值范围

3.1.3 网络鲁棒性的最优序列特征

3.1.4 网络鲁棒性的结合律

3.2 规划反向目标算法的提出与分析

3.2.1 问题的提出

3.2.2 规划反向目标算法

3.2.3 实验分析

3.3 本章小结

第四章网络鲁棒性重定义与其最优化关键节点挖掘

4.1 新网络鲁棒性

4.1.1 新网络鲁棒性的定义

4.1.2 新网络鲁棒性的取值范围

4.1.3 新网络鲁棒性的最优序列特征

4.1.4 新网络鲁棒性的结合律

4.1.5 新网络鲁棒性的兼容性

4.2 新反向目标算法

4.2.1 基于新网络鲁棒性的反向目标算法

4.2.2 实验及分析

4.2.3 数学分析实验过程

4.3 本章小结

第五章全文总结与展望

5.1 全文总结

5.2 后续工作展望

致谢

参考文献

攻读硕士学位期间取得的成果

文章来源

类型: 硕士论文

作者: 胡清华

导师: 周涛

关键词: 网络鲁棒性,反向目标算法,关键节点挖掘,图分割,复杂网络

来源: 电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 电子科技大学

分类号: O157.5

总页数: 80

文件大小: 2460K

下载量: 86

基于图分割的关键节点挖掘算法研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢