基于K-最短路径和社团结构的网络传输性能研究

发布时间：2019-10-30 02:59

【摘要】：复杂系统往往是通过许多个体之间的相互作用形成的,因而这些系统能抽象成网络进行研究。通过利用网络科学的理论描述系统的结构特征,理解系统的功能和性质,从而得到其规律进而加以应用是复杂系统研究贯彻始终的目标。在复杂系统抽象成为网络进行研究以后,系统运行状况就转化为网络运行问题。 本文为了研究网络节点的利用情况及网络的传输性能,在网络科学理论的研究背景下对城市道路网络和具有社团结构的网络进行深入研究,构建了三角网络和社团结构网络的模型,通过使用K-最短路径算法分析了在两种网络模型中节点的利用情况和网络传输性能,提出了恰当的K值能有效地增加节点利用率并提高网络传输性能。 由于三角网络与城市交通网规则、整齐的特点相似,构建三角网络模型作为研究对象。利用K-最短路径算法对三角网络进行OD仿真(交通出行),分析了网络节点的流量分布情况,通过路径长度和基尼系数判断节点利用情况和网络的传输性能,提出了采取增加出行时路径数目的策略能有效提高交通网络的吞吐量。 由于多数社团探测算法的时间复杂度为平方阶,而且这些社团探测算法需要事先确定社团数量的特点,提出了一个利用节点相似度及标签传递机制的社团探测算法。该算法的设计思路是利用网络的邻接矩阵得到节点之间的节点相似度,然后通过标签传递机制对节点相似度进行调整,最后由调整后的节点相似度对节点进行社团归类。与其他社团探测算法相比,该算法不需事先确定社团总数,同时时间复杂度和社团划分效果的综合表现较好。 同模拟交通网络模型一样,构建具有社团结构的网络模型作为仿真的研究对象,利用K-最短路径算法对模型进行OD仿真出行操作,分析网络节点的流量分布情况,通过判断节点利用情况和网络的传输性能,结果表明采用合适的K值能有效提高网络的吞吐量。
【图文】：

小世界特性、无标度特性和社团结构特性是网络科学中大部分网络具有的基本性质。不同领域的许多网络系统尽管在存在方式和用途上有多种相异的地方，但在其网络基本拓扑结构上，，却表现出了惊人的相似性。1)小世界网络小世界网络是Watts和Strogtz于1998年提出的一种网络模型[17】。该模型具体的构造算法如下：I构建规则网络：构建一个具有TV个节点的环形最近邻z1合网络，每一个节点都与该节点左右相邻的/C个节点之间有连边。II随机化断边重连：针对网络中的每条连边，固定边的任意一个端点，另一个端点以概率P选取网络中其他的节点进行连接。（网络中任意两个节点间的连边最多一条，同时每个节点不能连向自己）

图1-3具有社团结构的网络示意图团结构是一种揭示系统结构与功能间的对应关系、将复杂网络的认识简单化的有对具有社团结构网络的研究不但拥有很重要的现实意义，而且具备极其广泛的应目前已经被应用于组织成员的识别、结构管理等社会网络分析、蛋白质结构分析络分析以及基于文档、关键字查找等搜索引擎等领域。网络科学的基本模型则网络在网络科学研究的早期，研宄学者们普遍认为复杂系统中的多种因素可以使用一些网络来表示复杂系统中的联系。其中使用的比较多的规则网络是全局z1合网络、最网络和星型网络丨如图1-4所示，其中a图为全局z1合网络，该类型网络的任
【学位授予单位】：浙江工业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.02

【参考文献】

相关期刊论文 前2条

1 史定华;;无标度网络:基础理论和应用研究[J];电子科技大学学报;2010年05期

2 方锦清;汪小帆;郑志刚;;网络科学的理论模型及其应用课题研究的若干进展[J];复杂系统与复杂性科学;2008年04期

相关博士学位论文 前1条

1 吴建军;城市交通网络拓扑结构复杂性研究[D];北京交通大学;2008年

本文编号：2553717