复杂网络瓦解问题研究

论文摘要

现代科技的蓬勃发展促使社会的网络化进程不断向前推进,因特网、道路网、通信网、电力网……可以说,现代生活的方方面面都被各种网络所包围着。这些网络往往规模庞大、结构复杂,它们既不是简单的规则网络,也不是完全随机的网络,所以研究人员将之命名为“复杂网络”。随着小世界特征以及幂律特性的发现,复杂网络的相关探索随着技术手段的进步经历了近二十年的繁荣发展。绝大多数情况下,我们日常生活中所围绕的网络均为“有益的”,比如通信网络、电力网络、道路交通网络、物流运输网络等实证网络。针对这一类对人类生活明显有益的网络,研究者一直致力于采用优化设计、协调控制、防御修复等多种方法来确保它们持续而高效地运转。然而当这些网络中的节点(边)发生故障或是遭受恶意攻击时,将会对整个网络的结构和功能造成严重破坏。比如,2003年8月北美发生的大停电事件,造成北美共计数十个省份发生大面积停电事故,事后估计的经济损失约300亿美元;2005年12月发生在台湾海峡的地震导致众多途径附近海域的国际海底光缆遭到破坏,造成几乎整个亚太范围内的网络服务中断;2008年1月,我国南方发生了极为严重的冰冻灾害,造成我国数十个省市道路中断、能源告急、供水终止、食物匮乏。正是现实世界中对于网络保护研究的迫切需要,针对有益网络的设计、优化、保护等方面的研究成果已经非常丰富,研究范围涵盖了管理科学、信息技术、数学等多个学科领域。但是,很多时候我们所面对的网络也可能是“有害的”,最典型的例子就是恐怖分子关系网络。当前,恐怖组织已经从传统的等级制结构向网络化结构演化,这些由“恐怖分子”构成的网络通常分布于全球各地,如何有效地摧毁恐怖分子关系网络成为了各国反恐组织所面临的共同难题。另外一个典型例子就是疾病传播网络,近年来,令人闻之色变的传染病接踵而来,如何有效地阻断疾病在人群或动物之间的传播是全球公共卫生领域所面临的艰巨任务,上述这些实例正是复杂网络瓦解问题所面临的实际挑战。随着复杂网络的各类研究不断向前推进,作为复杂网络领域的核心课题之一,复杂网络瓦解问题研究的理论意义和应用价值日益凸显,成为极其重要并富有挑战性的前沿课题。本文以复杂网络理论与方法为基础,综合运用图论、运筹学、启发式算法、计算机数值仿真等多学科领域知识,逐步探究了复杂网络瓦解问题的建模、分析、优化以及应用。论文的主要研究内容与创新点如下所示:1、构建了复杂网络瓦解问题的数学模型。复杂网络瓦解问题的求解即解决如何在各种约束条件和瓦解目标下确定要移除的节点(边)集合,也就是说找到网络系统的“七寸”是网络瓦解问题的核心。所以,网络瓦解问题可以看作一类特殊的“关键节点识别问题”,其本质是一个组合优化问题,立足于上述瓦解问题的本质,本文分别构建了网络基本模型、节点移除模型以及瓦解效果评估模型。2、研究了面向关键节点识别的复杂网络最优瓦解策略。网络瓦解问题是一类特殊的关键节点识别问题,本文针对关键节点识别问题的两种主要研究思路,分别面向节点中心性指标和组合优化思想开展一般化的网络瓦解问题研究。首先引入九种节点中心性指标,对各种中心性指标瓦解策略的效果和适用性进行了深入探讨;然后,对立足于组合优化思想的网络瓦解优化问题进行全面剖析,引入启发式算法对优化模型的目标函数进行求解。进而针对复杂网络瓦解问题的特点,设计了对应的变量编码、移动操作、特赦准则以及终止准则。最后,通过数值实验发现,启发式算法可以有效进行全局寻优并得到近似全局最优解,其瓦解效果远高于当前的多种经典策略,为面向组合优化思想的网络瓦解策略求解提供了一套有效的研究框架与求解算法。3、求解了面向成本约束的复杂网络最优瓦解策略。为了研究考虑成本约束的复杂网络瓦解策略,本文将节点的瓦解成本定义为节点中心性指标取值的指数形式,在此基础上构建了可归一化的成本约束模型,使得基于成本约束模型的网络瓦解问题可以通过成本敏感系数和成本限制系数调节控制。本文首先提出三种典型倾向性瓦解策略来比较其瓦解效果,然后利用遗传算法求解基于成本约束的复杂网络瓦解策略优化模型,在模型网络和实证网络的实验中发现瓦解成本的非匀质性和成本受限对于最优瓦解策略的节点选择倾向性有着显著影响,并且指出当瓦解成本极度异质且成本约束紧缩时,小度节点将在最优瓦解策略中发挥重要作用。4、构建了空间网络的瓦解策略优化模型并引入改进的启发式算法进行求解。无论是成本匀质还是成本约束条件下的复杂网络瓦解问题研究,大多仅关注网络的拓扑结构而忽略了网络的空间属性,从而导致最终得到的实验结果与真实世界存在偏差。因此,本文在构建归一化网络坐标矩阵的基础上,建立了基于瓦解圆模型和空间分割机制的空间网络瓦解策略优化模型,进而引入禁忌搜索算法对优化模型进行求解,并在传统的禁忌搜索中加入初始解优化机制和选择算子来提高算法搜索效率,为空间网络的瓦解问题提供了合理有效的研究框架和求解思路。5、研究了多种类型的实证复杂网络最优瓦解策略。分别以智利电网、马德里火车爆炸恐怖分子关系网络、南佛罗里达雨季食物链网络、政客博客网络、美国航空网络、美国光纤网络以及芝加哥路网为背景进行了应用研究。

论文目录

• 摘要
• Abstract
• 第一章 绪论
•   1.1 研究背景和意义
•     1.1.1 什么是复杂网络
•     1.1.2 什么是复杂网络瓦解问题
•     1.1.3 研究意义
•   1.2 国内外研究现状
•     1.2.1 复杂网络研究现状
•     1.2.2 复杂网络瓦解问题的研究现状
•     1.2.3 研究现状分析
•   1.3 论文主要研究工作
•     1.3.1 论文思路
•     1.3.2 研究内容
•     1.3.3 主要创新点
• 第二章 复杂网络瓦解问题的网络模型与瓦解策略模型
•   2.1 网络的基本概念和模型
•     2.1.1 网络的基本概念
•     2.1.2 网络的基本模型
•   2.2 瓦解策略模型
•     2.2.1 瓦解策略的基本定义
•     2.2.2 经典的瓦解策略分类
•     2.2.3 瓦解效果的测度指标
•     2.2.4 基本瓦解评价模型
•   2.3 本章小结
• 第三章 面向关键节点识别的复杂网络最优瓦解策略研究
•   3.1 基于节点中心性指标的复杂网络最优瓦解策略研究
•     3.1.1 节点中心性指标的基本概念
•     3.1.2 方法原理与算例
•     3.1.3 基于中心性指标的模型网络瓦解效果
•   3.2 基于启发式算法的复杂网络最优瓦解策略研究
•     3.2.1 问题描述
•     3.2.2 求解思路与算法原理
•     3.2.3 基于禁忌搜索的最优瓦解策略实验结果
•   3.3 本章小结
• 第四章 基于成本约束模型的复杂网络最优瓦解策略研究
•   4.1 成本约束模型与求解思路
•     4.1.1 成本约束模型
•     4.1.2 求解思路
•   4.2 基于三种典型倾向性瓦解策略的瓦解效果
•     4.2.1 模型网络实验结果
•     4.2.2 实证网络实验结果
•     4.2.3 平均策略的精确性验证
•   4.3 基于遗传算法的成本约束条件下复杂网络最优瓦解策略
•     4.3.1 遗传算法的基本概念
•     4.3.2 基于遗传算法的成本约束条件下最优瓦解策略算法流程
•     4.3.3 实验结果
•   4.4 本章小结
• 第五章 面向空间网络的最优瓦解策略研究
•   5.1 基于瓦解圆模型和空间分割机制的空间网络瓦解策略优化模型
•     5.1.1 基于爆炸超压的瓦解圆模型
•     5.1.2 基于笛卡尔网格的空间分割机制
•   5.2 空间网络最优瓦解策略求解算法
•     5.2.1 初始解优化准则和选择算子
•     5.2.2 空间网络最优瓦解策略的求解算法
•   5.3 空间网络瓦解策略的实验结果
•     5.3.1 数据描述与背景意义
•     5.3.2 辅助指标
•     5.3.3 实验结果
•   5.4 本章小结
• 第六章 总结与展望
•   6.1 论文主要工作
•   6.2 未来工作展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果

文章来源

类型: 博士论文

作者: 邓烨

导师: 谭跃进

关键词: 复杂网络,瓦解问题,中心性指标,启发式算法,成本约束,倾向性策略,遗传算法,空间网络

来源: 国防科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 国防科技大学

基金: 国家自然科学基金重大项目“互联网与大数据环境下高端装备制造创新研制任务集成管理”,国家自然科学基金项目“基于节点信息伪装的复杂网络抗毁性增强方法研究”,985重点建设经费“基于复杂网络的XXXX体系描述建模与优化方法研究”,国防科大科研计划“复杂网络结构鲁棒性及攻防对抗分析研究”

分类号: O157.5;TP18

DOI: 10.27052/d.cnki.gzjgu.2019.000075

总页数: 135

文件大小: 22171k

下载量: 1