基于节点特性的复杂网络适应度模型研究

论文价格:免费 论文用途:其他 编辑:硕博论文网 点击次数:
论文字数:35624 论文编号:sb2020053016321931306 日期:2020-06-02 来源:硕博论文网
本文是一篇在职硕士论文, 论文主要对适应度模型进行了深入的分析和研究,在对实际网络的节点特性及现有各种模型分析的基础上,论文确定了对现有适应度模型的几点改进方向:首先是要对节点特性中反映节点竞争属性的方面给出系统的定义,使得模型的择优连接与实际网络更加类似;其次是要在保留无标度特性的基础上提高模型的小世界特性(较高的聚类系数及较低的平均路径长度),使模型的统计特性及拓扑结构更加接近实际网络。以此为目标,根据节点竞争属性的不同特征,论文首先提出了两种新的适应度的定义:静态适应度和动态适应度,并结合适应度模型提出了静态适应度模型和动态适应度模型。

第 1 章  绪论

1.1  研究背景及意义
1.1.1  研究背景
20 世纪中后期,随着科技的不断进步,人类在物理学、生物学等多个学科领域发现了许多类型各异、成员众多且关系复杂的网络。按照网络属性的不同[1],这些网络可以分为社会网络(人际关系网络,演员合作网络,世界贸易网络)、信息网络(万维网,电子社交网络)、技术网络(电力网络,交通网络,计算机互联网)、生物网络(蛋白质网络,基因调控网络)、自然网络(食物链)等。
通过对这些实际网络进行大量研究,学者们发现这些节点众多、结构复杂的网络既不属于规则网络的范畴,也不属于随机网络的范畴。二十世纪末,Watts 和 Strogatz 及Barabasi 和 Albert 先后提出了小世界网络模型[3]和无标度网络模型[4],两个模型分别描述了这些节点众多、结构复杂的网络中存在的小世界特性和无标度特性。小世界网络模型和无标度网络模型的提出使得人们对网络的研究从二十世纪中叶的随机图论阶段进入到了新的复杂网络阶段。BA 模型提出的择优连接的思想反映了实际网络中存在的物竞天择,适者生存的竞争特性,被沿用至今。但其依靠度值大小进行择优连接的方法却过于简单,未能真实的反映出实际网络的择优方式,此后学者们尝试对 BA 模型的择优方式进行改进,先后提出了适应度模型、吸引子模型、吸引力模型等,这些模型将节点具有的吸引其它节点与之连接的竞争属性与度相结合作为择优连接的依据,这种改进使模型在择优机制上更加接近实际网络,但是通过对比拓扑结构及统计特性可以发现,这些改进的模型仍与实际网络仍存在较大差距。
现实中,大多数网络节点的度值与节点加入网络的时间无直接关联。如微博中,用户的粉丝数量通常与加入微博的时间长短无关,粉丝数量的多少通常是由用户本身的热度所决定的。如果将 BA 模型及其改进模型的节点的度值按照节点加入网络的顺序进行排列可得其节点度的时间分布如图 1-1 所示:横轴表示节点进入网络的先后顺序,纵轴表示节点度值的大小,从图中可以看出,度值较大的节点集中分布在整个区域的左上角。而实际网络中后加入网络的节点也能获得较大的度值,如图 1-2 为一个引文网络的入度时间分布图,在各个时间段均有度值较大的节点,与图 1-1 度值较大的节点集中分布在整个区域的左上角的情况明显不同。
图 1-1  BA 模型节点度的时间分布图
.............................
 
1.2  复杂网络演化模型研究现状
目前已有的复杂网络演化模型大致可分为两类:小世界模型及其改进模型和无标度网络模型及其改进模型。论文在对网络研究现状进行总结时,将不按国内外研究现状进行总结,而是根据模型的分类及模型的改进方向的不同对模型的研究现状进行分类分析。
1.2.1  小世界模型研究现状
小世界网络模型[3]是由 Watts 和 Strogatz 在 1998 年提出的,简称 WS 小世界模型。该模型提出了一种介于规则网络和随机网络之间的网络模型的构建方法。通过控制随机重连的边的比例,可以控制网络的拓扑结构在规则网络和随机网络间进行变化。Newman和 Watts 将 WS 小世界模型中的随机重连改为随机加边,构建出了 NW 小世界模型[5]。Barrat A, Weigt M[8]通过数值仿真,对触发小世界特性的原因进行了分析。Maier Benjamin F[9]对小世界模型进行了修正,使模型可以在完全随机的极限内更加接近随机网络模型,
并证明了修正的模型相较原模型具有更好的适用性。统计参数表明,小世界模型生成的网络具有较强的聚类特性及较短的平均路径长度,这与实际网络的特征极为类似,这一特性使得小世界模型被广泛应用在各种研究领域。孟仲伟等[16]从电力网络等拓扑结构入手,对美国西部电网和中国北部电网进行比较分析,证明这两大电网都属于小世界网络,从而提出了一个分析电网发生级联式故障机理的新视角。穆华平等[17]通过分析印象网络中信息传播的主要因素,结合小世界网络提出了一种动态邻域结构的微粒群算法,对大部分优化问题都具有很好的效果。李静等[18]在资源查找算法中引入小世界原理,对资源定位和查找的时间复杂度进行了优化,提高了资源查找的效率。马力等[19]基于小世界模型提出一种新的关键词提取算法,实验结果表明,该算法是有效的。韩定定等[20]基于小世界模型提出了一种快速评估航线结构优化情况定方法,可以分局网络客流分布情况快速推算出航线网络的最优拓扑结构及相应的航班频率分布,为航线增减和调整提供建议。赵雨露等[21]将当前的非负矩阵分解的社区发现算法与小世界模型相结合,提出了一种新的社区发现算法,真实网络与人工网络的验证表明,新算法在性能上有一定的提升。可以看出,小世界模型在算法优化和鲁棒性领域都有广泛的应用。而鲁棒性是复杂网络研究的重要方向,复杂网络的鲁棒性是指当网络中的节点和连边受到不确定因素的影响时,网络能够保持结构的完整性及功能的完整性的能力。Barabasi 和 Albert 等[2]首次对小世界模型的鲁棒性进行了分析,实验结果表明小世界网络在面对随机攻击和蓄意攻击时具有类似的鲁棒性。
.......................

第 2 章  复杂网络理论与网络节点特性

2.1  复杂网络理论
2.1.1  网络的表示
由连边是否包含权重、方向,可将网络进行简单的分类:边包含权重但没有方向的网络称为无向加权网络;既有权重,又有方向的网络称为有向加权网络;边只有方向但无权重的网络称为有向无权网络;边即无权重又无方向的网络可称为无向无权网络。按照一定的规律将节点相互连接在一起形成的网络称为规则网络,反之不按任何规则随机连接的网络则是随机网络。
图 2-1  各类网络示意图
图 2-1(a)为有向无权网络,图 2-1(b)为有向加权网络,图 2-1(c)为无向无权网络,图 2-1(d)为无向加权网络。为了方便计算机进行处理,通常采用矩阵形式来对网络进行描述。
........................

2.2  实际网络节点演化特性
2.2.1  实际网络节点特性分析
在复杂网络模型研究现状的评述中,论文指出将节点特性中除了度值以外其它吸引节点与之连接的特性加入到节点连接概率公式中,是对 BA 模型非常重要的改进。因为实际网络中度值只是节点特性的一个方面,不能代表节点的全部特性。在互联网中,一个站点是否能被浏览很大程度取决于其提供的内容和服务质量的好坏;在引文网络中,一篇文章是否被引用不仅取决于其过去被引用的次数,还取决于文章的内容是否对作者是否有帮助;在微博网络中,选择是否关注一个用户不仅取决于该用户过去粉丝数量的多少,更取决于用户是否对博主本人感兴趣。因此,为了更精确的反映出实际网络的演化特性,必须将节点特性更准确的反映到网络演化过程中。
实际网络的演化特性千差万别,不同网络的节点特性也不同。网络的演化过程可以被简化为节点获取网络中其它节点连接的过程,而节点的竞争力通常是节点获得其它节点连接的重要依据。但在不同的网络中,节点竞争力具有不同的特性,通过对大量实际网络的分析,论文认为实际网络中节点竞争力可以分为两种情况:一种是节点竞争力会随着网络的演化而不断变化;一种是节点自身竞争力从节点进入网络起就不在发生变化。
............................
 
第 3 章  静态适应度网络模型 ........................................... 26
3.1  静态适应度模型的定义及构造方法 .................................. 26
3.2  静态适应度模型度分布理论分析 ..................................... 26
3.3  静态适应度模型仿真分析 ..................................... 28
第 4 章  动态适应度网络模型 ................................................ 42
4.1  动态适应度模型的定义及构造方法 .................................... 42
4.1.1  动态适应度模型及相关参数的定义 .............................. 42
4.1.2  模型的构造方法 ............................... 43
第 5 章  结论与展望 ............................... 56
5.1  研究结论 ............................ 56
5.2  不足与展望 ................................. 56

第 4 章  动态适应度网络模型

4.1  动态适应度模型的定义及构造方法
4.1.1  动态适应度模型及相关参数的定义
动态适应度模型(Dynamic fitness model)是节点适应度会随网络演化而发生变化的适应度模型。由 2.2.3 的分析可知,竞争性网络中节点适应度与节点从网络中获取的资源数量通常具有正向相关关系。而度值通常是反映网络中节点获取资源数量的指标,在动态适应度模型中,节点适应度与度值是正向相关关系。这些正向相关关系可以是一次线性相关或二次相关或其它相关关系,图 4-1 展示了几种简单的正向相关关系的数学表达。
图 4-1  适应度与度相关关系示意图
............................

第 5 章  结论与展望

5.1  研究结论
论文主要对适应度模型进行了深入的分析和研究,在对实际网络的节点特性及现有各种模型分析的基础上,论文确定了对现有适应度模型的几点改进方向:首先是要对节点特性中反映节点竞争属性的方面给出系统的定义,使得模型的择优连接与实际网络更加类似;其次是要在保留无标度特性的基础上提高模型的小世界特性(较高的聚类系数及较低的平均路径长度),使模型的统计特性及拓扑结构更加接近实际网络。以此为目标,根据节点竞争属性的不同特征,论文首先提出了两种新的适应度的定义:静态适应度和动态适应度,并结合适应度模型提出了静态适应度模型和动态适应度模型。在第三章中集中对静态适应度模型的拓扑结构参数特性进行了分析。结果表明,网络的度分布、平均路径长度、聚类系数等统计参数及无标度特性都受到适应度比例的影响。随着适应度在连接概率中的比重从 0-1 不断增加,模型的平均路径长度不短增加且聚类系数不断降低,网络逐渐由异质网络逐渐转化为同质网络。网络的小世界特性和无标度特性都逐渐消失。理论分析表明,当网络完全依靠节点适应度增长时,网络的度分布也不在服从幂律分布,网络完全转化为均质网络。在第四章中,基于动态适应度模型论文提出了一种基于全局的部分择优连接方法,并对模型的拓扑结构、统计参数及鲁棒性分别进行了分析。理论分析表明,动态适应度模型的度分布服从幂律分布,具有较强的无标度特性。而且与现有的 BA 模型、适应度模型相比,动态适应度模型具有最高的聚类系数和最低的平均路径长度。这表明动态适应度模型在保持无标度特性的同时还具有现有模型中最好的小世界特性。鲁棒性分析还表明,动态适应度模型具有高聚类系数模型特有的鲁棒性特征。案例分析表明,静态适应度模型和动态适应度模型很好的反映了非竞争性网络和竞争性网络所具有的特性。加入节点竞争属性的网络演化方法相较只依靠节点度值的网络演化方法更加接近实际网络的演化特性。
参考文献(略)