互联网宏观拓扑演化及谱特征研究

论文摘要

互联网具有极强的复杂性,因此要通过研究互联网的拓扑进而改进互联网的设计,改善互联网的性能,就必须对互联网的宏观拓扑进行研究。近年来人们在该领域取得了长足的进展,发现了许多隐藏在网络内部的特征规律。但目前的相关研究工作或是数据统计的空间量级较小、时间跨度较短,或是研究数据时间较早,或是没有与其他领域相结合、度量方法较为简单,所以需要做更为全面的进一步研究。本文研究工作基于CAIDA (The Cooperative Association for Internet Data Analysis) Ark项目授权的海量数据,数据采集时间为2007年9月至2011年2月。统计AS级互联网宏观拓扑的多种宏观特征,并研究各特征之间的关系,进而通过富人俱乐部及聚类系数、度的PDF幂律分布及CCDF幂律分布研究网络的连通性及幂律性。与早期研究结果有所不同的是,发现网络的整体连通性增强。论证了核数对度量拓扑层次性的意义,说明核数可以用来更精确的刻画网络拓扑层次。对网络核数进行演化,较早期研究,随时间变化网络层次的加深明显；对节点核分布进行研究,发现在核数较低区域核分布符合幂律性；进一步研究节点度与核的关系、核相同的节点度分布,指出最高核节点对网络的重要影响作用；不同核数节点集之间的连接体现网络各层次间的关联,对核间连接进行研究同样发现网络最高核是网络的真正核心。将代数理论与网络拓扑结构性质结合,对网络的谱特征进行研究。在论述了复杂网络图谱理论后,详细分析了邻接谱与Laplace谱。论证了连接偏好导致网络中节点之间的连接存在某种相关性,并研究了网络拓扑的度相关性。提出度相关系数可调算法对网络进行重连,进而研究了度相关系数在同配网络和异配网络下分别对邻接谱和Laplace谱的影响。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 互联网拓扑研究的背景及现状
• 1.2 互联网拓扑研究的重要性
• 1.3 课题的提出
• 1.4 课题的可行性研究
• 1.5 本文的组织结构
• 第2章 互联网宏观拓扑研究基本方法
• 2.1 互联网宏观拓扑研究的基本原理
• 2.1.1 互联网宏观拓扑的定义
• 2.1.2 互联网拓扑研究的方法
• 2.2 拓扑数据的获取
• 2.2.1 数据来源
• 2.2.2 数据预处理
• 2.3 主要拓扑特征量
• 2.3.1 幂律特性
• 2.3.2 层次性
• 2.3.3 聚集特性
• 2.4 网络拓扑结构模型
• 2.4.1 ER网络模型
• 2.4.2 BA网络模型
• 2.5 本章小结
• 第3章 互联网宏观拓扑特征演化规律研究
• 3.1 常规特征演化规律研究
• 3.1.1 网络规模演化
• 3.1.2 平均度演化
• 3.1.3 最大度及高度值节点演化
• 3.1.4 叶子节点及小度值节点演化
• 3.1.5 网络平均路径长度演化
• 3.2 网络拓扑连通性
• 3.2.1 富人俱乐部
• 3.2.2 聚类系数
• 3.3 网络拓扑幂律性
• 3.3.1 PDF幂律分布
• 3.3.2 CCDF-degree幂律分布
• 3.4 演化规律研究结果及应用
• 3.5 本章小结
• 第4章 互联网宏观拓扑层次性研究
• 4.1 核数的层次含义
• 4.2 网络核数演化
• 4.3 核的幂律性质
• 4.4 核数与度值的关系
• 4.5 核间连接分布
• 4.6 层次性研究结果及应用
• 4.7 本章小结
• 第5章 复杂网络谱特征研究
• 5.1 网络谱概述
• 5.2 度相关性分析
• 5.2.1 度相关系数
• 5.2.2 度相关与网络拓扑结构
• 5.2.3 互联网拓扑度相关性
• 5.3 基于度相关性的谱特征分析
• 5.3.1 度相关系数可调算法
• 5.3.2 度相关对谱的影响
• 5.4 度相关与谱特征应用
• 5.5 本章小结
• 第6章 总结与展望
• 6.1 本文工作及贡献
• 6.2 不足与展望
• 参考文献
• 致谢
• 攻读硕士期间发表的论著