当前位置:首页  >  博士论文

博士论文范文论文题目:基于超图的小世界超网络模型及传播特性分析

时间:2022-05-21来源:博士论文

随着复杂系统以及复杂性科学的迅速发展,网络科学作为一门新兴的多领域 交叉型学科,引起了各个领域内专家学者们的广泛关注。小世界特性因能准确地 描述真实网络的实际情况而成为了研究热点之一。然而,具有多维、多属性、复 杂性、节点规模庞大等特性的真实网络在不断发展,小世界网络的拓扑结构及其 自身性质也在不断变化,且难以通过传统的复杂网络进行刻画。因此,基于超图 的超网络应运而生,超图中的超边可包含任意数量的节点,能够准确地表示真实 网络中各种复杂多变的多维关系。本文综合运用复杂网络、超图理论、随机过程 等相关理论,以基于超图的超网络为主要研究对象,对小世界超网络模型及传播 动力学机制进行研究。具体研究内容如下: 1. 构造了小世界超网络模型并研究其小世界特性。本文以规则超网络为基 础,依据超边组成以及超边数量的不同取值,提出并构建了基于超边随机重连和 超边随机增加的小世界超网络模型。通过仿真实验,分析两种超网络模型的小世 界特性,并构建等价随机超网络验证其小世界特性。 2. 研究了小世界超网络上的传播动力学。本文用小世界超网络模型描述个 体社交关系,结合传播动力学中的 SIR 模型,构建两种小世界超网络上的信息传 播模型,并仿真实验分析超网络结构参数、传播参数、演变概率等因素对信息扩 散速度和稳态结果的影响,从宏观的角度揭示了信息在社交网络中的传播规律。 3. 分析了实证超网络的特性。本文分别选取社交网络、传染病网络、合作 网络典型领域的真实数据,结合超图理论构建不同类型的实证超网络,定量分析 超网络的拓扑属性,探讨其小世界特性以及信息传播规律,通过构建等价随机超 网络验证实证超网络的小世界特性,分析影响实证超网络信息传播的因素,进而 深入理解各类社会网络。 综上,论文首先从理论层面提出了小世界超网络的核心思想及构造算法;其 次,构建小世界超网络上的传播动力学模型,刻画现实超网络的信息传播规律; 最后,对真实网络进行实证研究,探索不同领域网络的拓扑结构特征。本文的研 究有助于为今后研究超网络中的小世界特性及拓扑结构提供一定的借鉴及参考
超图,超网络,小世界,实证超网络,传播动力学,博士论文范文

博士论文范文论文题目:基于超图的小世界超网络模型及传播特性分析

中文摘要
.........................................................................................................................IAbstract..........................................................................................................................II第一章 绪论..................................................................................................................1

1.1 研究背景和意义..............................................................................................1

1.2 超网络研究现状..............................................................................................2

1.3 小世界理论研究现状......................................................................................3

1.4 本文创新点......................................................................................................4

1.5 本文组织结构..................................................................................................5

第二章 基础知识..........................................................................................................6

2.1 超图的基本概念..............................................................................................6 2.1.1 超图的定义............................................................................................6 2.1.2 超图的表示............................................................................................7

2.2 超图的拓扑性质..............................................................................................7 2.2.1 超图的关联矩阵和邻接矩阵................................................................7 2.2.2 节点超度及节点度................................................................................8 2.2.3 聚集系数................................................................................................9 2.2.4 平均路径长度...................................................................................... 11

2.3 复杂网络经典模型........................................................................................ 11 2.3.1 规则网络.............................................................................................. 11 2.3.2 随机网络.............................................................................................. 11 2.3.3 小世界网络..........................................................................................12

2.4 超网络经典模型............................................................................................14

2.5 传播动力学理论基础....................................................................................16

2.6 小结................................................................................................................17

第三章 基于超图的小世界超网络模型....................................................................18

3.1 概述................................................................................................................18

3.2 基于超图的最近邻耦合超网络模型............................................................18 3.2.1 模型构建..............................................................................................18 3.2.2 仿真实验及结果分析..........................................................................19

3.3 基于超边随机重连的小世界超网络模型....................................................21 3.3.1 模型构建..............................................................................................21 3.3.2 仿真实验及结果分析..........................................................................21

3.4 基于超边随机增加的小世界超网络模型....................................................24 3.4.1 模型构建..............................................................................................24 3.4.2 仿真实验及结果分析..........................................................................24

3.5 小世界特性对比分析....................................................................................27

3.5.1 小世界超网络模型与无标度超网络模型对比分析..........................27

3.5.2 超边随机重连小世界超网络与 WS 小世界网络对比分析..............29

3.5.3 超边随机增加小世界超网络与 NW 小世界网络对比分析............. 30

 3.6 小结................................................................................................................32第四章 小世界超网络中的传播动力学模型............................................................33

4.1 概述................................................................................................................33

4.2 基于超网络结构的 SIR 模型信息传播过程................................................33

IV


 4.3 最近邻耦合超网络上的 SIR 信息传播模型................................................35 4.4 超边随机重连小世界超网络上的 SIR 信息传播模型................................37 4.4.1 超网络结构与传播参数对信息传播的影响......................................37 4.4.2 超网络和复杂网络结构下信息传播的对比分析..............................41 4.5 超边随机增加小世界超网络上的 SIR 信息传播模型................................42 4.5.1 超网络结构与传播参数对信息传播的影响......................................42 4.5.2 超网络和复杂网络结构下信息传播的对比分析..............................45 4.6 小世界特性对信息传播的影响....................................................................46 4.6.1 聚集系数与信息传播的关系..............................................................46 4.6.2 平均路径长度与信息传播的关系......................................................47 4.7 小结................................................................................................................48第五章 实证超网络特性分析....................................................................................49 5.1 概述................................................................................................................49 5.2 Facebook 电视节目超网络实证分析............................................................ 49 5.2.1 研究背景及数据来源..........................................................................49 5.2.2 超网络构造算法..................................................................................50 5.2.3 实证结果分析......................................................................................50 5.3 都柏林模拟传染病超网络实证分析............................................................53 5.3.1 研究背景及数据来源..........................................................................53 5.3.2 超网络构造算法..................................................................................53 5.3.3 实证结果分析......................................................................................54 5.4 科研合作超网络实证分析............................................................................56 5.4.1 研究背景及数据来源..........................................................................56 5.4.2 超网络构造算法..................................................................................57 5.4.3 实证结果分析......................................................................................57 5.5 实证超网络特性分析....................................................................................60 5.5.1 实证超网络小世界特性对比分析......................................................60 5.5.2 实证超网络传播特性对比分析..........................................................60 5.6 小结................................................................................................................61第六章 总结与展望....................................................................................................62 6.1 总结................................................................................................................62 6.2 展望................................................................................................................63参考文献......................................................................................................................65致谢..............................................................................................................................70附录一 个人简介........................................................................................................71附录二 作者攻读硕士学位期间参与的科研项目....................................................72附录三 作者攻读硕士学位期间完成和发表的论文................................................73

1.1 研究背景和意义
复杂网络是刻画复杂系统的有力工具,其研究热潮自出现开始便居高不下
[1-4]。复杂网络以普通图作为拓扑结构,网络中的节点表示研究对象,网络中的
连边表示节点间的关系,从现实网络的特性出发,依据真实数据集构建复杂网络,
计算网络的各项拓扑参数,以此分析现实网络所表现出的现象,最终结果反馈至
网络,用于刻画出复杂系统的共性特征。例如,众所周知的“六度分离”理论便
可由具有小世界特性的 WS 模型来描述[5],而“富者越富,穷者越穷”的马太效
应则可通过具有无标度特性的 BA 模型进行刻画[6]。在这两类经典模型提出之后,
诸多专家学者们开始对复杂网络有所关注,在经历了长足的发展研究后,复杂网络
在生物、数学、计算机等领域内取得了非常多的研究成果[7-11]。其中,小世界理论
是复杂网络中极其重要的理论以及热门研究之一,真实世界中的大多数网络几乎都
具有小世界特性,随着互联网的迅速普及,越来越多的个体将被连接的世界包围,
人与人之间的联系越来越密切,社会距离越来越近,小世界特性在真实网络中的体
现日益显著。因此,对网络中小世界特性形成原理、信息扩散过程以及实证分析
等问题的研究,能帮助人们更好地理解社会网络的构成、演化以及对人类社会的
影响,解释现实世界中各种复杂的自然现象,为解决现实世界中出现的各类问题
提供理论指导及决策建议。
随着网络规模的不断扩大以及科技的进步,现实世界中的各种网络规模得到
了空前的提升,节点间连接关系更加多元化,基于普通图的复杂网络已经无法很
好的描述真实网络的所有特征,如现实中任何一个项目或任务都不是一个人能够
完成的,人与人之间的合作关系变得错综复杂,在普通图中的一条边只能表示同
质节点之间的合作关系,但是很难描述多人之间的复杂合作关系。因此,专家学
者开始尝试利用基于超图的超网络解决上述问题。无论是普通网络还是超网络,
研究小世界特性都是网络模型分析和复杂系统科学领域值得研究的问题。
在现实生活中,人们通常都在微信群、家族或社会团体中以多对多的方式发
布信息,特别是新冠病毒肺炎的爆发具有明显的家族式、社区式及地域式的传播
特点,各种信息、谣言也在不同的团体中被转发。病毒和谣言不断的在社区中传
播,从几十到几百个,最终导致新冠病毒指数式呈增长,并迅速蔓延至全球。在
这种情况下,基于普通图的复杂网络并不能完全描述人类群居社会的全部真实活
动及网络特性,如果用传统的简单图或有向图的方法来处理这类问题,网络中的
很多关键信息如传播途径、传播速度以及超级传播者等都可能会被丢失。超图中
的超边可包含任意多个节点之间的关系,可看作是一个家族或一个社区。因此,
1
青海师范大学硕士学位论文
基于超图理论的超网络能更好地刻画网络的诸多细节(例如节点、关系),能更准
确、全面地描述真实网络的所有特性。对比复杂网络,网络中节点之间的连接能
够形成小世界效应,而在超网络中节点同样能够通过超边联系在一起,表现小世
界特性,不仅能够表示节点之间的关系强弱,还能够表示关系圈之间的联系程度。
因此,基于超图的超网络研究对现实网络的研究意义更大、影响更深远。
小世界理论自诞生以来就受到了各个领域专家学者的重点关注[12-18],如病毒
传播、生物学、知识流动、网络信息传播等问题上都涉及到了小世界现象。超网
络的小世界特性研究不仅用超网络的角度重现和刻画了真实系统中的小世界现
象,而且为帮助人们理解从局部特性发现系统整体结构提供了新方法,在理论层
面以及实际应用中具有至关重要的作用。例如,在脑神经网络“生物经济性”假
说中,每个神经元只与其最近邻的神经元联系,在减少神经元材料消耗的同时,
使整个网络联通且网络半径较短,体现了小世界效应在生物进化中的优势;在具
有小世界特性的超网络系统模型中,信号能够更快地传播,计算能力得到一定程
度的提升。除了在理论层面的重大意义,小世界超网络的研究在实际应用中也极
具价值。例如,利用小世界超网络模型的快速传播能力和高聚类特性,可以更有
效地搭建点对点网络,提高资源有序管理的性能,使信息得以有序、高效地被存
储以及检索;通过小世界超网络模型创建规模较小且半独立的社交运动团体,仅
通过少量人员即可使信息或指令在团体之间快速、广泛地传达,使其具有较强的
抗毁性能力;将小世界超网络与区块链结合,可大大提高区块链对抗网络攻击的
安全性等。
1.2 超网络研究现状
“超网络”是指具有网络规模巨大、网络内部连接复杂等特点的网络。目前,
超网络的定义共有两种。第一类超网络 Supernetwork,其概念最早由 Denning 提
出[19],以网络结构梳理及多层次网络的建模问题为重点,为分析大规模系统各组
成部分之间的关系及实际问题的解决提供了新方法[20],目前已广泛应用于物流网
络、社交网络以及供应链网络中[21-23]。而 Hypernetwork 这类超网络,则是 Estrada
及 Rodrgíuez 给出的超网络定义[24-25],可以用超图表示的网络就是超网络。超图
理论在各个领域都有十分广泛的应用,超图中的超边概念使得超图能够使任意数
量、任意属性的节点之间产生联系,所以它具有描述多元关系的能力,解决了复
杂网络难以描述多元复杂关系的问题,如在食物竞争网络中利用超图能清晰地刻
画出多个捕食者之间的竞争关系,传染病网络中的传播范围也能利用超图清晰地
描述。现如今,真实网络不仅在整体的组成规模上超出传统网络数倍,且内部节
点关系错综交织,如包含成百上千万的节点数,节点之间的关系呈现出多维的特
2
基于超图的小世界超网络模型及传播特性分析
点,简单的复杂网络结构不能够解决此类问题,而基于超图的超网络能够轻松应
对,更加契合真实网络的实际情况。
近年来,基于超图结构的超网络研究在模型构建及真实世界中的超网络特性
分析上取得了较好的成果[26-35]。Hu 等[30]构造了三种超网络动态演化模型,用不
同的参数值对每种模型进行了数值模拟,其仿真结果与理论分析结果一致,有助
于理解实际系统的结构和演化机制;Arruda 等[31]研究了超图上的社会传染动力
学,为高阶结构动力学过程的建模铺平了道路;Zhang 等[32]提出了一种基于超图
的社会化标签网络模型,该模型有助于深入理解大众分类法的结构和功能;巩等
[33]以无标度超网络动态演化模型为基础,构建了在线社交网络的信息全局传播模
型,并分析在线社交超网络中信息传播规律及发展趋势;王等[34]针对舆论演化过
程中的复杂动力学问题,提出了超网络视觉下的舆论演化动态模型;卢等[35]构建
了双层超网络模型,能更准确有效地描述现实生活中的多层、异质关系。
本文的研究主要关注于 Hypernetwork 这类超网络,不同学科领域的专家学
者对于超网络的发展前景十分关注,尚有较大的研究空间。目前,利用复杂网络
和超网络的特性分析和模型构建方法研究大规模系统数据还是一个有效地科学
方法,能够描述真实系统的内在本质。超网络与复杂网络之间在特征方面存在一
定的相似之处,但也存在本质差异,因此,探究超网络结构下的各种特性及演化
模型,挖掘潜在的本质,是值得研究的方向。
1.3 小世界理论研究现状
小世界理论,又称为六度分离理论,指任何两个素不相识的人,通过一定的
方式,总能够产生必然联系或关系。随着科技的不断发展与进步,小世界理论在
社会学、生物学等不同学科领域都已发挥重要作用。WS 模型提出后,各领域专
家学者纷纷投入对小世界特性的研究,实证结果表明,大多数真实网络几乎都具
有小世界效应,如学术圈的建立及扩大、人际网络的发展等。随着社会信息化的
不断发展,小世界效应会更加显著,未来的每一个人都将以各种方式联系在一起。
到目前为止,人们根据现实中实际问题以及理论上的猜想,利用复杂网络理
论进一步研究小世界特性或将小世界特性应用于各领域内的研究工作。成[36]提出
一种用小世界粒子群算法优化图像检索中的相关反馈过程的方法,结果表明该方
法可以使用较少的迭代次数,检索到更多的相关图像;任等[37]提出一种基于弹性
小世界回声状态网络的非线性时间序列预测方法,仿真实验结果表明,该方法相
比常规方法稳定性更好且预测精度更高;柳等[38]基于混合模式构造了具有小世界
特征的无线传感器网络,仿真分析结果表明该无线传感器网络具有更长的生命周
期和更好的网络运行有效性;袁等[39]提出了基于小世界算法的机械手时间最优运
3
青海师范大学硕士学位论文
动规划,仿真测试结果表明,小世界算法使得机械手规划模型表现出较好的收敛
性和稳定性;文献[40]提出一种新的变异-免疫模型,详细分析了小世界网络的规
模、协调数和无序参数对疫情传播的影响,结果表明,小世界网络的结构和病毒
变异周期对疫情的传播有重要影响;吕等[41]构造了一种择优选择小世界网络模
型,在该模型的基础上研究了复杂网络中各种因子对同步性能的影响,仿真结果
表明,网络中节点的最大介数能表征网络同步能力;石等[42]提出并构建关于大学
生危机行为传播的小世界网络模型,结果表明小世界效应越强的网络,危机行为
传播越快;刘等[43]通过语料库建立了与单词共现网络相似的汉语词网络,对该网
络进行了系统的实验分析,实验结果表明该网络具有高聚集、低平均路径长度的
特征,具有小世界特性;张等[44]以 SARS 疫情为例,拟合分析疾病传播趋势,拟
合结果与实际数据基本吻合,证明利用小世界网络分析流行性疾病的可靠性;邓
等[45]在交流网络的分析中,提出将聚集系数和平均路径长度转化为团队交流网络
中交流集中度和交流频率的思想;刘等[46]通过检索 Web of Science 的文献数据构
建合作网络,研究了网络小世界特征与科研绩效之间的关系,结果表明两者之间
呈线性正相关关系。
迄今为止针对具有小世界特性的超网络研究较少,Wang 等[47]提出了一种超
边增长和超度优先连接机制的无标度超网络演化模型,并研究了该模型的小世界
特性。本文首先针对超网络中的小世界特性进行研究,以一类规则超网络为基础,
利用超边随机重连和超边随机增加的方法,构建了两种基于超图的小世界超网络
模型,对超网络模型上的小世界效应进行分析。其次,采用小世界超网络模型构
建社交超网络,建立了两种小世界超网络结构上的信息传播模型,研究小世界超
网络上的传播动力学。最后,选取三个不同领域内的真实网络数据集,结合超图
理论分析实证超网络的小世界特性和传播机制。
1.4 本文创新点
本文主要针对超网络上的小世界特性和传播规律进行研究,构建了两种小世
界超网络模型;借鉴经典的传播模型为理论基础,分析了小世界超网络结构上的
传播动力学行为;对现实中的超网络进行实证分析,探讨真实超网络的小世界特
性和传播机制。
本文的创新点主要有以下三个方面:
(1) 本文以最近邻耦合超网络模型为基础,构建了基于超边随机重连和基于
超边随机增加的小世界超网络模型,通过仿真实验分析两类超网络模型的小世界
特性,并与经典的超网络模型和复杂网络的小世界模型进行对比分析。
(2) 本文以小世界超网络结构刻画社交超网络,结合传播动力学中的 SIR 模
4
基于超图的小世界超网络模型及传播特性分析
型,分析信息在社交超网络中的扩散过程,探讨了结构参数、传播率等对信息传
播的影响,并对比了信息在超网络与复杂网络中的传播过程。
(3) 本文结合超图理论构建了 Facebook 电视节目超网络、都柏林模拟传染病
超网络和科研合作超网络三类实证超网络,选取多个指标分析网络的拓扑结构特
征,通过构建等价随机超网络验证其小世界特性,并在实证超网络上模拟信息传
播过程。
1.5 本文组织结构
全文共分为六个章节,具体论文组织架构安排如下:
第一章 绪论
本章主要归纳总结了复杂网络及超网络的研究背景及研究现状,概述了小世
界理论研究现状,介绍了本文的创新点,最后梳理了本文的组织结构。
第二章 基础知识
本章对超图、超网络和传播动力学理论的基础知识进行了详细介绍,主要介
绍了超图和超网络的基本概念及拓扑性质,最后介绍了几种典型的复杂网络模
型、超网络模型以及传播动力学模型,为后文分析奠定理论基础。
第三章 基于超图的小世界超网络模型
本章首先以一类最近邻耦合超网络为基础,结合小世界理论,提出超边随机
重连和超边随机增加两种方法,构建小世界超网络模型,通过仿真实验分析超网
络模型的特性,并以等价随机超网络对其小世界特性进行量化及验证。最后,将
两种小世界超网络模型与经典的超网络演化模型以及复杂网络中的小世界网络
模型进行对比。
第四章 小世界超网络中的传播动力学模型
本章在考虑真实社交关系特征的前提下,基于传播动力学理论,讨论信息在
不同小世界超网络结构下的传播规律,通过仿真实验分析影响信息传播的因素,
并将信息在超网络和复杂网络上的传播过程进行对比,揭示小世界超网络结构下
的信息传播规律及趋势。
第五章 实证超网络特性分析
本章从真实系统出发,分别选取社交网络、传染病网络和合作网络的实证数
据,构建实证超网络,计算超网络拓扑指标,结合实证结果及等价随机超网络,
验证实证超网络的小世界特性,分析信息在不同超网络结构中的传播过程,归纳
总结不同实证超网络的拓扑性质和规律。
第六章 总结与展望
本章对全文的研究工作做总结,并对未来进一步的研究工作进行展望。
5
青海师范大学硕士学位论文
第二章 基础知识
2.1 超图的基本概念
由若干个给定的节点以及连接节点对的边所构成的图形称为图,通常用来描
述事物之间的特定关系,其中节点代表事物,连接节点对的边表示相应的特定关
系。称二元组 G=(V, E)是图,其中V 称为图G 的顶点集,E 称为图G 各节点的边
集。超图是图的一种推广,普通图的一条边最多连接图中的两个节点,超图中一
条超边里面的节点不受数量的限制,可使任意数量的、任意属性的节点之间产生
关联,而不仅仅是两个节点,在本质上与复杂网络中的边有所不同,复杂网络中
的边可视为超边中只有两个节点的特例。普通图和超图的示例如图 2-1 所示。
(a) 普通图 (b) 超图
图 2-1 普通图和超图的示例
2.1.1 超图的定义
1973 年,Berge 最早定义了超图[48]。定义如下:设有限集合 { 1,v ,...,vn}
V  v ,
2
若满足以下条件:
1 Ei  (i 1,2,...,e)
e
2 Ei V
i1
则称二元关系 H=(V, E)为超图,集合 V 中的元素
v1,v ,...,v 表示超图的节点,
2 n
|V|表示节点的个数; { 1, E ,..., Ee}
E  E ,E 为超图中所有超边集合,其中的元素
2
Ei {vi ,v v }(1 j  n)
 ,..., 称作超边,|E|表示超边的个数。
i i 1 2 j
6
基于超图的小世界超网络模型及传播特性分析
2.1.2 超图的表示
超图的表示方法与普通图相同,以图形的形式进行表示,特别地,当超图中
的超边仅包含 2 个节点时,超图退变为普通图。图 2-2 为超图实例,包含 6 个节
点和 2 条超边。
图 2-2 超图 H
在 图 2-2 中 超 图 H=(V, E) , 其 中 节 点 { 1,v ,v ,v ,v ,v }
V  v , 超 边 集
2 3 4 5 6
E = {E ,E },其中
1 2 E = v v v ,
1 { 1, 2 , 4} E2 = {v2 ,v3,v4 ,v5 ,v6}。
2.2 超图的拓扑性质
2.2.1 超图的关联矩阵和邻接矩阵
(1) 超图关联矩阵
超图通过其关联矩阵 C=(cij)M×N 可以唯一表示[49],其中 cij 是关联矩阵 C 中
的元素, M 代表超图的超边总数, N 代表超图的节点总数。设 H 是一个超图,
若关联矩阵满足以下条件:
1 C 中的每一行与 H 的节点有关;
2 C 中的每一列与 H 的超边有关;
3 如果节点 vj 包含在超边 ei 中,则 Cij=1。
则矩阵 C 为超图 H 的关联矩阵。如图 2-2 超图 H 的关联矩阵 C 为:
e
1 e
2
C v
1
v
2
v
3
v
4
v
5
v
6








1
1
0
1
0
0 0
1
1
1
1
1









7
青海师范大学硕士学位论文
(2) 超图邻接矩阵
超图的邻接矩阵 A=(aij)N×N 表示超图中的节点之间邻接关系[49],其中 aij 是 A
中 i 行 j 列的元素。邻接矩阵 A 是 N 阶对称矩阵,通过邻接矩阵能够计算聚集系
数、平均路径长度、节点度等拓扑参数。设 H 是一个超图,若邻接矩阵满足以
下条件:
1 A 中的行与 H 的节点相关;
2 A 中的列与 H 的节点相关;
3 A 中元素 aij 为包含节点 vi 与节点 vj 的超边数量,主对角线元素为 0。
则矩阵 A 为超图 H 的邻接矩阵。如图 2-2 中超图 H 的邻接矩阵 A 为:
v
1 v
2 v
3 v
4 v
5 v
6
A v
1
v
2
v
3
v
4
v
5
v
6

0
1

 0



1
 0


 0
1
0
1
1
1
1 0
1
0
1
1
1 1
1
1
0
1
1 0
1
1
1
0
1 0

1
1



1
 
1


0

2.2.2 节点超度及节点度
(1) 节点超度
在超图中,节点 vi 的超度 dH(vi)被定义为包含节点 vi 的超边总数[47]。通常情
形下,节点的超度是判断关键节点的重要参数之一,同时也是分析真实网络的重
要指标之一,超度越大的节点影响力越大,以这种节点作为信息传播源可以使信
息传播的范围更广。节点 vi 的超度可通过关联矩阵 C=(cij)M×N 计算:
m

d (  (2-1)
H v ) c
i ij
j1
节点的超度分布 P(d ) 为超度为 dH 的节点占节点总数的比例,即:
H
N
d
P
(dH )  (2-2)
H
N
其中 N 表示超度为 dH(vi)的节点数。
d
H
平均超度指超图中所有节点超度的平均值[50-51],能够在一定程度上描述超图
的本质,记为 d ,即
H
1
N


H d (v )
H i
N
i1 (2-3)
8
基于超图的小世界超网络模型及传播特性分析
(2) 节点度
普通图中节点 vi 的度 ki 指该节点的连边数目[26-27]。在超图中,节点 vi 的节点
度 d(vi)指超图中同一条超边内的所有节点全连接,节点全连接后形成全连接图,
超图的节点度等同于全连接图中的节点度,即节点之间的连边数。若节点被不同
超边包围,则该节点与所属的超边内的其他所有节点全连接。节点之间的联系能
够通过邻接矩阵中的元素值进行表述,即
n n
  d i )  a a
(v  (2-4)
ij ji j1 i1
通过邻接矩阵 A 能够获得超网络的度分布,节点度分布概率 P(k ) 的计算公
i
式为:
N
P( i )  i (2-5)
k
N
其中 Ni 表示度为 ki 的节点数。通过对平均度的计算能够衡量整体网络节点
的活跃程度,越低说明节点之间交互较少,反之则联系更多。
2.2.3 聚集系数
聚集系数能够描述在超网络中节点之间的联系程度的强弱,也可以认为是至
少被两条超边包含的节点参与形成超三角形的比例。聚集系数的值是辨别超网络
是否具有小世界现象的条件之一,聚集系数越大则代表超网络中的超三角形在所
有二元组中的比例越高,超网络节点之间的联系就越紧密。本文主要计算整个超
网络的平均聚集系数,以期对整个网络的拓扑特性进行分析。在文献[24]中,
Estrada 等人明确定义了超网络的聚集系数及其计算方法,即

N
3
6t
C  1
s s
H   u t
N N
(( ) 1) 6
2 2
s j is s
1 1 (2-6)
其中
 是超网络对应邻接矩阵 A 的特征值,用于计算闭迹的长度,指数的
s
值代表计算长度为 s 的闭迹的个数,U=(uij)是正交矩阵,其中每一列 uij 表示 对
s
应的特征向量,用来与特征值一起计算长度为 s 的迹的个数。其中 t 代表超网络
H 中伪超三角形的个数。当所有节点来自于同一条超边时,尽管闭迹长度达到了
3,但是不能被称为超三角形,被称为伪超三角形[24]。伪超三角形计算方式如下:
t m

( 1) j a (2-7)
 1

j
j1
9
青海师范大学硕士学位论文
上式中,aj 表示 j 条超边中伪三角形的个数,其计算公式为:
a
j
 
i ,i ,...,i
1 2 k
3

i ,i ,...,i
1 2 k
 表示超边集合{E


i1, Ei2,..., Eik}的交集中节点的个数。
 i1 ,i2 ,...,i
k

此外,Estrada 等给出了基于传递学的聚集系数[24],即 transitivity coefficient。
计算方法如下:
6*超三角形个数
C  (2-8)
H
迹长度为2的数量
超三角形被定义为以下列形式组成的序列: A E1 v E v E v ,3 个完全
v , , , , , ,
B 2 C 3 A
不同的节点通过超边相互毗邻,超三角形示例图如图 2-3 所示。每个超三角形贡
献了三条长度为 2 的迹,迹总长度为 6,CH=1。
图 2-3 超三角形
竞争超网络是一种捕食者之间进行竞争的超网络,捕食者用节点表示,被捕
食者用超边表示,在同一条超边内的所有节点互相之间都被视为竞争关系,竞争
超网络如图 2-4 所示。由图 2-4 可知,该超网络中存在 2 个超三角形,分别是由
节点 v2 ,v ,v 和 2 ,v ,v
v 构成,构成超三角形具体序列为
4 10 5 10 v 以
2 , E ,v , E ,v , E ,v
2 4 3 10 1 2
及v2 , E ,v , E ,v , E ,v ,且长度为 2 的迹数目为 48 个。利用公式 2-8 可知,该
2 5 3 10 1 2
超网络的平均聚集系数C  6*2/ 48  0.25 ,这表明至少被两条超边包含的节点
H
参与形成超三角形的概率为 25%。
图 2-4 竞争超网络
10
基于超图的小世界超网络模型及传播特性分析
2.2.4 平均路径长度
在超网络中,任意两个节点之间的距离 dij 指通过超边可达的两个节点的最
短路径上的超边数目[27],超网络的平均路径长度 L 指任意两个节点之间的平均
H
距离[32]。首先,构造超网络的距离矩阵 D=(dij)N×N,保存节点之间间隔的超边数
目,矩阵的阶数与节点总数 N 有关,为 N 阶方阵。平均路径长度的计算公式如
下:
2 N


H d
N(N 1)
 ij
i, j1 (2-9)
2.3 复杂网络经典模型
2.3.1 规则网络
常见的规则网络有全局耦合网络、最近邻耦合网络、星型耦合网络。全局耦
合网络在规模相同的情况下,平均路径长度最小且聚集系数最大,有小世界效应,
但不能作为实际网络模型。最近邻耦合网络中每个节点只与其少数邻居节点相
连,是被广泛研究的稀疏规则网络模型,在节点数较大时,其聚集系数C  3/ 4 ,
对于固定的最近邻节点数,平均路径长度会随网络规模无限增长,不可能兼具高
聚集系数和低平均路径长度,因此最近邻耦合网络不是小世界网络。星型耦合网
络只有一个中心节点,其余节点都只与中心节点相连。三种规则网络如图 2-5 所
示。
(a) 全局耦合网络 (b) 最近邻耦合网络 (c) 星形耦合网络
图 2-5 三种规则网络
2.3.2 随机网络
随机网络模型的构建方法主要有两种,一种是具有固定边数的随机网络,另
一种是具有固定连边概率的随机网络。
(1) 具有固定边数的随机网络构建方法:
1 初始化:给定 N 个节点,M 条待添加的边。
11
青海师范大学硕士学位论文
2 随机连边:随机选择一对没有连边的节点,为该节点对添加一条边,重
复此过程,直至添加 M 条边。
(2) 具有固定连边概率的随机网络构建方法:
1 初始化:给定 N 个节点,连边概率 p[ 0,1] 。
2 随机连边:随机选择一对没有连边的节点,生成一个随机数 r (0,1),若
r  p ,则在此节点对之间添加一条边,否则不加边;重复选取剩余的节点对,
直至所有节点对都被遍历过。
图 2-6 为在相同参数 N=10 和 p=1/6 时所产生的 3 个具有固定连边概率的随
机网络图。
图 2-6 三种随机图
2.3.3 小世界网络
在真实网络特性研究发展的过程中,小世界特性因为契合真实网络而深受专
家学者们的青睐。小世界现象是 Stanley Milgram 在进行社会学研究时提出的一
个概念,Milgram 注意到了现实世界中的网络节点之间的距离非常短,于是引入
了六度分离理论的概念,这种现象表明任何两个陌生人之间,在通过一定数量的
中间人联系后,总能够取得联系。Watts 和 Strogtz 于 1998 年提出了第一个小世
界网络模型[5],称为 WS 小世界网络模型,是复杂网络中最经典的模型之一。1999
年,Newman 和 Watts 对 WS 小世界网络模型进行改进[52],提出了 NW 小世界网
络模型。
(1) WS 小世界网络模型
模型构造步骤如下:
1 初始化:从规则图开始,考虑一个最近邻耦合网络,网络的节点数为 N ,
其中每个节点与左右各 K/2 邻居节点相连,满足 N>>K>>lnN>>1,K 为偶数。
2 随机化重连:以概率 p 随机重连网络中原有的每条边,任意节点对之间
至多有一条边,不得有重边和回环。WS 小世界网络模型演变过程如图 2-7 所示。
12
基于超图的小世界超网络模型及传播特性分析
图 2-7 WS 小世界网络模型演变过程(参见文献[5])
图 2-8 为不同随机重连概率 p 下 WS 网络模型的聚集系数C( p)及平均路径
长度 L( p)变化情况。由图 2-8 可知,p=0 时对应于最近邻耦合网络,p=1 时对应
于完全随机网络,重连概率 p 能够左右网络特性的变化。此外,概率 p 存在一个
范围,在此范围中,网络就明显表现出高聚集性和小世界性,形成小世界网络。
图 2-8 随机重连概率 p 下聚集系数、平均路径长度变化图(参见文献[5])
图 2-9 为不同随机重连概率 p 下 WS 网络模型的度分布情况,该模型中
N 1000, K  6。由图 2-9 可以发现,每一条曲线都服从泊松分布,且随着概率
p 的增大,不同概率 p 下的曲线峰值减小,曲线范围增大。
图 2-9 WS 小世界网络度分布
13
青海师范大学硕士学位论文
(2) NW 小世界网络模型
模型构造步骤如下:
1 初始化:从规则图开始,考虑一个最近邻耦合网络,网络的节点数为 N,
其中每个节点与左右各 K/2 个邻居节点相连,满足 N>>K>>lnN>>1,K 为偶数。
2 随机化加边:以概率 p 随机选取 NK/2 对节点,并在 NK/2 对节点之中添
加边,不得有重边和回环。NW 小世界网络模型构造过程如图 2-10 所示。
图 2-10 NW 小世界网络模型演变过程(参见文献[52])
图 2-11 为 NW 网络模型在不同加边概率 p 下的度分布情况,其中 N=1000,
K=6。由于对最近邻耦合网络进行加边而不是重新连接,因此该模型中每个节点
的度有最小值。从图 2-11 中可以观察到,随着概率 p 的增大,不同概率 p 下的
曲线峰值逐渐减小,曲线范围逐渐增大。
图 2-11 NW 小世界网络的度分布
2.4 超网络经典模型
愈发成熟的超图理论吸引了各个领域的专家学者,基于超图理论构建了种类
繁多且实用的超网络模型,对真实网络的各种特性进行分析研究。为了更加精确
地、切合实际地研究真实网络,人们提出了各种超网络演化模型的构造算法[28, 47],
Wang 等[47]根据无标度网络的生成机制,每个时间步添加 m 个新节点至现有超网
14
基于超图的小世界超网络模型及传播特性分析
络中,与现有超网络中的一个节点结合,组成一条新超边,在多个时间步后完成
超网络演化模型的构建,并对超网络模型的小世界特性进行了研究分析。文献[47]
的超网络演化模型构建步骤如下:
1 初始条件
超网络中有少量 m0 个节点,以及一条包含 m0 个初始节点的超边。
2 超边增长
每个时间步添加 m 个新节点至现有超网络中,与现有超网络中的一个节点
结合,组成一条新超边 E 。
3 超度优先连接
新节点与网络中的一个旧节点连接生成一条超边,旧节点 i 被选取的概率为
i d v 取决于节点 i 的超度 dH(vi),即
( ( ))
H i
d (v )
 ( (v )) H i (2-10)
d

i H i d j
( ) H
jN
其中,节点 vi 的超度 dH(vi)被定义为包含该节点的超边总数。t 时间步后,超
网络中有 m0  mt 节点, t 1条超边, ( ( 1) ( 1)) / 2
m0 m   tm m  条边。图 2-12 显
0
示了当 0  3,m  2
m 时超网络前四步的演化过程。
图 2-12 m0  3,m  2情况下的网络生成图(参见文献[47])
此外,在文献[47]中分析了相同超边数量下不同 m 值引起的指标变化。图
2-13 描述了 m 值分别为 2、4、6 时,不同超边数量情况下超网络聚集系数的变
化情况。m 为固定值时,m 的值越大,聚集系数越低,优先连接机制越不明显。
0
图 2-13 不同超边数量下超网络聚集系数变化示意图(参见文献[47])
15
青海师范大学硕士学位论文
图 2-14 为当 m  2 时不同超边数量 NE 下超网络平均路径长度的变化情况。
由图 2-14 可以观察到,平均路径长度与超边数量成正相关关系,超边数量越多,
平均路径长度越大。
图 2-14 不同超边数量下超网络平均路径长度变化示意图(参见文献[47])
2.5 传播动力学理论基础
网络传播动力学起源于人们对传染病的研究,首先以疾病的产生及传播规
律、种群的生长特性为根据,通过动力学方法建立符合实际情况的数学模型,研
究某种传染病是否会继续扩散传播或最终消除。最后通过对模型中的动力学过程
进行仿真分析和数值模拟,发现传染病的传播机理,预测传染病传播趋势,进而
制定预防和控制疾病的免疫及预防策略[53]。
1927 年,Kermack 和 McKendrick 提出了仓室建模法[54],将个体所处状态分
为四类:易感状态(S),未得病者,但没有免疫疾病的能力,与感染者接触后容
易受到感染;潜伏状态(E),接触过感染者,但暂时不会传播疾病的个体,适用
于潜伏期长的传染病;感染状态(I),染上传染病的个体,可将传染病传播给处于
易感状态的未得病者;免疫状态(R),因病愈后具有免疫力或死亡的个体。根据
不同的传播过程及实际情况可建立多种传播模型[55-58]。本节重点介绍最经典的
SIR 模型。
SIR 模型将人群划分为三类:易感者(S)、感染者(I)和免疫者(R)。其中感染
者以概率  感染易感人群,同时感染者本身以概率 对疾病免疫,SIR 模型状态
转移图如图 2-15 所示。
图 2-15 SIR 模型状态转移图
16
基于超图的小世界超网络模型及传播特性分析
记  为感染概率, 为免疫概率, s(t) 、i(t)和 r(t)分别为时刻t 的易感者,
感染者,免疫者的比例,则有 s(t)  i(t)  r(t) 1。SIR 模型的微分方程描述如下:
ds(t)

dt

di(t)

dt

dr(t)


dt

s(t)i(t)
s(t)i(t) -i(t)
i(t) (2-11)
2.6 小结
本章首先回顾了超图和超网络的基本概念和基本性质,超图是普通图的推
广,超网络和超图的性质大多由复杂网络和普通图推广而来。随后介绍了复杂网
络中的三种经典模型以及超网络中一种经典的超网络演化模型。最后介绍了传播
动力学的相关理论,为小世界超网络中的传播动力学研究奠定理论基础。
17
青海师范大学硕士学位论文
第三章 基于超图的小世界超网络模型
3.1 概述
一般来说,网络中的大部分节点彼此不相邻,但某一节点的邻居之间亦可能
是邻居关系,大多数节点都能够与除自己之外的所有节点通过较短的距离取得联
系,且网络中节点之间的距离与网络节点数量成正相关关系,具有这些特性的网
络就是小世界网络。针对这种特性,Watts 与 Strogatz 两人共同在 1998 年提出了
复杂网络中的第一个小世界网络模型,WS 模型,此模型同时具备高聚集系数、
低平均路径长度,是从完全规则网络向完全随机网络的过渡。在 WS 模型被提出
后 , 相 关 研 究 在 复 杂 网 络 学 界 争 相 出 现 , Barthélémy 和 Amaral 最 先 对
Watts-Strogatz 模型中“大世界”(如规则网络)与小世界的交叉性质进行了描述[59]。
小世界理论的研究在复杂网络的发展过程中取得了丰硕的研究成果[60-66]。而迄今
为止,对基于超图的超网络上的小世界特性研究还较少。基于以上分析,本章以
最近邻耦合超网络模型为基础,构造小世界超网络模型,提出基于超边随机重连
的小世界超网络模型和基于超边随机增加的小世界超网络模型,通过实验仿真分
析以及等价随机超网络量化,表明以超边随机重连和超边随机增加方法构建小世
界超网络模型是可行的。
本章主要介绍了基于超边随机重连的小世界超网络模型和基于超边随机增
加的小世界超网络模型构建方法。首先给出了规则的最近邻耦合超网络模型的构
建方法及仿真分析结果,随后介绍了两种小世界超网络模型的构建思想和演变过
程,以最近邻耦合超网络为基础,构建具有小世界特性的超网络模型,并进行仿
真实验,得到两种小世界超网络模型的聚集系数、平均路径长度变化趋势及超度
分布规律,通过等价随机超网络量化这两种超网络模型的小世界特性。最后,将
两种小世界超网络模型与经典超网络演化模型以及复杂网络中的经典小世界网
络模型进行对比分析,进一步验证了两种小世界超网络模型的小世界特性。
3.2 基于超图的最近邻耦合超网络模型
3.2.1 模型构建
复杂网络中的小世界网络是从最近邻耦合网络逐渐演化形成的,本文提出的
小世界超网络模型以最近邻耦合超网络为基础网络进行构建。最近邻耦合超网络
模型构建思想为:从包含 N 个节点的环开始,其中每个节点都与其周围的各 K/2
个邻居节点组合形成一条超边,直至形成一个环状的超网络。以此方式构建的
最近邻耦合超网络是均匀超网络。
18
基于超图的小世界超网络模型及传播特性分析
图 3-1 中(a)、(b)分别为最近邻耦合网络和最近邻耦合超网络示意图。
E2 E3
E1
V1
 E4
E8
V8 V2
V7 V3
E7
 E5
V6 V4
V5
 E6
(a) 最近邻耦合网络 (b) 最近邻耦合超网络
图 3-1 最近邻耦合网络示意图
3.2.2 仿真实验及结果分析
(1) 最近邻居节点数量对超网络特性的影响
最近邻居节点数量会影响最近邻耦合超网络的聚集特性的强弱以及节点之
间的距离。表 3-1、表 3-2 分别统计了 N=1000 时,不同最近邻居节点数量下超
网络中最近邻耦合超网络和复杂网络中最近邻耦合网络的聚集系数、平均路径长
度。
表 3-1 最近邻耦合超网络拓扑参数值对比
最近邻居节点数 聚集系数 平均路径长度
20 0.524072 6.493993
18 0.520668 7.189189
16 0.516605 8.056056
14 0.511669 9.171171
12 0.505540 10.657657
10 0.497695 12.737737
8 0.487179 15.860360
6 0.471698 21.063063
表 3-2 最近邻耦合网络拓扑参数值对比
最近邻居节点数 聚集系数 平均路径长度
20 0.7105 25.4755
18 0.7059 28.2523
16 0.7000 31.7207
14 0.6923 36.1802
12 0.6818 42.1261
10 0.6667 50.4505
8 0.6429 62.9379
6 0.6000 83.7508
19
青海师范大学硕士学位论文
由表 3-1 可以观察到,随着邻居节点数量增多,超网络的聚集系数也在增大,
成正相关关系,而平均路径长度则与最近邻居节点数量成负相关关系,最近邻居
节点数量越多,平均路径长度越小。结合表 3-1、表 3-2 可以观察到,最近邻耦
合超网络与最近邻耦合网络的聚集系数和平均路径长度变化趋势相同。
(2) 网络规模对超网络特性的影响
在不同最近邻居节点数量 K 下,测试网络规模 N 对超网络特性的影响。将 K
分别固定为 16、18,N=1000、2000、3000、4000。表 3-3 为平均路径长度随网
络规模改变的变化情况。图 3-2 为根据表 3-3 绘制的平均路径长度随网络规模变
化的趋势示意图。
表 3-3 平均路径长度随网络规模改变的变化情况
最近邻居
节点数量 规模 最近邻耦合超网络
平均路径长度 最近邻耦合网络平均
路径长度
1000 8.05606 31.7207
K=16 2000 15.8681 62.9694
3000 23.6802 92.2194
4000 31.4922 125.468
1000 7.18919 28.2523
K=18 2000 14.1330 56.0281
3000 21.0770 83.8063
4000 28.0210 111.583
结合表 3-3 和图 3-2 可以观察到,当 N=1000,K=16 时,最近邻耦合超网络
的平均路径长度为 8.05606,节点数量增大到 2000、3000、4000 时,最近邻耦合
超网络的平均路径长度分别成 2 倍、3 倍、4 倍增长,即平均路径长度与网络规
模成正比。这与复杂网络中最近邻耦合网络平均路径长度的变化规律相同,K=18
时的超网络同样有此规律,说明此规律适用于最近邻耦合超网络。
(a) K=18 (b) K=16
图 3-2 平均路径长度随网络规模变化的趋势示意图
20
基于超图的小世界超网络模型及传播特性分析
(3) 最近邻耦合超网络小世界特性分析
以 N=1000,K=14 的最近邻耦合超网络为例,该超网络的聚集系数 CH 为
0.511669,说明最近邻耦合超网络的超三角形在超网络中分布较为密集,即至少
被两条超边包含的节点参与形成超三角形的概率较高,且节点之间的联系较为稳
固;该超网络的平均路径长度 L 为 9.171171,说明任意两个节点之间需要经过最
少 9 条超边才能完成信息的传递,非常不利于信息的快速传播。
由以上分析可得,最近邻耦合超网络中任意两个节点之间的联系有一定的规
则,聚集系数与平均路径长度均较大,虽然具有高聚集特性,但不具有短的路径
长度,因此这类超网络不具有小世界特性。
3.3 基于超边随机重连的小世界超网络模型
3.3.1 模型构建
本文提出的基于超边随机重连的小世界超网络模型以最近邻耦合超网络为
基础网络进行构建,通过在最近邻耦合超网络中引入少许的随机性,产生具有小
世界特性的超网络模型。重连过程会使超网络中出现长边,使超网络保持高聚集
特性的同时,减小平均路径长度。
模型构建算法如下:
(1) 从规则超图开始:考虑一个含有 N 个节点的环状最近邻耦合超网络,其
中每个节点都与它左右相邻的 K/2 个节点组合形成一条超边,K 是偶数。
(2) 超边随机化重连:以概率 p 随机地重新连接超网络中原有的每条超边,
即将超边内的节点以概率 p 替换成随机选择的其他节点,不得出现重边,且每条
超边内不允许出现重复节点。
3.3.2 仿真实验及结果分析
(1) 聚集系数与平均路径长度
给定一个最近邻耦合超网络 H。仿真中令节点数量 N=1000,最近邻居节点
数量 K=14,重连概率 p=0、0.01、0.1、0.2、0.5、0.9、1。构建不同概率 p 下的
超边随机重连小世界超网络模型,其中,p=0 时为规则的最近邻耦合超网络,p=1
时为等价随机超网络。不同概率 p 下基于超边随机重连的小世界超网络模型聚集
系数以及平均路径长度如表 3-4 所示。为消除随机影响,每次仿真实验独立重复
运行 50 次取平均。
21
青海师范大学硕士学位论文
表 3-4 超边随机重连小世界超网络模型拓扑参数
随机重连概率 p 聚集系数 平均路径长度
0 0.511670 9.171171
0.01 0.479835 1.603196
0.1 0.350575 1.036181
0.2 0.271882 0.959250
0.5 0.181672 0.926827
0.9 0.180042 0.916767
1 0.179116 0.916703
由表 3-4 可以观察到,随着超边随机重连概率 p 的增加,平均路径长度由
9.171171 急剧减小至 1.603196,但聚集系数减小速度则较为缓慢,由 0.511670
减小至 0.479835,这与复杂网络中小世界网络构造过程表现出的特征完全一致。
图 3-3 为超网络聚集系数与平均路径长度随重连概率改变的变化示意图。为
使不同拓扑参数的变化趋势表示在同一图中,以最近邻耦合超网络的相应参数为
基准,将 CH(p)和 LH(p)做归一化处理,即 CH(p)/C(0)和 LH(p)/L(0),从而使得两个
拓扑参数的最大值均为 1。
图 3-3 超边随机重连概率 p 下聚集系数、平均路径长度变化图
(2) 超网络小世界特性量化
等价随机网络是指与给定网络具有相同规模及平均度的完全随机网络[66],将
给定网络与等价随机网络进行比较能够量化给定网络的小世界特性。p=0.01 时基
于超边随机重连的小世界超网络与等价随机超网络的聚集系数与平均路径长度
如表 3-5 所示。
22
基于超图的小世界超网络模型及传播特性分析
表 3-5 超边随机重连小世界超网络与等价随机超网络拓扑参数
对比标准 超边随机重连超网络模型 等价随机超网络模型
聚集系数 0.479835 0.179116
平均路径长度 1.603196 0.916703
由表 3-5 可知,p=0.01 时基于超边随机重连的小世界超网络聚集系数远大于
等价随机超网络的聚集系数,而平均路径长度约为 1.603196,略大于等价随机超
网络,表现出明显的小世界效应。
另外,系数 可量化给定超网络的小世界特性[67-68], C Cr L Lr
  H / / / ,
H
其中 CH 和 LH 分别为给定超网络的聚集系数与平均路径长度,Cr 和 Lr 分别为等
价随机超网络的聚集系数与平均路径长度。p=0.01 时超边随机重连小世界超网络
的系数 为:


C
H

 
Cr
 L
 H

Lr




 
0.479835
 
 
0.179116
1.603196 
 
 
0.916703 2.678906
1.748871 1.53179
由系数 1(C Cr H  )可以认为基于超边随机重连的小世界超
H  ,且 L Lr
网络模型具有小世界特性。
(3) 超度分布
图 3-4 为概率 p 取不同值时,超边随机重连小世界超网络模型的超度分布图。
为消除随机影响,每次仿真实验独立重复运行 50 次取平均。由图 3-4 可以观察
到,小世界超网络模型的超度分布曲线服从泊松分布,与等价随机超网络超度分
布趋势相同,随着概率 p 的增大,曲线峰值逐渐减小,曲线范围逐渐增大。
图 3-4 超边随机重连小世界超网络模型超度分布图
23
青海师范大学硕士学位论文
3.4 基于超边随机增加的小世界超网络模型
3.4.1 模型构建
基于超边随机重连的小世界超网络模型是通过改变最近邻耦合超网络中原
有超边而获得小世界特性,为进一步研究小世界超网络的特性,本节提出基于超
边随机增加的小世界超网络模型,即不再改变最近邻耦合超网络中原有超边,而
是直接增加超边,将超网络中的节点联系起来,形成小世界效应。
模型构建算法如下:
(1) 从规则超图开始:考虑一个含有 N 个节点的环状最近邻耦合超网络,其
中每个节点都与它左右相邻的 K / 2 个节点组合形成一条超边, K 是偶数。
(2) 超边随机化增加:生成一条包含 K 个随机节点的超边,以概率 p 添加至
最近邻耦合超网络中,其中新生成的超边不允许与原有超边重复。
3.4.2 仿真实验及结果分析
(1) 聚集系数与平均路径长度
给定一个最近邻耦合超网络 H。仿真中令 N =1000,K =14,p=0、0.01、0.1、
0.2、0.5、0.9、1。构建不同概率 p 下基于超边随机增加的小世界超网络模型。
为消除随机影响,每次仿真实验独立重复运行 50 次取平均。在不同超边随机增
加概率 p 下该超网络的聚集系数及平均路径长度值如表 3-6 所示。由表可知,超
边随机增加概率 p 值较小时,超网络兼具高聚集系数及低平均路径长度。
表 3-6 超边随机增加小世界超网络模型拓扑参数
随机增加概率 p 聚集系数 平均路径长度
0 0.511670 9.171171
0.01 0.503974 1.864079
0.1 0.474029 1.567841
0.2 0.431993 1.368780
0.5 0.385110 1.281698
0.9 0.324334 1.166873
1 0.314771 1.148615
图 3-5 为超网络聚集系数随超边随机增加概率 p 改变的变化图,图 3-6 为超
网络平均路径长度随超边随机增加概率 p 改变的变化图。
由图 3-5 可知,聚集系数分布曲线较为平滑。当 p 值刚开始变化时,聚集系
数下降幅度较小,这意味着增加少量超边不会引起聚集系数的快速下降,随着概
率 p 的增加,超网络聚集系数缓慢降低,p 最大时下降至最低值。
由图 3-6 知,超网络的平均路径长度在急剧下降后以较小的幅度逐渐减小,
24
基于超图的小世界超网络模型及传播特性分析
平均路径长度分布曲线与一条水平的直线类似。p=0 时,超网络中任意两节点之
间的平均路径长度大于 9,当 p 开始变化时,少量超边的增加使整个超网络的平
均路径长度大幅度降低。正如在现实交通网络中,城市甲与城市乙之间没有直达
的公路之前,来往十分不便,而在政府投资修建省道、国道、高速公路之后,极
大的缩短了两地之间的距离。
图 3-5 超边随机增加概率 p 下聚集系数变化图
图 3-6 超边随机增加概率 p 下平均路径长度变化图
(2) 超网络小世界特性量化
p=0.01 时基于超边随机增加的小世界超网络与等价随机超网络的聚集系数
与平均路径长度值如表 3-7 所示。由表 3-7 可知,超边随机增加概率 p=0.01 时,
该超网络聚集系数约为 0.503974,远高于等价随机超网络的聚集系数;平均路径
长度约为 1.864079,略高于等价随机超网络的平均路径长度。
表 3-7 p=0.01 时超边随机增加超网络与随机超网络拓扑参数对比
对比标准 超边随机增加超网络 等价随机超网络
聚集系数 0.503974 0.191327
平均路径长度 1.864079 0.911572
25
青海师范大学硕士学位论文
进一步,通过参数 对基于超边随机增加的小世界超网络的小世界特性进行
量化,p=0.01 时该超网络的系数 为:

C
 H
 Cr


L
H

Lr




 
0.503974
 
 0.191327
 
 
1.864079
 
0.911572 2.656287333
2.044903393 1.28812449
由参数 1.2881 ( 1 )可以认为基于超边随机增加的小世界超网络模型具
有小世界效应。
(3) 超度分布
表 3-8 统计了概率 p=0.01、0.1、0.2、0.5、0.9、1 时超边随机增加超网络模
型超度分布情况。由表 3-8 可知,超度的最低值为 14,这是由于超边随机增加超
网络是在最近邻耦合超网络的基础上增加超边,相当于在规则超网络的基础上叠
加一个完全随机超网络。因此,超网络中任意节点超度值至少为 14,不会出现
某一节点不在任意一超边中的问题,也不会破坏超网络的连通性。
表 3-8 不同概率 p 下的超网络超度值分布情况
超度值/增
加概率 p=0.1 p=0.2 p=0.5 p=0.9 p=1
14 85.7% 69.6% 50.8% 26.6% 24.8%
15 13.2% 25.0% 35.1% 38.0% 34.5%
16 1.1% 4.9% 10.7% 22.3% 24.3%
17 0.4% 3.0% 9.9% 11.1%
18 0.1% 0.3% 2.3% 3.5%
19 0.1% 0.9% 1.4%
20 0.2%
21 0.2%
图 3-7 为依据表 3-8 中数据得到的不同概率 p 下基于超边随机增加的小世界
超网络模型超度分布图。由图 3-7 可知,当概率 p 足够小时,大部分节点的超度
值仍为 14,极少部分节点的超度值大于 14。随着概率 p 逐渐增大,超度分布的
峰值逐渐降低,分布范围逐渐扩大。这说明随着超网络中超边数量的增加,超度
值为 14 的节点逐渐减少,超度值大于 14 的节点增加。
26
基于超图的小世界超网络模型及传播特性分析
图 3-7 超边随机增加小世界超网络超度分布图
由图 3-7 可知,当概率 p 足够小时,大部分节点的超度值仍为 14,极少部分
节点的超度值大于 14。随着概率 p 逐渐增大,超度分布的峰值逐渐降低,分布
范围逐渐扩大。这说明随着超网络中超边数量的增加,超度值为 14 的节点逐渐
减少,超度值大于 14 的节点增加。
3.5 小世界特性对比分析
3.5.1 小世界超网络模型与无标度超网络模型对比分析
无标度超网络模型在某些情况下也具有小世界特性。因此,本节将 2.4 节中
经典无标度超网络模型和本章提出的小世界超网络模型进行对比,探究影响无标
度超网络模型与小世界超网络模型拓扑特性的因素。
表 3-9 为 N =1000,K =14,p=0、0.01、0.1、0.2、0.5、0.9、1 时两种小世界
超网络模型的聚集系数,表 3-10 为 2.4 节中 N =1000,新增加节点个数 m =2、4、
6 时无标度超网络模型的聚集系数。
表 3-9 不同概率 p 下小世界超网络模型的聚集系数
概率 p 超边随机重连超网络 超边随机增加超网络
0 0.511670 0.511670
0.01 0.479835 0.503974
0.1 0.350575 0.474029
0.2 0.271882 0.431993
0.5 0.181672 0.38511
0.9 0.180042 0.324334
1 0.179116 0.314771
27
青海师范大学硕士学位论文
表 3-10 不同 m 下无标度超网络模型的聚集系数
m 聚集系数
2 0.67
4 0.48
6 0.37
结合表 3-9 和表 3-10 可以观察到,无标度超网络模型中新增加的节点个数 m
的取值决定了聚集系数的大小,当 m 较小时无标度超网络模型能够表现出较高的
聚集特性,随着新增加节点的数量m 增加,无标度超网络模型在演化完成之后的
聚集系数越小,通过这种方式构建的超网络模型,新形成的一条超边中新增加节
点数量较少时才能表现出高聚集的特性,而在两种小世界超网络模型中概率 p 的
取值决定了聚集系数的大小,p 值较小时超网络的聚集系数大。
表 3-11 统计了不同概率 p 下两种小世界超网络模型的平均路径长度,表 3-12
统计了 m=2 时,不同超边规模下无标度超网络模型的平均路径长度。
表 3-11 不同概率 p 下小世界超网络模型的平均路径长度
概率 p 超边随机重连超网络 超边随机增加超网络
0 9.171171 9.171171
0.01 1.603196 1.864079
0.1 1.036181 1.567841
0.2 0.95925 1.36878
0.5 0.926827 1.281698
0.9 0.916767 1.166873
1 0.916703 1.148615
表 3-12 m=2 时无标度超网络模型的平均路径长度
超边数量 平均路径长度
1000 6.2
3000 9
结合表 3-11 和表 3-12 可知,新增加节点数 m=2 时无标度超网络模型的平均
路径长度随超边数量 N 增加而增加,从 1000 条超边增加到 3000 条超边使无标
E
度超网络的平均路径长度约增加了 2.8,超边数量越多,平均路径长度越大,信
息传递的速度越慢。小世界超网络模型中概率 p 的取值越大,平均路径长度越小,
如基于超边随机增加的小世界超网络在增加超边后平均路径长度会下降,p=0.01
时平均路径长度由 9.171171 急剧下降至 1.864079。
28
基于超图的小世界超网络模型及传播特性分析
3.5.2 超边随机重连小世界超网络与 WS 小世界网络对比分析
由于基于超边随机重连的小世界超网络模型与复杂网络中 WS 小世界网络
模型的演变思想类似。因此,本节将这两种小世界网络模型进行对比分析,探究
其演变过程中的相似之处。表 3-13,表 3-14 分别为 N=1000,K=14,p=0、0.01、
0.1、0.2、0.5、0.9、1 时,基于超边随机重连的小世界超网络模型与 WS 小世界
网络模型以相同概率 p 进行演变的聚集系数及平均路径长度值。
表 3-13 小世界超网络与 WS 小世界网络的聚集系数
概率 p 超边随机重连小
世界超网络 WS 小世界网络
0 0.511670 0.6923
0.01 0.479835 0.6805
0.1 0.350575 0.5787
0.2 0.271882 0.4919
0.5 0.181672 0.3194
0.9 0.180042 0.2055
1 0.179116 0.1867
表 3-14 小世界超网络与 WS 小世界网络的平均路径长度
概率 p 超边随机重连小
世界超网络 WS 小世界网络
0 9.171171 36.1802
0.01 1.603196 6.6069
0.1 1.036181 3.6428
0.2 0.959249 3.2159
0.5 0.926827 2.7546
0.9 0.916767 2.5524
1 0.916703 2.5071
图 3-8、图 3-9 分别为依据表 3-13、表 3-14 中数据得到的聚集系数与平均路
径长度变化图。结合图 3-8、图 3-9 可以观察到,基于超边随机重连的小世界超
网络模型和 WS 小世界网络模型在演变过程中的聚集系数与平均路径长度变化
趋势相似。随着概率 p 的逐渐增加,两者的聚集系数在整个过程中均以较小的幅
度缓慢下降,而平均路径长度则是在急剧下降后以较小的幅度缓慢下降,平均路
径长度变化曲线几乎接近水平。
由此可见,在以概率 p 随机地进行超边重连后,超网络的平均路径长度大幅
度缩短的同时保持了较高的聚集系数,基于超边随机重连的小世界超网络模型与
WS 小世界网络模型在演变过程中表现出的特征大致相同,概率 p 在一定范围内
时,超边随机重连小世界超网络模型具有现实世界中大多数超网络表现出的高聚
29
青海师范大学硕士学位论文
集、低平均路径长度的特性。
图 3-8 超边随机重连小世界超网络与 WS 小世界网络聚集系数变化图
图 3-9 超边随机重连小世界超网络与 WS 小世界网络平均路径长度变化图
3.5.3 超边随机增加小世界超网络与 NW 小世界网络对比分析
表 3-15,表 3-16 分别统计了 N=1000,K=14,p=0、0.01、0.1、0.2、0.5、
0.9、1 时基于超边随机增加的小世界超网络模型与 NW 小世界网络模型演变过
程中的聚集系数和平均路径长度,通过对比分析,探寻两者的相似之处。
表 3-15 小世界超网络与 NW 小世界网络的聚集系数
概率 p 超边随机增加小
世界超网络 NW 小世界网络
0 0.511670 0.6923
0.01 0.503974 0.6796
0.1 0.474029 0.5787
0.2 0.431993 0.4849
0.5 0.385109 0.3200
0.9 0.324334 0.2059
1 0.314771 0.1882
30
基于超图的小世界超网络模型及传播特性分析
表 3-16 小世界超网络与 NW 小世界网络的平均路径长度
概率 p 超边随机增加小
世界超网络 NW 小世界网络
0 9.171171 36.1805
0.01 1.864079 6.4967
0.1 1.567841 3.6310
0.2 1.368779 3.1963
0.5 1.281698 2.7510
0.9 1.166873 2.5449
1 1.148615 2.4999
图 3-10 和图 3-11 分别为依据表 3-15 和表 3-16 得到的不同概率 p 下归一化
处理后两种小世界网络模型的聚集系数与平均路径长度变化图。
图 3-10 超边随机增加小世界超网络与 NW 小世界网络聚集系数变化图
图 3-11 超边随机增加小世界超网络与 NW 小世界网络平均路径长度变化图
结合图 3-10、图 3-11 可知,在节点规模及最近邻节点数相同的情况下,超
网络中基于超边随机增加的小世界超网络模型和复杂网络中 NW 小世界网络模
型的聚集系数与平均路径长度变化趋势大致相同。随着概率 p 逐渐增加,两者的
31
青海师范大学硕士学位论文
聚集系数均以较小的幅度缓慢下降,NW 小世界网络的下降幅度略大于超边随机
增加超网络,而两者的平均路径长度均以极大的幅度减少后,以较小的幅度缓慢
下降,平均路径长度变化曲线接近水平。综上所述,概率 p 在一定范围内时,基
于超边随机增加的小世界超网络模型兼具高聚集特性和小世界性,能够描述现实
世界中具有小世界特性的超网络。
3.6 小结
本章主要研究了超网络中小世界超网络模型的构造方法,将基于普通图的最
近邻耦合网络扩展到基于超图的超网络中,得到最近邻耦合超网络模型,以该超
网络模型为基础,提出了基于超边随机重连的小世界超网络模型和基于超边随机
增加的小世界超网络模型,对这两种小世界超网络模型进行实验仿真分析后发
现,构建的两种小世界超网络均表现出高聚集系数、低平均路径长度的特征,并
通过等价随机超网络量化了两种模型的小世界特性。最后,与经典超网络演化模
型及经典复杂网络中小世界网络模型进行对比,进一步验证了本章提出的两种小
世界超网络模型的小世界特性。
32

【博士论文范文论文题目:基于超图的小世界超网络模型及传播特性分析】相关文章

《博士论文范文论文题目:基于超图的小世界超网络模型及传播特性分析》

将本文的Word文档下载到电脑,方便收藏和打印

推荐度:

点击下载文档

文档为doc格式

热点排行

推荐阅读

付费下载

付费后无需验证码即可下载

限时特价:原价:

微信支付

支付宝支付

微信二维码支付

付费后无需验证码即可下载

支付金额:

支付成功