因特网拓扑作为因特网的基本特征,对于运行于因特网之上的各种协议和应用具有本质的影响。因特网拓扑研究对于许多其它因特网相关研究具有重要意义。因特网拓扑特征的系统化分析技术和dK特征序列是因特网拓扑研究领域的最新研究成果,对因特网拓扑的特征分析和建模研究起到了重要的推进作用,对其它相关研究领域(如复杂网络研究)也具有重要的借鉴意义。dK特征序列由一系列的拓扑特征组成,这些拓扑特征被称为dK特征。dK特征序列能够在不同的精度刻画拓扑图的特征,且精度随着d的增大而增加。这种用一系列的精度不断增加的拓扑特征来分析因特网拓扑的特性的方法,被称为系统化的拓扑特征分析技术。本文在dK特征序列的基础上深入研究了因特网拓扑的系统化分析技术,论文创新点如下:(1)提出了性能优于现有算法的dK图生成算法,并提出了用于增加dK图连通性的算法。dK图定义为dK特征与待研究的拓扑图的dK特征相同的拓扑图。由于dK特征序列具有强大的拓扑特征描述能力,因此研究dK图生成算法对于因特网拓扑研究具有重要意义。本文针对现有dK图生成算法存在的主要问题(精度低和生成的拓扑图连通性差),提出了一种改进的2K图生成算法以及一种3K图直接生成算法。实验结果表明,本文算法在精度和生成的拓扑图的连通性方面明显优于已有算法。本文进一步提出了一种基于重连的增加dK图连通性的算法,实验结果表明,该算法能够显著减少各种dK图生成算法生成的拓扑图的非连通子图的个数。(2)提出了用于计算关系标注的AS(自治系统)拓扑图的最短路径和Betweenness的快速算法。由于AS之间存在复杂的路由关系,因此因特网AS级拓扑通常用一张部分有向图(partially directed graph)表示,图中的边标注了AS之间的路由关系。在这样一个部分有向图中,传统的计算拓扑图的最短路径和Betweenness的算法将不再适用。本文基于宽度优先搜索(BFS)算法提出了一种计算关系标注的AS拓扑图中最短路径和Betweenness的快速算法。算法的时间复杂度为O(nm),优于现有的时间复杂度为O(n3)的算法(其中n为拓扑图节点个数,m为拓扑图边个数),因此更适合于因特网AS级拓扑研究。(3)研究了关系标注的AS拓扑图的系统化分析方法。dK特征序列的定义是基于无向图的,因此不能用于关系标注的AS拓扑图的特征分析。本文提出了一种用于系统化分析关系标注的AS拓扑图的特征序列:dK′特征序列,dK′特征序列在dK特征序列的基础上增加了边类型的描述信息。本文进一步通过对dK图生成算法进行扩展,提出了dK′图生成算法。实验结果表明:dK′特征序列具有与dK特征序列类似的系统化拓扑特征描述能力;当d=3时,3K′图生成算法生成的拓扑图能够在各种重要的拓扑特征方面与关系标注的AS拓扑图保持一致。(4)提出了一种新的简洁的系统化拓扑特征分析方法。dK特征序列存在状态空间膨胀的问题,随着d的增加,拓扑图中节点个数为d的子图个数迅速增大。这个问题导致dK图生成算法比较复杂,在d>3的情况下没有有效的dK图生成算法。本文定义了一种邻接图的概念,并在此基础上提出了一种新的特征序列:dM特征序列。本文进一步提出了dM图的生成算法,与dK图生成算法相比该算法步骤更简单,而且该算法对任意的d都适用,因此更适合于大规模拓扑图的系统化特征分析研究。实验结果表明dM特征序列具有与dK特征序列相同的拓扑特征描述能力:随着d的增加,dM特征的描述精度不断增大;2M图已经能够在各种重要的拓扑特征方面与原始拓扑图保持一致。