基于复杂网络理论的平面网络抗毁性测度研究

发布时间：2017-04-01 17:14

  本文关键词：基于复杂网络理论的平面网络抗毁性测度研究，由笔耕文化传播整理发布。

【摘要】：随着信息技术的快速发展,人类生活在越来越多的复杂网络中,比如社会网络、交通网络、电力网络、技术网络、通信网络等.面临复杂且多样的各类网络,人们最为关心的问题是：我们赖以生存的网络到底有多可靠?当网络遭受一个微不足道的事故时网络的抗毁能力如何?事故发生后又如何快速的重建网络?这些问题正是复杂网络抗毁性的核心研究内容.本文基于复杂网络理论、图理论、统计物理、数理统计、计算机仿真等多学科领域知识,围绕着如何度量网络的抗毁性和如何建立最优抗毁网络模型两个问题,系统并深入研究了典型的平面网络的抗毁性测度和最优抗毁性平面网络.主要内容如下：(1)基于边失效策略,研究了网络抗毁性测度-网络生成树数目.网络生成树数目影响着网络的通信能力.当边攻击概率比较大时,网络生成树数目越多网络越可靠,从而网络抗毁性也越强.本文提出了计算平面2-树网络生成树数目的线性算法,其算法复杂度为O(n)低于矩阵树定理的算法复杂度O(n2),其中n为网络演化时间步.同时对算法进行了推广提出了一类平面2-连通网络生成树数目的线性算法,并利用算法确定了平面2-连通网络中具有相同节点数和边数的τ-优图.(2)基于边失效策略,研究了网络抗毁性测度-可靠度.假设网络G,G'∈Q(n,e),且网络中各边失效是相互独立的并具有相同的概率q(0≤q≤1),网络G的可靠度用Re(G,q)表示.当0≤q≤1时,若存在Re(G,q)≥Re(G',q),即网络G的连通概率比G'更大,则网络G比G'的抗毁性更强.本文提出了一类平面2-连通网络可靠度计算的线性算法,并利用算法确定了网络中的一致最优可靠网络和一致最差可靠网络的结构.(3)基于点边同时失效策略,提出并研究了网络抗毁性测度-混合可靠度和子树数目.对给定网络G∈ΩQ(n,e),假定每个节点失效概率为p,每条边失效概率为q,且节点和边失效总假定是相互独立的,称R(G;p,q)为点边失效下的混合可靠度.本文首先给出了网络混合可靠度的计算算法并明确了混合可靠度与子树数目的关系：如果p→O,q→1,p+g=1且F(G)F(G'),则R(G;p,q)R(G';p,q),其中F(G)表示网络G的子树数目.网络子树数目越多,网络的混合可靠度越大,则网络抗毁性也越强.其次给出了树图的混合可靠度的多项式算法,并确定了树图中的混合最优网络和混合最差网络结构.最后提出了子树数目计算算法,并利用算法确定了一类树型网络的子树数目.(4)基于节点失效策略,结合计算机仿真利用其他测度-剩余连通分支和平均路径长度分析了不同网络的抗毁性.
【关键词】：平面网络 抗毁性测度 生成树 子树 混合可靠度
【学位授予单位】：陕西师范大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-5
• Abstract5-12
• 第一章 前言12-30
• 1.1 研究背景及意义12-17
• 1.1.1 复杂网络研究背景及意义12-14
• 1.1.2 复杂网络抗毁性研究背景及意义14-17
• 1.2 国内外研究现状17-26
• 1.2.1 复杂网络研究现状17-22
• 1.2.2 复杂网络抗毁性研究现状22-26
• 1.3 本文的主要研究工作26-30
• 1.3.1 研究内容26-27
• 1.3.2 主要创新点27-30
• 第二章 基础知识30-38
• 2.1 图与网络30-32
• 2.1.1 图30
• 2.1.2 完全图30
• 2.1.3 子图30-31
• 2.1.4 平面图与外平面图31-32
• 2.2 图的基本概念32-34
• 2.2.1 路和连通32
• 2.2.2 树32-33
• 2.2.3 图的矩阵表示33-34
• 2.3 典型的平面网络模型34-38
• 第三章 平面网络生成树数目与抗毁性38-64
• 3.1 引言38
• 3.2 生成树数目与抗毁性38-40
• 3.2.1 生成树数目与网络抗毁性的关系38-39
• 3.2.2 生成树数目的研究39-40
• 3.3 平面2-树网络生成树数目的枚举40-53
• 3.3.1 平面2-树网络40-41
• 3.3.2 生成树数目算法描述41-43
• 3.3.3 平面2-树网络生成树数目上下界43-48
• 3.3.4 算法的应用48-53
• 3.4 算法推广及应用53-63
• 3.4.1 算法推广53-55
• 3.4.2 平面2-连通网络C(t)的生成树数目55-59
• 3.4.3 一类外平面网络的生成树枚举59-63
• 3.5 本章小结63-64
• 第四章 平面网络的可靠度与抗毁性64-82
• 4.1 引言64
• 4.2 靠度与网络抗毁性的关系64-65
• 4.3 平面2-树网络的可靠度65-73
• 4.3.1 模型算法65
• 4.3.2 可靠度的算法描述65-67
• 4.3.3 平面2-树网络可靠度的上下界67-72
• 4.3.4 仿真72-73
• 4.4 算法推广及应用73-81
• 4.4.1 模型算法73-74
• 4.4.2 可靠度算法描述74-75
• 4.4.3 平面2-连通网络C(t)可靠度的上下界75-81
• 4.5 本章小结81-82
• 第五章 子树数目与抗毁性82-108
• 5.1 引言82
• 5.2 网络混合可靠度82-89
• 5.2.1 树的混合可靠度85-88
• 5.2.2 混合最优树图和混合最差树图88-89
• 5.3 子树数目与网络的抗毁性89-91
• 5.4 子树数目计算算法91-93
• 5.5 直径为3和4的子树数目93-99
• 5.6 直径为5的子树数目99-106
• 5.7 小结106-108
• 第六章 不同网络抗毁性分析108-120
• 6.1 引言108
• 6.2 预备知识108
• 6.2.1 推广的平均路径长度108
• 6.2.2 剩余巨大连通分支108
• 6.3 网络抗毁性建模108-111
• 6.3.1 模型算法109-110
• 6.3.2 拓扑分析110-111
• 6.4 网络抗毁性分析111-117
• 6.4.1 基于不同节点失效策略之下网络抗毁性分析111-114
• 6.4.2 基于同一种节点攻击策略之下的网络抗毁性分析114-117
• 6.5 本章小结117-120
• 第七章 结束语120-122
• 7.1 论文主要工作120-121
• 7.2 进一步研究的工作121-122
• 参考文献122-134
• 致谢134-136
• 攻读博士学位期间的研究成果136

  本文关键词：基于复杂网络理论的平面网络抗毁性测度研究，由笔耕文化传播整理发布。

，

本文编号：280998