【作者】 庄天舒；

【导师】 张宏莉；

【作者基本信息】 哈尔滨工业大学 ， 计算机科学与技术， 2007， 硕士

【摘要】 Internet拓扑特征化研究是认识Internet的必然过程,是在更高层次上开发利用Internet的基础。然而,目前对Internet拓扑的了解还不够充分,这并不只是一个计算机科学问题,而是根源于缺少一个对大规模真实网络进行特征化的科学框架。本文基于最近迅速发展的复杂网络理论来系统的研究大规模IP网络的拓扑特征。复杂网络理论源自图论与统计力学之间的交叉,其主要方向之一是对所研究结构进行拓扑特征化。本文给出了复杂网络的图论特征方法,介绍并分析了多项测度,包括度分布、度相关性,聚集性,核数,介数、群落识别相关测度等等。本文从这些测度中分类出两大类测度——度相关的和路径相关的测度。根据测度定义,本文给出了计算主要特征的相关实现,计算了包括度分布熵、相称系数、传递性、介数分布等等在内的拓扑特征。本文提出了根据图自身性质的基于块—割点树的加速算法,可减少计算消耗35%~54%。本文运用上述理论与实现对中国网络和Internet的IP级拓扑进行了全面的特征化分析,揭示了多项拓扑内在规律。与CAIDA的skitter进行了全面的比较,发现skitter丢失了大量边缘网络节点,大多数特征定性上都是相似的,但定量上不同,特别是距离相关测度。本文提出了测度相关性分析技术,分析了五个主要节点相关测度之间的相关性,发现顶点度的低度部分与其他测度存在较直观的联系,而高度分布相关性较弱。更多还原

【Abstract】 Internet topology characterization research is the necessary process of understanding Internet, and it is the base for a more deeply development of Internet. It is not only a problem of computer science, but there is a lack of scientific frame class for a large scale real network. This paper bases on complex network theory which is developing fast recently, and it researches topology characteristics of large scale IP networks by the numbers.Complex network research originated from graphical theory and stastical mechanics, and one of its main goal is to topologically characterize researching structures. This paper introduces complex network graphical theoretical characterizing methods, and analyzes many measurements, including degree distributing and correlation coefficients, clustering coefficients, coreness, betweenness, community identification and measurements. This paper classifies these measurements into two kinds: degree and path correlative measurements.According to the definition of these measurements, this paper presents many applications for different main characters, including degree distributing entropy, assortative coefficients, transitivity, betweenness distributing. This paper recommends an accelerate algorithm according to graph’s own property, and this method can reduce 35%~54% computational consume.This paper uses above algorithms and applications analyzing topological characteristics for IP level of China network and Internet, and finds a lot of topological internal rules. After a general comparison to CAIDA’s skitter data, we find that the skitter data loses many marginal network nodes, and most of characteristics are similar in qualitative analysis, but they are quantificationally different, especially distance measurements. Introducing measurement correlation analyzing techniques, this paper analyzes relativity of five main measurements, and finds low parts of node degree are correlative straight to others, and the high parts are less associated.更多还原