复杂网络拓扑特性的理论与应用研究

《复杂网络拓扑特性的理论与应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级注1UDC学位论文复杂网络拓扑特性的理论与应用研究（题名和副题名）冯旻昱（作者姓名）指导教师屈鸿教授电子科技大学成都（姓名、职称、单位名称）申请学位级别博士学科专业计算机软件与理论提交论文日期2018.04.15论文答辩日期2018.06.04学位授予单位和日期电子科技大学2018年06月答辩委员会主席评阅人注1：注明《国际十进分类法UDC》的类号TheTheoreticalandAppliedStudyonTopologicalCharacteristicsofComplexNetworksADoctoralDis

2、sertationSubmittedtoUniversityofElectronicScienceandTechnologyofChinaDiscipline:ComputerSoftwareandTheoryAuthor:MinyuFengSupervisor:Prof.HongQuSchool:SchoolofComputerScience独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研宄工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方夕卜，论文中不包含其他人已经发表或撰写过的研宄成

3、果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研宄所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名＇：Ｖｋｌ日期：ｗ０年《月日＾论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。ｊ（保密的学位论

4、文在解密后应遵守此规定）、作者签名：＼导师签认名：备人曰期：年月曰＆７…一）３摘要摘要随着21世纪的悄然到来，人类科学日新月异，简单和随机系统已然不能满足科技高速发展的需求。为了缓解该矛盾，复杂系统作为一门新兴学科，不仅从科学技术上指明了未来的发展方向，而且给科研人员提供了一种非线性的、自适应性的研究思路。在复杂系统的研究之路上，复杂网络的出现使得复杂性科学在各学科大放异彩，并通过数十年的发展逐步形成了网络科学这门学科。其中，复杂网络的拓扑特性研究是其核心问题，是完善网络科学的理论和拓广其应用领域不可或缺的

5、部分。本文以复杂网络中拓扑特性的理论与应用为研究课题，充分利用概率论、微积分、数值分析等数学工具，重点探讨了不同环境下网络的建模、度分布和规模分布的求解、平均路径长度的应用等等问题，主要研究内容分为四部分：1.基于泊松分布的演化网络的建模及其度分布和度指数分析。为了探索节点生成机制对网络拓扑的影响，本章节分别提出基于齐次泊松分布、非齐次泊松分布与生灭过程的网络模型，这三类模型均可被视为典型的无标度网络，并用于拟合现实网络。这三类网络的度分布和度指数分析是这部分研究的重点，并通过数值分析方法拟合求解度指数、分析网络鲁棒性，证实网

6、络具备无标度特性。2.构建具有可变加边的演化网络模型，在多变量的基础上推导得到全新的亚态分布。在大量观测现实网络的基础上，该部分工作从具有多变量的复杂网络中求解得到亚态分布，用于更精确地拟合度分布，并且给出了该分布的数字特征分析。该分布可应用于拟合现实中常见的数据，例如社交网络的度分布和个人财富分布。基于理论演化网络度分布和实际分布的拟合实验证实了该分布拟合的精准和广泛。3.构建基于生灭过程和排队系统构建的网络模型，并分析其规模特性。为了解决传统网络模型无限增长以及网络规模不收敛的问题，本章构造了一种基于生灭随机过程的演化网络

7、，其节点不断增加的同时也有一定概率消亡，并用排队系统加以诠释该网络。在此基础上，本章推导出了该网络的规模分布解析式，并证明其与时间无关。理论对比实验和人口数据拟合都验证了该网络的规模平稳性，并将其应用于人口分析上。4.提出了基于状态转移矩阵的复杂网络最大似然度搜索算法。为了实现快速搜索和消息传递，本章提出一种具有k个遍历器并行搜索的算法。该算法I摘要不仅具备并行性和高效性，而且充分利用网络的拓扑特性，使其适合于多种不同类型的复杂网络。离散马氏链及状态转移矩阵被用于分析该算法的可行性。与其他算法的对比实验也证实该算法具有有效性和

8、高效性。关键词：网络科学，拓扑特性，无标度网络，概率论，度分布，亚态分布，网络规模，路径搜索算法IIABSTRACTABSTRACTWiththequietcomingofthe21stcentury,thesciencesforthehumanracearechanging