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

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

2、P 发言人,BGP 发言人,BGP 发言人,AS1,AS3,AS2,AS5,AS4,针对AS层面的Internet拓扑结构Internet拓扑产生器（网络拓扑模型） 第1代： 20世纪80年代 随即图产生器 第2代： 20世纪90年代 结构产生器 第3代： 2000年以来 基于网络节点度的产生器,3.2 Internet的拓扑特性,A visualization of the network structure of the Internet,本节大部分关于Internet拓扑特性的分析是基于Oregon的数据，由NLANR每天采集一次BGP路由表的信息收集而成。,Skitter： 由CAID

3、A每天采集连续的基于Trace-route的Internet拓扑测量值。 WHOIS： 是一系列包含关于网络运行者重要信息的数据库；是一个用来查询域名是否已经被注册，以及注册域名的详细信息的数据库（如域名所有人、域名注册商、域名注册日期和过期日期等）。 人工维持的，不能及时更新。,3.2.1 幂律分布,Faloutsos 三兄弟,dv rvR 节点出度与该节点等级的R 次幂成比例 dv是节点v的度，rv是将网络中节点按度降序排列节点v的序列号，R是秩指数常数。,Dd dD 度大于d 的节点在网络拓扑中所占百分比与节点出度d 的D 次幂成比例 Dd表明度大于d的节点在整个网络中所占的百分比，D是

4、度指数常数。可以推得R=1/D。,i i 特征值i 与其次序i 的次幂成比例. i为网络对应的连接矩阵的特征值，i为将特征值按降序排列时的序列号。特征值指数和连接度指数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域承载域内的通信量 Tra

5、nsit域一般是WAN或MAN Transit域有效地连接Stub域 是区域或国家层主干网络,看作客户。 客户-供应商关系,每个AS可以被看作属于特定的层次(Tier) 最高层内的AS属于Transit域，称为Tier-1供应商 较低层次的Transit域或Stub域依赖于其上层的Transit节点与网络内的其他域进行通信；也可以通过同一层内的对等关系的其他Transit域发送信息 各层的平均度： Tier1：614.29 Tier2：19.30 Tier3：6.93 Tier4：4.30,3.2.3 富人俱乐部特性,3.2.3 富人俱乐部特性,Internet中少量节点具有大量的边，这些节点

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

7、的节点 连接到度为k的节点的概率。 Internet统计结果可见， 一个节点的度越高， 它的邻居的平均度就越低。,3.2.4 异配性,同配性系数(assortativity coefficient) ji和ki分别为第i条边的两个端点的度数，M为网络中边数。 若r0，则网络是同配的(assortative)；-正相关的 若r0，则网络是异配的(disassortative)。-负相关的 若r=0，则网络无相关性 技术网络一般是异配的，包括AS层面的Internet网络 社会网络通常是同配的,3.2.4 异配性,Average neighbor connectivity as a functio

8、n of node degree,3.2.5 核数和介数,核数（coreness） 一个图的k-核(k-core)是指反复去掉度小于或等于k的节点后，所剩余的子图。 若一个节点存在于k-核，而在(k+1)-核中被移去，那么此节点的核数(coreness)为k。 度为1的节点的核数为0。 节点核数中最大值称为图的核数,节点核数在某种程度上说是比节点度数更反映关联性的度量指标，可以表明节点在核中的深度。 一个节点的度数很高，它的核数也可能很小。这说明其关联并不紧密，与邻居节点的连通性容易破坏。,K=0,K=1 反复去掉度=1的节点,Internet 节点的度数与核数的关系： 当度数较小时呈现幂率关

9、系 当节点度数大于100时 核数基本保持不变,3.2.5 核数和介数,Internet的节点核数与度数之间的关系,介数(betweenness centrality) 通常分为边介数和节点介数两种： 节点介数定义为网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例. 边介数定义为网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例. 介数反映了相应的节点或者边在整个网络中的作用和影响力，是一个重要的全局几何量，具有很强的现实意义。 节点介数衡量了通过网络中该节点的最短路径的数目,反映了节点在网络中的枢纽性,节点介数越大,说明这个节点的枢纽性越强,删除这样的节点会造成大量节点

10、对之间的最短路径变长; 边介数定义为在网络的所有最短路径中,通过某条边的最短路径的条数,类似地,边介数也同样反映了该边在网络中的枢纽性. 例如，在社会关系网或技术网络中，介数的分布特征反映了不同人员、资源和技术在相应生产关系中的地位，这对于发现和保护关键资源、技术和人才具有重要意义。,介数 一个节点的介数衡量了通过网络中该节点的最短路径的数目。 Internet拓扑数据： 节点的度数和介数呈现 明显的幂率关系。,Internet的节点的标准化介数与度数之间的关系,网络拓扑生成,网络拓扑生成，是通过对现实网络进行建模，然后利用模型生成网络拓扑的方法。 它与网络拓扑发现是不同的，后者是从一台设备出

11、发，探测周围的网络拓扑的方法。 目前的网络拓扑生成模型主要是建立在随机模型、层次结构模型或幂律模型的基础上，常用的拓扑生成方法/模型有Waxman，Tiers，Transit-stub，BA，Inet等。其中Waxman为随机模型，Tiers和Transit-stub建立在层次结构的基础上，BA和Inet都是基于幂律模型。Brite和Inet则是典型的拓扑生成器 拓扑生成器是拓扑生成算法的软件实现，是生成拓扑的工具,随机型，即认为网络拓扑图处于一个完全无序的状态,在大尺度上是均一的最早的随机模型是由Waxman提出来的。Waxman认为节点之间的连接概率与其距离相关,服从泊松分布,距离越近,概

12、率越大。 层次型，来自对网络结构所具有的层次特征的认识，在同一层上的节点出度接近，不同层间节点出度差别很大。对同一层上的节点布置借用Waxman模型方法。 幂律型，1999年，Faloutsos等人对NLANR(National Lab for Applied Network Research)在1997-1998年间的3份BGP数据以及1995年的一份tracerouter测量数据进行分析,发现网络拓扑中存在着幂律规律。,3.3 随机图产生器,步骤： 在nn的平面上均匀放置N个节点； 两节点u和v之间建立边的概率为： 0, 1, d(u,v)是节点u和v之间的欧氏距离， 为平均连接度，L是图

13、中相距最远的两节点之间的欧式距离, 决定了边的平均长度。 如果增大，则边的生成概率增大，使得最后生成的图中边的数目增加； 如果 增加，则使得最后生成的图中较长的边相对于较短的边出现的概率增加。,随机图产生器,Waxman图中相距较远的两节点存在边的可能性较小，从而获得连通图的可能性也较小，通常用来对网络中的最大连通子图进行研究。,随机图产生器,频率fd表示网络中度为d的节点的个数，其对数分布如上图所示(5000个节点),由于在基于随机图的拓扑模型中,节点度数会随着节点数量的增加而增加,因此,随机图拓扑模型无法生成节点众多且节点平均度较小的网络.,3 .4 结构产生器,Tiers产生器 Tran

14、sit-Stub产生器,1 Tiers产生器,Tiers产生器用于表现广域网、中域网和局域网这三个层次间的关系及内部联系。 在Tiers中需要指定MAN和LAN的目标个数，其中LAN采用星形拓扑结构。,1 Tiers产生器,Tiers产生器的参数： WAN的个数Nw(一般把Nw设为1)； 每个WAN内的节点的个数SW； MAN的个数NMSW； 每个MAN内的节点的个数SM； 每个MAN内LAN的个数NLSM； 每个LAN内节点的个数SL； 节点总数：NSWNMSMNMNLSL。 WAN、MAN和LAN的内部网络冗余度，即一个节点到另一个相同类型节点的连接度，分别为RW、RM和RL。其数值通常分

15、别为3、2、1。 网络间的冗余度：WAN和MAN间的连接个数RMW；MAN和LAN之间的连接个数RLM。,1 Tiers产生器,Tiers产生器的步骤： 创建WAN。随机地在格子内放置节点，如果一个节点与另一个节点距离非常近，就将其舍弃。 当放置的节点的个数达到所需的目标个数后，在这些节点间建立最小生成树。 随机地检查每个节点，看它们是否满足RW。一个节点与对等节点间边的个数可能多于RW，则不需要再额外的边。如果与对等节点间少于RW条边，则需要添加它与网络中最近的节点的边。 类似地，可采用上述三步骤创建MAN网络。只是当两节点相距很近时，不需舍弃其中之一。 创建LAN网络。在每个LAN内随机选

16、择一个节点作为星形拓扑的中心，再将LAN内其他的每个节点与它之间建立一条边。若RL1则采用与步骤3类似的操作加边。,1 Tiers产生器,建立网络之间的连接： 将MAN连接到WAN上。从SW个WAN节点内随机选取NM个节点组成一个集合A，在A内的每个节点和从每个MAN内随机选取的一个节点x间建立边，所以，每个MAN就通过一条边连接在WAN上。 如果RMW1，那么,对于每个MAN，在MAN的另外一个节点（也可能会再是x）和x已经连接到A中的那个节点相距最近的节点间建立边。 与上述步骤相类似，将LAN连接到MAN。, ,1 Tiers产生器,以上步骤所建立的网络具有较大的网络直径：,2 Trans

17、it-Stub产生器,Transit-Stub产生器 产生具有三个层次的网络：Transit层、Stub层、LAN层 每层上的节点被限制在一个个的矩形空间内，其中不同层次的限制空间是不同的，最下层的LAN空间最小。,产生器有两组控制参数： 控制域的相对大小的参数： T：所有Transit域的个数，T1； NT：每个Transit域的平均节点个数，NT1； S：每个Transit域的平均Stub域个数，S1； NS：每个Stub域的平均节点个数，NS1； L：每个Stub域的平均LAN数，L1； NL：每个LAN的平均主机个数，NL1； 路由器节点和主机总是分别记为NR和NH，满足： NR=TN

18、T(1+SNS)，NH=TNTSNSLNL。,Transit-Stub产生器,控制域内和域间的连通性的参数： ET：一个Transit域节点和本域其他节点间边的平均数，ET2； ES：一个Stub域节点和本域其他节点间边的平均数，Es2； ETT：一个Transit域节点和其他Transit域之间边的平均数，ETT2； EST：一个Stub域和一个Transit域间边的平均数，EST1；每个Stub域至少和一个Transit域相连。 ELS：一个LAN域和一个Stub域之间边的平均数，ELS1；每个LAN域至少和一个Stub域相连。 所有参数必须足够大，使得层内和层间是连通的。,Transit

19、-Stub产生器,Transit-Stub产生器的建模步骤： 在指定的位置上生成所有的Transit域。可由任何一种随机方法（一般用Waxman方法）生成一张随机图，图中每个节点代表一个Transit域；并保证生成的图是连通的； 为每一个Transit域生成节点，将节点放置在环绕Transit域位置的子域内，使得Transit域平均含有NT个节点；在每个Transit域内连接边，使得此域连通，满足NT2,ER2. 在每一个Transit域中随机选取合适的节点作为Transit域间连接边的端点。,4. 为每一个Transit节点的Stub域选择合适的位置，并在这个位置周围生成相应Stub域的节点

20、，使每个Stub域内包含NS个节点，并将其连接起来。 5. 每个Stub域都要和Transit域相连。如果EST1，那么随机增加额外的从Stub域到Transit域的边，并从Stub域中选择一个节点与相应的Transit节点间加一条边。 6. 生成LAN，以星形结构设置主机节点。 7. 把每个LAN连接到相应的Stub节点的中心路由器上；若ELN1，则额外地增加中心路由器和Stub节点间的连接。,Transit-Stub产生器,Transit-Stub产生器 生成的节点度的频率fd的对数分布图：,3.5 基于连接度的产生器,1. 静态模型Inet（不考虑增长性） 在建模过程中采用非线性优先的连

21、接方式,通过初始放置所有节点,并对每个节点分配连接度,从而有层次地添加边。 尽管Inet 无法反应Internet 的动态变化,但对于某种特定规模的Internet 网络,能够较为真实地反应某些拓扑特性,如度分布遵循幂律分布,且最大度也接近真实网络的实际值等。 Winick 和Jamin提出Inet 模型可模拟3037 个节点的实际网络,即1997 年Internet 网络中的自治域数目,线性优先,回归模型,1. Inet,Inet 从用户那里获得节点个数N和N个节点中度为1的节点所占的比例k。 根据下式计算Internet从1997年11月份的节点个数增长到N所需的月份数t： N=exp(0

22、.0298t + 7.9842) 定义V1,Vtop3和V： V1是度为1的节点的集合， Vtop3为前三个最大度的节点的集合， V为除去V1,Vtop3中节点以外的其他节点。,代入t，根据F(d)=ecdat+b来计算V中节点的度分布，其中 ，a、b、c为常数。 Internet上度为1的节点所占比例基本上维持在30%左右。根据度秩指数增长律d=ept+qrR来计算Vtop3中节点的度分布，其中p、q为已知常数。 在度大于1的节点间构建一个生成树：令G为所要产生的图，初始为空集；不在G中的度大于1的节点i与G中的一个节点j相连的概率为： 其中 di为节点i的度，f(di)为度的频率。,按概率

23、公式，将V1中的kN个节点连接到G中的节点上。 从具有最大度的节点开始，连接G中仍剩余的自由度；在进行这些连接时，以概率公式随机的选取有着自由度的节点。,2.AB模型,动态模型BA: 是第一个演化网络模型,由Barabasi 和Albert 等人提出,现在拓扑建模研究中普遍将其作为无标度网络基本模型.BA 模型也是第一个从动态增长观点研究复杂网络具有幂律度分布特性的模型,并论证了生成无标度网络的两条重要机理:增长和择优。 但是,BA 模型对初始网络没有完全设定,只说明开始给定n0 个节点,但这n0 个节点间如何建边尚未讨论,而对于不同的初始网络,其后演化的结果网络并不相同; 并且,BA 模型的

24、算法可能导致重复建边.另外,优先连接也并不适用于所有出现幂律分布的情形,即便是对于某些无标度网络,利用优先连接来解释幂律的形成机理也很不合理.,AB 模型: 是Albert 和Barabasi 对BA 模型的修正, 该模型采用了线性优先的连接方式,通过概率增加点和边,并对内部边重新配置,保证了孤立节点建立新连接的可能性,逐步生成动态的AS 级拓扑模型. AB模型的连接度分布呈现幂律,且幂律指数接近真实网络.但是,它在聚类系数和特征路径长度上存在着很强的负相关性,其聚类系数严重低于网络实际值;并且,在最大连接度和次最大连接度等方面也都和实际网络存在较大的偏差.,AB模型的构建过程： 初始有m0个

25、孤立节点，每一步执行下面三个步骤中的一个： 以概率p增加m(mm0)条新的内部连接，即在已存在的节点间添加新的边：随机选取一个节点作为新的边的起点，边的另一个端点由以下概率决定： 重复此过程m次。,2. 以概率q重新配置m条边。随机选取节点i和连接到i的一个边lij，然后移走此边，以连接节点i和节点j的新边lij取代。每次根据公式的概率选取j来配置一条边，并重复此过程m次。 3. 以概率1-p-q增加一个新节点。根据以上公式所示概率分别与网络中已存在的m个节点连接。 其中，0p1，0q1-p； 概率公式采用(ki+1)，保证了孤立节点可以建立新边,3. BRITE 模型,BRITE 模型: 是

26、一种采用Waxman 概率与线性优先相结合方式的动态自治域级拓扑模型,其特点在于反映实际Internet 拓扑的多面性,如层次性和连接度分布等,对于不同的参数及不同的节点分布方式,BRITE 会产生不同的拓扑特性.另外,在建模过程中,它将当时已存在的Waxman, AB, Inet 都融合其中,并提供了更好的接口界面供仿真使用.,3. BRITE 模型,BRITE： BRITE期望能构建一个具有代表性、包容性和交互性的拓扑产生器： 代表性： 指期望反映Internet实际拓扑的多个方面，如层次性、连接度分布等 包容性： 指将多个已存在的拓扑产生器的功能融合在一个拓扑产生器之中 交互性： 指为广

27、泛使用的仿真应用提供更好的接口界面。,Table: Parameters of BRITE,Figure 6: Snapshot of BRITEs GUI main window,BRITE模型的构建过程： 在平面上放置节点； 在节点间建立内部边； 为每个拓扑元素设置属性； 以一定的形式输出此拓扑结构。 将平面分成HSHS个正方形，每个正方形被进一步分成LSLS个小的正方形，每个小正方形内最多分配一个节点。 平面上节点的随机放置：根据一致随机分布或者Pareto重尾(haevy-tailed)分布来分配每个大正方形内的节点个数。随机选取一个小正方形，在避免冲突的情况下，将一个节点放入其中。,

28、初始产生一个有着m0个节点的随机图作为主干，然后添加其他的节点。 如果参数IG(incremental growth)为0，则将所有节点一次全部放置在平面上，然后随机选取一个节点，与其他节点建立m条边； 如果IG为1，则每步添加一个节点，将其与网络中的已存在的节点间建立m条边，m越大拓扑越密。 4. 节点间连接概率的确定： 如果参数PC(preferential connectivity)为0，则按Waxman概率式 ，将所考虑的新节点v与节点i相连 如果PC为1，则v与i相连的概率为BA线性优先连接概率； 如果PC为2，则v与i相连的概率为： 其中，wi为Waxman概率。,当PC=IG=0

29、时，BRITE采用点随机分布所产生的拓扑即为Waxman拓扑； 当PC=IG=1时，BRITE所产生的拓扑在幂率指数和特征路径长度等方面最接近Internet的实际拓扑；,4.GLP模型,GLP模型 现实Internet中的节点比BA线性优先连接更倾向于连接到高连接度的节点上 广义线性优先(generalized linear preference, GLP)模型正是基于此观察而提出的，使其满足小世界性。 其建模步骤如下：,通过m0-1条边，将m0个节点连接起来，其中每一步执行下面两个操作中的其一： 以概率p0,1增加m条新边(mm0)，节点i被选作为一条边的端点的概率为： 其中(-, 1)是

30、一个可调节参数，它表明新节点或新边更倾向于受欢迎的节点。 以概率1-p增加一个新节点和此新节点的m条新边。系统中已存在的节点i被选中的概率(ki)由以上公式确定。,5. PFP模型,PFP模型 AS层Internet存在“富人俱乐部”现象，正反馈优先(positive feedback preferential, PFP)模型正是在研究此现象的基础上提出的。 PFP模型是基于新节点和内部边两个方面的交互增长、非线性优先连接两个机理构建的。 每一步除了将新节点连接到已存在的host节点上，还会将host连接到其他已存在的节点上，从而产生内部边。当选择所要连接的已存在的节点时，采用非线性优先连接概

31、率： 其中，0, 1,以概率p增加一个新节点，它与一个host节点建立一条外部边；同时，此host节点与网络中已存在的一个对等节点间建立一条新的内部边； 以概率q增加一个新节点，它与一个host节点建立一条外部边；同时此host节点与两个对等节点建立两条内部边； 以概率1-p-q将新节点连接到两个host节点上；同时其中一个host节点与一个对等节点建立一条内部边。 这里p0, 1, q0, 1-p,6. DP模型,DP模型 Internet的不同AS间具有消费者-供应商关系或对等关系，当存在其中一种关系时，彼此间建立边。 动态优先(dynamic and preferential, DP)模

32、型正是对这种情况的建模，模型建立的两个假设前提为： 两个存在的AS间，连接度较低的为消费者，连接度较高的为供应商 消费者决定将要连接到哪个供应商上，即由消费者来选择供应商,令i是消费者，将由它产生一个新边，ki是i的顶点度。V(ki+)是连接度较高的一组节点，为一常数。那么i选择j为供应商的概率为： 即i所选择的供应商的连接度总是要比ki+大，且在其中优先选择那些具有较大连接度的节点。,DP模型 以概率p在已存在的节点中产生一条新的内部边，即随机选择一个节点作为消费者，按概率将其连接到一个供应商上。,以概率1-p增加一个新节点和外部的m条边。由于Internet的平均连接度随时间连续变化，为了

33、反映此种情况，将p设为动态改变的。 设P(N)为“增加的内部边”与“增加的所有边”的平均比值，即P(N)=In/(N+In)，In=L-Nm， N是节点个数，L是边数，In是1997年11月后所增加的内部边数。可由下面公式计算得到边增加概率： 由经验数据，令p(0)=0.3, =1，便可以产生在一定程度上与Internet接近的拓扑结构。,7. TANG模型,TANG模型 由于BA模型不是专门针对Internet建模而提出的，将其应用于Internet拓扑结构会有很多不足： BA模型中没有叶子节点，而Internet中叶子节点比例约有30%； BA模型的幂率指数为3，而Internet的幂率指

34、数约为2.2； BA模型不能产生Internet中的密集核心；,TANG模型能很好地刻画以上拓扑特性，其构建基于两种思想： 增量加边(incremental edge addition, InEd) 超线性优先连接(super-linear preferential attachment, SliP)。 模型构建步骤如下： 起始有m0个节点，每一步增加一个新节点和m条边。一条外部边将新节点与已存节点相连，而在已存网络中增加m-1条内部边，其中已存节点被选作边的一端的概率为： 其中，0时为超线性优先连接。,GDTANG模型具体步骤（有向地理区域模型） 定义l个不同的地理区域，每一步增加一个新节点

35、和m条由客户指向供应商的有向边。根据分布Pl随机选择一个地理区域，再用一条有向边将新节点v与此区域中的一个节点i进行相连，其中选择节点i的概率为： 这里yi为节点i的出度 将v和i分别看作客户和供应商；,在已存节点间建立m-1条边，节点i被选作客户的概率为： 这里ki为节点i的入度 节点j被选作供应商的概率有上面第一个公式决定，其中这m-1条边中无向边的概率为p，边的两个端点在同地理区域内的概率为。令p=0.07，=0.5，便可得到在一定程度上与实际Internet值相接近的拓扑特性。,3.6 多局域世界模型,模型构造 在AS层面上，可以将Internet的层次分为国际连接、国家主干、区域网络

36、和局域网。区域网内的节点紧密连接使得此网络内具有很高的聚合系数，而这些高度聚合的区域网由国际连接或国家主干稀疏地相互联系在一起。 当一个新节点加入到一个区域网络时，它对其他区域网中的节点影响非常小，而它反过来主要受本区域中的节点的影响。 将区域网看作一个“局域世界”，那么整个Internet可以看作是由很多区域世界组成的。 MLW,模型构造： 起始为m个孤立的局域世界，在每个局域世界内部均有m0个节点、e0条边。,m0 e0,m0 e0,m0 e0,m0 e0,每一步随机地进行如下的一个操作： 新AS 的产生： 以概率p增加一个拥有m0个节点、e0条边的局域世界 新节点的产生： 以概率q将一个

37、新节点加入到一个已存在的局域世界中，它与同一个局域世界中的节点建立m1条边。 首先随机地选取一个局域世界，此局域世界中，新节点将要连接的节点由如下概率选取： 重复此过程m1次。,新链接的产生： 以概率r增加m2条边到一个选定的局域世界。 首先随机地选取一个局域世界，边的一端随机选取，另一端根据以上概率公式选定。重复此过程m2次。 链接的消亡：为刻画边的消亡，以概率s在一个选定的局域世界内去掉m3条边。首先随机选取一端，另一端由如下概率选定： 其中N(t)为局域世界内的节点个数。重复此过程m3次。,局域世界间的连接： 以概率u在一个选定的局域世界与其他已存在的局域世界间建立m4条长程边。 首先随机选取一个局域世界，在其内部根据上面第一个概率公式选定一个节点，作为边的一端，边的另一端位于另一个随机选取的局域世界内，选定概率仍为第一个概率公式。重复次过程m4次。 上述参数满足：0q1, 0p, r, s, u1, p+q+r+s+u=1。,度分布分析,=1+1/ 若要求MLW模型幂率指数在23之间，还需满足下列条件： 可以验证，若另rm22sm3，那么上面的条件公式就能得到满足