CHP3 复杂网络理论及应用3.ppt

《CHP3 复杂网络理论及应用3.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章Internet拓扑特性及建模3.1引言3.2Internet的拓扑特性3.3随机图产生器3.4结构产生器3.5基于连接度的产生器3.6多局域世界模型3.7各类模型的定性比较3.1引言路由器层面：自治系统(AutonomousSystem)层面：在互联网中，一个自治系统(AS)是一个有权自主地决定在本系统中应采用何种路由协议的小型单位。由单一行政部门所管理的子网络，可由高达数以百计的路由器组成。节点为路由器，边为路由器之间的物理连接（如光纤）（a）路由器层（b）AS层自治系统AS间采用BGP协议BGP发言人BGP发言人BGP发言人BGP发言人BGP发言人AS1AS3AS2

2、AS5AS4针对AS层面的Internet拓扑结构——Internet拓扑产生器（网络拓扑模型）第1代：20世纪80年代随即图产生器第2代：20世纪90年代结构产生器第3代：2000年以来基于网络节点度的产生器3.2Internet的拓扑特性AvisualizationofthenetworkstructureoftheInternet本节大部分关于Internet拓扑特性的分析是基于Oregon的数据，由NLANR每天采集一次BGP路由表的信息收集而成。Skitter：由CAIDA每天采集连续的基于Trace-route的Internet拓扑测量值。WHOIS：是一系列包含关

3、于网络运行者重要信息的数据库；是一个用来查询域名是否已经被注册，以及注册域名的详细信息的数据库（如域名所有人、域名注册商、域名注册日期和过期日期等）。人工维持的，不能及时更新。3.2.1幂律分布Faloutsos三兄弟dvrvR节点出度与该节点等级的R次幂成比例dv是节点v的度，rv是将网络中节点按度降序排列节点v的序列号，R是秩指数常数。DddD度大于d的节点在网络拓扑中所占百分比与节点出度d的D次幂成比例Dd表明度大于d的节点在整个网络中所占的百分比，D是度指数常数。可以推得R=1/D。ii特征值λi与其次序i的ε次幂成比例.i为网络对应的连接矩阵的特征值，i为

4、将特征值按降序排列时的序列号。特征值指数和连接度指数D间存在近似关系0.5D。P(h)hH(h<<时)P(h)为距离不超过h的节点对的数目(也称为hop内的节点对的数目)，H是hop指数常数。c=N+2M,N、M和δ分别为网络节点数、边数和直径四种幂率指数的演化情况：3.2.2层次性Internet可以被看作是由大量的相互连接的AS系统组成每个AS系统可以被看作Stub域或Transit域Stub域由一些相互连接的LAN组成Stub域承载域内的通信量Transit域一般是WAN或MANTransit域有效地连接Stub域是区域或国家层主干网络看作客户。客户-供应商关系

5、每个AS可以被看作属于特定的层次(Tier)最高层内的AS属于Transit域，称为Tier-1供应商较低层次的Transit域或Stub域依赖于其上层的Transit节点与网络内的其他域进行通信；也可以通过同一层内的对等关系的其他Transit域发送信息各层的平均度：Tier1：614.29Tier2：19.30Tier3：6.93Tier4：4.303.2.3富人俱乐部特性3.2.3富人俱乐部特性Internet中少量节点具有大量的边，这些节点称为“富节点(richnodes)”；它们倾向于彼此之间相互连接，构成“富人俱乐部(rich-club)”；(r/N)表示网络中前

6、r个度最大的节点之间，实际存在的边数L与这r个节点之间总的可能存在的边数r(r-1)/2的比值。如果(r)=1，那么前r个最富有的节点组成的富人俱乐部为一个完全连接的子图。RCC(rich-cludconnectivity)，只考虑节点度排名靠前的节点连接程度，是聚集系数的一种特殊情况。它反映了互联网拓扑层次性，描述了核心层的连接情况。richclubconnectivity对于所有具有给定度的节点的邻居节点的平均度分布P(k’

7、k)表示度为k的节点连接到度为k’的节点的概率。Internet统计结果可见，一个节点的度越高，它的邻居的平均度就越低。3.2.4异配性同配性系数(

8、assortativitycoefficient)ji和ki分别为第i条边的两个端点的度数，M为网络中边数。若r>0，则网络是同配的(assortative)；-正相关的若r<0，则网络是异配的(disassortative)。-负相关的若r=0，则网络无相关性技术网络一般是异配的，包括AS层面的Internet网络社会网络通常是同配的3.2.4异配性Averageneighborconnectivityasafunctionofnodedegree3.2.5核数和介数核数（coreness