Internet拓扑结构的静态概率模型研究王林1,2,戴冠中2摘要:近年来,许多学者对Internet的拓扑结构进行了研究,发现了幂律(Power2Law)规律,然而这些研究基本上针对的是Internet拓扑的局部性质。该文从Internet拓扑的一个参数(度秩指数)出发,定义了Internet拓扑结构的一个静态概率模型。利用静态概率模型,对文中所提出的Inter2net拓扑中具有整体意义的两个重要性质(连接率和吸引率)进行了深入研究。通过理论研究和仿真研究,获得了下列成果:①发现了Internet中的一个新的幂律(即连接率满足幂律),并且相关系数超过99.3%。②发现了Internet中吸引率与Internet中幂律之间具有的内在联系;③关键词:Internet拓扑结构,自治系统(AS)核心,幂律,静态概率模型文章编号:100022758(2005)0320341206中图分类号:N94,TP1,TP3文献标识码:A对于Internet这样的开放复杂巨系统[1],深入研究其拓扑结构,对于其建模、分析、仿真和网络信息安全等均有十分重要的意义。将Internet看成一个图G=G(V,E)。它可以分解成相互连接的若干子网(见图1),每个子网具有独立的管理机构和独立的路由政策,这样的子网称为自治系统[2](AutonomousSystem),简称AS。研究Internet的拓扑结构有2种方法:①将Internet中的路由器看成图的结点,所得到的图称为路由器层的图(router2level);②将每个自治系统看成一个结点,而将自治系统之间的连接(基于BGP协议[2])看成边,所得到的图称为自治系统层上的图,简称AS层的图(AS2level)。在没有获得关于Internet的结构数据之前,人们对于Internet拓扑结构的了解很少[3,4]。这期间,研究者们将Internet的拓扑结构抽象成一个均质网络的概率模型,其中,图的结点的度服从Poisson分布[5]。近年来,许多研究者由Oregonroute2viewsAssociationforInternetDataAnalysis,http://www.caida.org)来获得有关路由器层的数据[6]。这使Internet拓扑结构的研究工作取得很大进展[3,4,7],发现无论在路由器层或在AS层的Inter2net拓扑图中,都广泛地存在幂律,而不是Poisson分布。图1Internet拓扑结构应当指出,这些幂律仅刻划了Internet拓扑结构的局部性质,由此还不能看到Internet拓扑结构的整体性质[8]。作者在文献[9]中引进了Internet的子图的连接率概念,并发现连接率也满足幂律。另一方面,CAIDA的研究者通过将Internet中A收稿日期:2004207214作者简介:王林(1963-),西安理工大学教授,现为西北工业大学在职博士生,主要从事复杂网络方面的研究。·342·西北工业大学学报第23卷层图的结点的连接关系实际描绘出来,发现在In2ternet中存在AS核心[10](AScore),其它一些研究者也发现了同样的事实。但他们尚未对AS核心作仿真或理论方面的研究,尤其没有发现AS核心和幂律之间的关系。本文通过对连接率和吸引率的仿真和理论两个方面的研究,从而对AS核心问题,获得了若干研究成果。事实上,连接率、吸引率以中没有一条边。因此,连接率LG在一定程度上描述了图G的整体性质。提出的吸引率的定义如下:定义2给定一个图G=G(V,E),设V1<V为该图结点集的子集,E1表示只有一个结点在V1中的所有边的集合,E′1表示2个结点均不在V1中的所有边的集合。定义V1的吸引率为|E1||E′|≠01|E1|+|E′1|1AV1(4)|E′1|=0子集V1的吸引率描述了V1对于V1以外的结点的吸引程度,吸引率越大,与V1中结点相连接的V1以外的结点就越多。当V1的吸引率为1时,E′1为0,则V1以外的结点只与V1中的结点有边相连,而V1以外的结点之间没有任何连接;而当V1的吸引率为0时,则V1是孤立的。因此,V1的吸引率描述了V1成为图G的连接核心的程度,这在一1静态概率模型的提出设n为Internet拓扑图的结点总数,d(d1,=,dn)为一正实数序列,表示与Internet拓扑图d2,的结点(v1,v2,,vn)的度成正比的一组参数值,而结点的度表示与该结点相连接的边数。若结点按照其度的大小由大到小进行重新排列,则其结点的度是其下标的幂函数[4],该幂函数的幂指数α称为该拓扑图的度秩指数。于是可取参数值di满足实际数据的来源3di=Ci-α(0.5<α<1)(1)在本文提出的静态概率模型中,Internet上任意两结点vi与vj之间存在边的概率设为本文是在Internet的AS层上对Internet的拓扑结构进行理论和仿真两个方面的研究,因此本文的实验数据只包...