互联网拓扑分析发展

1在自然界和人类社会中存在各种各样的网络，像作为基础设施的铁路、公路、航空等各种交通网、电力网，近年来广泛应用的技术网络万维网(www)、对等传输(P2P)网络、互联网等。一个典型的网络由许多节点和连接节点的边组成，通常节点代表真实世界中的个体或组织，而它们间的关系用边来表示。例如，在互联网中，可以用点来表示自治系统(AS，autonomoussystem)，边来表示其间的连接关系，即形成自治系统级的网络拓扑；如果把互联网中的路由器看成节点，而路由器间的连接关系看成边，这样就形成了路由器级的互联网拓扑。

数学家和物理学家在研究网络的时候，为了抓住本质，通常进行一定的抽象，表现在既不关心节点的特定物理位置、大小，也不在意边的长短、曲直、相交与否，只关心节点和节点间是否相连。例如，欧拉在解决哥尼斯堡七桥问题的时候，虽然当时(1736年)讨论长短大小的几何学是主流，而不考虑长短大小、不牵涉量计算的情形几乎没人研究，但他却撇开研究对象的长短、大小、面积、体积等度量性质和数量关系，把2座小岛和河的两岸分别抽象成4个点，而把7座桥抽象这4个点之间的连线，开创了拓扑研究的先河。当人们把网络抽象成这种不依赖于节点的位置、大小和边的具体形态，所得到的性质就成为网络的拓扑性质，相应的结构称作网络的拓扑结构。

网络结构和功能是网络理论研究的核心内容。

其中网络结构通常用网络的统计特征(如度分布、聚集系数、平均最短路径、度一度关联性等)来刻画，网络功能由网络上的动态变化过程来反映。这两者并非相互独立，而是存在必然的本质联系。通常结构决定功能，功能反过来影响网络结构的演化。例如，交通网中不同的结构决定了网络的容量有很大的不同，而交通量的增加也可能引起人们增加路径，从而影响网络的演化。

2大规模复杂网络拓扑结构分析与其他学科的关系

网络拓扑结构知识需要通过拓扑结构分析获得。当前网络科学关心的主要对象是大规模复杂网络，如互联网。而网络拓扑结构分析方法是网络科学的核心内容。从学科角度看，这方面的研究要以传统统计学、图论、统计力学、随机过程等学科为基础。因为复杂网络规模巨大，网络结构又具有多样性、动态性、复杂性，必须经过统计处理；而图论提供了简洁精确的方法来描述网络，已成为研究人员的共同语言和必要工具。近年来，国内外已出版了相关的一些文章和专著。

但是网络拓扑结构分析方法与传统学科中的方法还是有很大不同。传统的统计学侧重于对属性数据的分析，网络结构的分析方法则通常侧重于对关系数据的分析。属性数据是指节点或一组节点自身拥有的数据。关系数据是指节点间关系、社团(eOlllmullity)问关系、整体层次、块层次间的关系，是2个或更多节点共同拥有的。关系数据与属性数据是不同的分析对象，其分析方法也有很大的差异。

经典图论的研究对象通常只有几个或几十个节点，数学家们可以对其做精确的网络优化，而复杂网络结构分析方法处理的节点数目常常为数千、数万、数亿甚至更大规模，因此，需要从不同尺度作抽象。而过分抽象可能导致所得结论与实际情况相差甚远，从而引发各种争论，这就要求研究者需要根据实际情况从不同尺度来看问题。常常可以发现，一个尺度上发现的结论在另一个尺度上并不一定成立。如互联网自治系统级拓扑的度分布满足幂律【l，8惟1，而在互联网路由器级拓扑中，由于路由器接口数目的限制，度分布显然不会满足幂律。由于不同学科的研究者看问题的尺度不同，最近就引起了激烈的争论，计算机网络领域的研究人员对网络科学领域的研究结论产生异议就是一例【9J。这好比拿《庖丁解牛》中的庖丁与普通厨师的工作做比较，庖丁是在反复实践的基础上，掌握牛的结构(即事物的规律，现在的说法就是一个“科学问题”)，再去指导实践(“解牛”)，而普通厨师则不必做庖丁的工作，只要把牛肉做成牛排、做成菜就可以直接满足用户需要了，更多的是一个“技术问题”。

也就是说，两者是两个层面的工作，但都是有益的工作。网络结构分析在社会网、技术网、生物网的研究和实践中都已发挥了重要作用，互联网就是一个典型的例子。作为一个真实网络，互联网从最初的4个节点，发展成为当今世界的信息基础设施，其应用的深入发展和无处不在的广泛性深刻地改变了人们的工作、生活和学习方式，己成为一个名副其实的具有复杂结构的巨大系统。对互联网拓扑结构研究所蕴含的科学意义和应用价值正受到学术界、应用部门和军事部门的普遍重视。下面主要对互联网拓扑结构分析的成果及其应用做比较详细的说明。

3互联网拓扑结构特征

千差万别的网络都可以通过图来描述，邻接矩阵和邻接表包含了网络的所有信息，是2种传统的图表示方法，但都不能直观地告诉人们给定网络的特征。由于网络规模常常很大且结构复杂，为了刻画网络的性质，需要通过一些概念、统计的特征量和度量方法来直观地表征一个网络的主要结构特点。常用的刻画一个网络特征的指标有：节点度分布、平均路径长度、聚集系数、度一度关联性系数、介数、核数等。近年来，人们通过对互联网拓扑结构的分析，发现了多项互联网的拓扑结构特征。

3．1幂律的发现

在互联网拓扑研究中，1999年法鲁托斯(Faloutsos)等人对美国应用网络研究国家实验室(NLANR，nationallabforappliednetworkresearch)1997年至1998年的3份BGP(bordergatewaypro．toc01)数据以及1995年的一份traceroute眦探测数据进行分析，发现了互联网拓扑中存在4条幂律。论文发表在SIGCOMM’99和《计算机通信评论(ComputerCommunicationReview)))…上。这个实验结论所指的幂律是近似幂律。这一结论最重要的是在本质上揭示了节点间的差异，表明与原先占主导地位的随机网络【l州根本不同的是，在自治系统级拓扑中，少数节点有大度值，而多数节点的度值小。