基于复杂网络理论的计算机网络拓扑研究

１３２２００７，４３（６）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用基于复杂网络理论的计算机网络拓扑研究雷霆１．－，余镇危１ＬＥＩＴｉｎｇｌ，２，ＹＵＺｈｅｎ－ｗｅｉｌ１．中国矿业大学计算机系，北京１０００８３２．北京林业大学理学院，北京１０００８３１．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒ，ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＭｉｎｉｎｇ＆ＴｅｃｈｎｏｌｏｇｙａｔＢｅｉｊｉｎｇ，Ｂｅｉｊｉｎｇ１０００８３，Ｃｈｉｎａ２．ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＢｅｉｊｉｎｇＦｏｒｅｓｔｒｙＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８３，ＣｈｉｎａＥ－ｍａｒｌ：ｘｌｅｉｔｉｎｇ＠１２６．ｃｏｒｎＬＥＩＴｉｎｇ．ＹＵＺｈｅｎ—ｗｅｉ．ＲｅｓｅａｒｃｈｏｎｃｏｍｐｕｔｅｒｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｂａｓｅｄＯｉｌｃｏｍｐｌｅｘｎｅｔｗｏｒｋｔｈｅｏｒｙ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（６）：１３２－１３５．Ａｂｓｔｒａｃｔ：Ｃｏｍｐｌｅｘｎｅｔｗｏｒｋｔｈｅｏｒｙｉｓａｎｅｗｌｙｒｉｓｅｎｓｕｂｊｅｃｔ．Ｄｕｅｔｏｔｈｅｒａｐｉｄｄｅｖｅｌｏｐｍｅｎｔ，ｔｈｅｓｔｒｕｃｔｕｒｅｏｆｃｏｍｐｕｔｅｒｎｅｔｗｏｒｋｉｓｉｎｃｒｅａｓｉｎｇｌｙｃｏｍｐｌｉｃａｔｅｄ，ａｓａｒｅｓｕｌｔ，ｔｈｅｔｒａｄｉｔｉｏｎａｌｒａｎｄｏｍｎｅｔｗｏｒｋｍｏｄｅｌｉｓｄｉｆｆｉｃｕｌｔｔｏｃｈａｒａｃｔｅｒｉｚｅｏｂｊｅｃｔｉｖｅｌｙｃｕｒｒｅｎｔｃｏｍｐｕｔｅｒｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙ’Ｓｃｈａｒａｃｔｅｒ，ＳＯｃｏｍｐｌｅｘｎｅｔｗｏｒｋｔｈｅｏｒｙｐｒｏｖｉｄｅｓｎｅｗｖｉｅｗａｎｄｔｈｉｎｋｉｎｇｔｏｓｔｕｄｙｉｎｔｈｉｓｆｉｅｌｄ．Ｉｎｔｈｅｐａｐｅｒ，ｃｏｍｐｌｅｘｔｈｅｏｒｙｉｓｉｎｔｒｏｄｕｃｅｄ，ｔｈｅｎｉｔｓｕｒｖｅｙｓｃｕｒｒｅｎｔｓｔａｔｕｓｏｆｒｅｓｅａｒｃｈｏｎｃｏｍｐｕｔｅｒｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｂａｓｅｄｏｎｃｏｍｐｌｅｘｎｅｔｗｏｒｋｔｈｅｏｒｙ，ａｌｓｏｐｏｉｎｔｓｏｕｔｓｏｍｅｐｒｏｂｌｅｍｓｅｘｉｓｔｉｎｇａｍｏｎｇｔｈｅｍ，ａｓｗｅｌｌａｓａｐｐｌｙｉｎｇｔｈｉｓｔｈｅｏｒｙｔｏｓｔｕｄｙｃｏｍｐｕｔｅｒｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｉｓｅｍｐｈａｓｉｚｅｄ，ａｔｌａｓｔ，ｔｈｅｄｉｒｅｃｔｉｏｎｔｏｒｅｓｅａｒｃｈｉｎｆｕｔｕｒｅａｒｅｓｕｍｍａｒｉｚｅｄ．Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｕｔｅｒｎｅｔｗｏｒｋ；ｃｏｍｐｌｅｘｉｔｙｎｅｔｗｏｒｋ；ｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙ摘要：复杂网络理论是一门新兴学科。随着计算机网络的快速发展，网络结构日益复杂，使得传统的随机网络模型已很难对其拓扑特性作出客观的描述，因此，复杂网络理论为计算机网络拓扑的研究提供了一个新的视野和思路。文章对复杂网络理论作了介绍，综述了当前基于复杂网络理论计算杌网络拓扑研究的状况并指出了其中存在的问题；强调将复杂网络理论应厨到计算机网络拓扑研究当中的必要性。最后对复杂网络理论在未来计算机网络拓扑研究中的可能应用方向作了总结。关键词：计算机网络；复杂网络；网络拓扑文章编号：１００２—８３３１（２００７）０６—０１３２—０４文献标识码：Ａ中图分类号：ＴＰ３９３Ｉ复杂网络理论在有Ⅳ个节点的网络中，两点ｉ和ｉ的距离定义为所有连１．１网络定义通ｉ到ｉ的通路中，所经过的其它顶点最少的一条或几条路径网络已成为各学科领域重要的分析工具和研究手段．事实上，客观世界中复杂系统。都可用网络进行直观刻画。的长度。网络的平均距离Ｌ定义为：ＪＬ＝—导∑￡（ｉＪ）。网络是由许多节点与连接两个节点的一些边组成的，其中平均距离描述了节点对时间的平均分离。节点代表系统中不同的个体，边刚表示个体闯的关系；两个节（３）聚集系数Ｃ点之间具有特定的关系则连一条边．有边相连的两个节点被看在有Ⅳ个节点的网络中，若第ｉ个节点的度为ｋ。。在由这作是相邻的。比如计算机网络可以看作是自主工作的计算机通ｋ。个邻居节点构成的子网当中，实际存在的边ｅ；与这＆。个节过各种物理介质与通信协议相互连接所得到的网络。１．２网络的统计参数点所构成的完全图的总边数盈呜｜二堕的比值：ｃ（ｉ）＝ｉ痞三万，（１）度和度分布称为第ｉ个节点的聚集系数。整个网络的聚集系数Ｃ定义为所一个节点与其它节点相连的边数称为该节点的度．度是描述网络局部特性的基本参数。有节点聚集系数的平均值，即ｃ＝百１艺ｃ（ｉ）。节点度分布是指网络中度为ｋ的节点的概率Ｐ（ｋ）随节点聚集系数反映网络的聚集程度，聚集程度的意义是指网络度ｋ的变化规律。节点度的分布函数反映‘了网络系统的宏观统集团化的程度，即网络的内聚倾向。计特征，理论上利用度的分布可以计算出其它表征全局特征参１．３计算机网络的拓扑结构数的量化行为。不依赖于节点的具体位置和边的具体形态就能表现出来（２）网络的平均距离￡的性质称为网络的拓扑性质．相应的结构被称为网络的拓扑作者简介：雷霆（１９７２一），男，博士生，讲师，研究方向为计算机网络体系结构网络行为学；余镇危（１９４２一），男，教授，博士生导师，研究方向为下一代网络体系结构。万　方数据雷霆，余镇危：基于复杂网络理论的计算机网络拓扑研究２００７，４３（６）１３３结构。分组最多经过１９跳左右就可以被传到通信对端。大量研究表明。网络所具有的特性在很大程度上是由网络１９９９年Ｂａｒａｂ６ｓｉ和Ａｌｂｅａ指出真实网络的另一个重要统拓扑来决定的，不同的拓扑结构会导致网络性能的差异，所以计特征是网络的节点度服从幂律分布１５１，即Ｐ（｜｜｝）＝．ｉ｝１，幂律分布在研究网络的时候最值得关心的一个问题当然是网络拓扑了。的统计参数ｒ与网络大小无关．因此将具有这种特性的网络称什么样的拓扑结构比较适合用来描述真实的复杂系统呢？传统为无标度网络。所谓无标度性指所研究的客体与尺度无关．即图论所考虑的网络一般是规则网络【１１：网络中节点及其与边的无论测量的单位如何改变，所研究的客体的性质，例如形态、复关系是比较稳定的，例如邻环网，完全连结图。大的聚集系数和杂程度和统计特征等均不发生变化。无标度性同时表明客体的大的平均距离是规则网络的主要统计特征。到了２０世纪５０年自相似性只能存在于某一个范围之内，也就是无标度区．超出代．Ｅｒｄｔｉｓ和Ｒ６ｎｙｉ建立了随机网络的基本模型（２１：两个节点之了这个范围，自相似性随之消失，在无标度区里，系统具有自相间是否相连不是确定的事情．而是根据一个概率决定，它具有似性，也就是在不同尺度下观察或测量系统，会发现其结构、行小的聚集系数和小的平均距离的统计特征：节点度服从Ｐｏｓｓｉｎ为或者功能表现出不同的特性。无标度网络的节点度分布从直分布。在很长的一段时间内。真实系统被认为可以用随机网络观上看具有这样的特征：大多数节点只有少量的连接．而极少来客观描述。一直到了近几年，人们才认识到许多真实系统的数节点却有大量的连接，拥有的连接点可能高达数百，数千甚拓扑结构不是完全固定．也不是完全随机．而是一类复杂网络，至数百万，是一个无标度网络，少数主干节点路由器与其它众所谓复杂网络是指那些具有复杂动力学行为和复杂拓扑结构多的路由器相连。例如Ｓｉｎａ、Ｇｏｏｇｌｅ等这些门户网站有上百万的网络模型。甚至几十亿个链接。这说明当用随机网络模型来描述计算机网复杂网络的主要统计特征是小世界效应、无标度性，并且络的拓扑结构时．认为其节点度服从Ｐｏｓｓｉｏｎ分布的观点是不节点度服从幂律分布。符合事实的。图３所表示的是无标度网络与随机网络的区别。１９９８年Ｗａｔｔｓ和Ｓｔｒｏｇａｔｚ提出了小世界网络（Ｓｍａｌｌ—图４所表示的是Ｉｎｔｅｒｎｅｔ的拓扑结构，同时具有小世界和无标Ｗｏｒｌｄ）模型［３１。该模型通过以概率Ｐ随机改写规则网络的每一度两种统计特性，同时，在不同尺度上观察Ｉｎｔｅｒｎｅｔ，可以发现条边，即以概率Ｐ将一条现成的边重新连结到另一个顶点上，其结构具有自相似性。同时避免将自己连有的边相重合的方法．构造出了一种介于规则网络和随机网络之间的小世界网络。图１所表示是小世界网络的演化过程，当ｐ＝Ｏ时得到规则网络，当ｐ＝ｌ时对应于随机动网络，而介于０和１的一个很大范围内，Ｐ所对应的网络即是小世界网络。它同时具有大的聚集系数和小的平均距离的统计特征。图２所表示小世界网络统计具有介于规则网络与随机网络之间的统计特征。Ｓｍａｌｌ—ｗｏｒｌｄＲａｎｄｏｍ图３随机网络与无标度网络的区别④◇恭ｐ＝ｌｉｎｃｒｅａｓｉｎｇｒａｎｄｏｍｎｅｓｓ图１小世界网络的演化过程图４Ｉｎｔｅｍｅｔ拓扑结构：同时具有小世界效应与无标度特性ｐ图２小世界网络的统计特征：小的平均距离￡（Ｐ）复杂网络目前已成为研究真实系统的有力工具，已应用于和大的聚集系数Ｃ（ｐ）各个学科领域，受到了众多研究人员的广泛关注。研究发现．ＷＷＷ是一个小世界网络…，它的节点平均距离是１９个连接．也就是在ＷＷＷ上随机任意取两点，不断地点２复杂网络理论在计算机拓扑行为研究中的应用击这上面的超级链节。按１９次鼠标就能从一点连接到达另一网络管理是网络系统正常运行的关键，而掌握网络拓扑行点：Ｉｎｔｅｍｅｔ也是一小世界网络Ｉ“４１，Ｉｎｔｅｍｅｔ上的路由器数量已为的演化规律又是网络管理的基础。对网络性能及流量进行分经是数以几十万计，用户数量更是大得惊人，但通过计算得知析．首先必须对拓扑结构及其演化规律作出较为精确地刻画。整个Ｉｎｔｅｍｅｔ的平均距离仅是１９，也就是说平均起来一个数据传统的方法大都采用结构相对简单的随机网络来描述真万　方数据１３４２００７．４３（６）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用实的计算机网络的拓扑。在规模不大、业务种类比较单一的网络起步阶段，随机网络模型在一定程度上能比较客观反映计算机网络拓扑演化规律，但与以前相比，如今计算机网络所处的环境与发生根本性的改变：规模和用户数量巨大且仍然在不断增长．异质异构的网络融合发展；网络协议体系庞杂，垂直方向呈现出多样化的层次结构。而水平方向上又以地域和功能为标准进一步形成分布且多级的架构：网络节点问、节点与数据分组间由于协议而产生的非线性作用、用户之间的合作与竞争以及各种网络恶意攻击的出现等［６１。这些情况使计算机网络日益复杂．用随机网络模型来描述计算机网络拓扑行为已经显得力不从心．在这样的背景下，强调系统整体性的复杂网络理论的兴起给人们提供了计算机网络拓扑研究的新思路。如今已有一些学者利用复杂网络理论去研究计算机复杂的网络行为，借助于复杂网络理论这个有力工具，从多个视角、不同的抽象角度对网络系统进行分析．研究各个单元之间相互连接、相互作用而导致网络系统表现出来行为规律和本质。例如流量行为特性分析、网络拓扑的生成机理和动力学行为、流量行为和拓扑行为的相互作用、网络同步行为的研究等。２．１计算机网络拓扑行为的演化模型目前为止。针对计算网络拓扑主要是基于Ｂａｒａｂｒｓｉ和Ａｌｂｅａ提出来的复杂网络演化模型（ＢＡ模型）和其改进型的局部演化模型．在路由器和自治域这两种不同的层次来描述计算机网络的拓扑结构¨Ｏｌ。从路由器层次上看，路由器相当于网络节点，路由器之间的物理连接相当于边：而从自治域来看，如果两个自治域之间存在基于边界网关协议（ＢＧＰ）的对等连接，则表示这两个节点之间有一条边相连。大量实验研究表明计算机网络的增长遵循ＢＡ模型的“偏好连接”法则，演化的结果会导致“富者更富”的现象。也就是说新加入的用户总是更倾向于优先考虑连接到那些知名度高、服务质量好、连接数多的服务器或者网络服务商，这一点与生活中的“名人效应”很相象。但是这个模型一个明显的不足之处那就是其中的“偏好连接”是基于整个网络的“偏好连接”，这点与实际情况不相符，实际上现实中网络路由一般是优先考虑连接到本地区的路由器或服务器，尽管该地区以外的其它路由器或服务器的连接数可能要高于当地路由器的连接数。针对这种情况。汪小帆、陈关荣［１１１等人所提出的局部演化模型的“偏好连接”的倾向性是基于局部而非全局的信息，在一定程度上改进了模型的缺陷。事实证明现有的模型来解释计算机网络拓扑演化规律还比较弱。因为无论是ＢＡ模型，局部演化模型还是其它演化模型。都是在一些理想化的简单假定下来解释计算机网络复杂的拓扑演化规律，对于在一些诸如信息传输中的延迟、时变、节点动态地加入与退出、不同节点不同动力学的差异等复杂情况下网络拓扑行为特性的研究还开展不够．所以现有的模型还不能很好地描述网络拓扑对网络动力学的影响以及网络单节点的行为与网络整体行为特性的关系等问题。是否还有更好的模型来对计算机网络拓扑结构的动力学演化特性更加真实的细致和全面的刻画，是一个有待于研究的问题【１２１。２．２计算机网络同步行为研究网络中各结点间的同步化行为是复杂网络很普遍的一个现象．它的产生由网络拓扑和单个节点的动力学性质共同决定。在很多场合，同步行为是有害的。例如说Ｉｎｔｅｒｎｅｔ上的不同万　方数据路由器发送路由消息，最终会达到同步化现象，也就是或者同时发布路由消息。或者不发布，这种同步行为显然会导致网络拥塞［１１，１３】。人们已经提出了一些方法来避免有害的同步行为，例如早期随机检测机、可变拥塞窗口控制等机制。但是还没有一套有效的方法真正避免计算机网络上有害的同步化现象，经常是一种同步化现象避免。另外一种同步化现象又产生了ｆ１１—４１。所以，弄清楚同步性和网络拓扑结构的相互作用的机理，进而采取有效措施来避免网络中有害的同步行为，到目前为止还是值得进一步研究的课题。２．３计算机网络鲁棒性与脆弱性的动力学模型无标度的拓扑结构使计算机网络对随机错误的具有较强鲁棒性但在恶意攻击情况下却表现得很脆弱［１５，１６３。（１）鲁棒性计算机网络具有很强的鲁棒性。众所周知。计算机网络本来是由军方的通信系统演变而来的，当初构建计算机网络的一个重要原则就是保证系统的鲁棒性，提高它的自愈能力或者说生存能力，也就是在某些节点或者线路遭到攻击或发生故障的情况下不会导致整个系统的崩溃。的确如此，无标度性的拓扑结构使计算机网络在局部环境受到随机攻击时也能保持节点度分布的稳定性。抗毁能力很强。例如计算机网络对随机性的攻击具有非常高的鲁棒性，局部失效很难导致失去全局网络传输信息的能力。研究发现，随意选择高达８０％的节点使之失效，剩余的网络还可能组成一个完整的集群并保持任意两点间的连接。（２）脆弱性由于少量的中心结点对整个网络运行所起的重要的作用，所以也使得网络遇到针对高节点度的中心节点的智能攻击时显得非常脆弱。实验表明对于计算机网络。只要５％一１０％的中心节点同时失效，就可导致整个网络溃散成一些相互隔绝的“信息孤岛”，从而导致整个系统的瘫痪。图５所表示的鲁棒同时脆弱的双重特性，Ｉｎｔｅｍｅｔ随机故障（Ｆａｉｌｕｒｅ：用小方格表示）与遇到智能打击（Ａｔｔａｃｋ：用椭圆表示）时候网络连通度受损程度的比较，其中横坐标表示以随机或智能的方式按一定比例厂移除网络中的一些节点，纵坐标表示网络连通度，连通度用网络平均距离￡来刻画，Ｌ越大，表明网络遭到破坏的程度越高。图５Ｉｎｔｅｍｅｔ的鲁棒性和脆弱性导致计算机网络鲁棒同时脆弱双重特性的动力学机制是什么呢？这个问题至今还没有一个圆满的答案。如果能知道产生这两种相对立特征背后的真正原因，就有可能根据需要，设计出一个安全性更高、性能更为优越的网络。在复杂系统的研究领域中，自组织临界性（ＳＯＣ，Ｓｅｒｆ—ＯｒｇａｎｉｚｅｄＣｒｉｔｉｃａｌｉｔｙ）模型【ｌ刀曾一直被认为是产生无标度拓扑结构的动力学原因．并且很好解释了产生地震灾害、火山爆发、股市涨落等复杂性现象的动力学原因，但是用它来解释计算机网络鲁棒同时脆弱的特性又非常牵强。这是因为计算机网络体系结构具有很强的层次雷霆，余镇危：基于复杂网络理论的计算机网络拓扑研究２００７，４３（６）１３５结构，而ＳＯＣ模型的层次结构却不那么明显．另一方面ＳＯＣ模型强调时空坍塌的临界状态与外界的冈素无关，只和系统内部动力学机制相关，这与计算机网络系统是按照一定优化目标建立起来从雨存在外部人工干扰的实际情况不相符。针对这些情况有学者来提出的高优化容忍（ＨＯＴ）模型了ｉｍｌ。ＨＯＴ模型的层次结构，既鲁棒又脆弱的特性和Ｉｎｔｅｒｎｅｔ很相似，可以帮助理解Ｉｎｔｅｒｎｅｔ复杂行为的一些动力学原理。但是ＨＯＴ模型只是对Ｉｎｔｅｒｎｅｔ中鲁棒同时脆弱做定性方面的解释．没有给出定量的刻画．显得很粗糙．同时ＨＯＴ模型对Ｉｎｔｅｒｎｅｔ自相似行为不能作出很好的解释。建立一个很好的动力学模型来解释Ｉｎｔｅｒｎｅｔ鲁棒同时脆弱的双重性．至今还是一个没有解决的难题．在未来研究中需要更加深人地探讨。２．４网络病毒扩散模型与防范方法在计算机网络安全研究领域中。有关计算机病毒防范的研究，主要着眼于如何采取合理的反病毒和预防策略。降低病毒传播的网络效率，阻断病毒传播链，降低病毒对网络的危害，目前仍是一个还没完全解决的重要问题。传统的病毒防范方法是基于规则网络病毒传播模型上．该模型认为病毒在网络中的平均波及范围与其传染强度正相关，而传染强度有一个阈值，只有当其值大于这个阈值时，病毒才能在网络中长期存在，否则感染节点数会指数衰减。根据这种理论，提出了随机免疫方法：进行免疫时对所有点平等对待的，随机地选择节点，没有优先顺序。但实际情况是这样，即使对网络的大量节点都进行随机免疫，仍不能阻止病毒的爆发。复杂网络理论的兴起为研究病毒的扩散机制和防范方法提供了新的思路．人们逐渐意识到网络的拓扑结构对计算机病毒的传播行为有着很重要的影响，例如相对于规则网络，病毒在小世界网络上更容易传播．在无标度网络上病毒的传播没有正传播阈值，也就是说在此类网络上病毒传染强度接近零．虽然只播及非常少的节点，也能在网络中长期存在，一旦有节点感染病毒就会大范围的传染【１９１。而计算机网络具有小世界特征，又有无标度特性。这使得以往的阻断病毒传播的策略面临挑战。建立一个完整的病毒传播模型是预防的前提条件，传播模型至少应该包括３个方面．即病毒的传播原理和网络的拓扑结构以及两者之间的相互作用机制。同样在阻止病毒传播策略上，不仅注重降低病毒有效传播率，更重要着眼于如何针对病毒传播机制在管理策略上有针对性要改变网络拓扑结构以达到控制病毒大规模传播的目的．复杂网络理论在这些问题的研究中具有指导意义。随着人们对网络行为系统的复杂性及其相关规律的深入研究，计算机网络基础理论研究可望取得重大突破。必将对未来计算机网络的发展产生巨大的影响。３展望复杂网络理论使人类的认识产生了新的飞跃，面对网络化和信息化时代的挑战与机遇，复杂网络理论必将大有作为，它在一个新的高度上提供了理解客观世界的视野。任何复杂网络理论研究的新成果都有可能被运用到计算机网络行为特性的研究当中，结合计算机网络自身的特点，应用复杂性理论对计算机网络的拓扑行为加以研究．就有可能发现其拓扑行为演化规律，从而根据实际需要，设计出一个性能比较优越的计算机万　方数据网络，下面几点是基于复杂网络理论的计算机网络拓扑行为以及相关技术可以研究的方向和实现的目标：（１）从理论上定义和建立计算机网络的复杂网络理论。包括描述计算机网络拓扑的基本性质的特征最．定量与定性分析方法；研究计算机网络的拓扑演化机制。不同节点对于整个网拓扑演化行为的影响程度，以及彼此之间的相互作用：寻求能够真实反映其拓扑结构的复杂网络的构造机制，并建立网络拓扑以及其动力学演化行为的模型，基于该模型讨论网络结构的统计平均性质，例如，类似节点度的分布特征、小世界性质、无标度特性以及动力学过程中混沌、分形等复杂行为：构造网络拓扑模型的各种算法以及模型的性能评价。（２）基于复杂网络的某些统计特性，对计算机网络拓扑的构建、拓扑发现、用户的动态更新、资源管理、服务发现、服务部署等问题进行研究；针对某种具体网络体系结构服务或应用，构造其相应的性能高、可扩展性好、有利于管理的具有小世界或无标度特性的网络结构．例如具有小世界特性或者无标度的主动网络、主动Ｏｖｅｒｌａｙ网络、Ｗｅｂ服务Ｏｖｅｒｌａｙ网络、Ｐ２Ｐ网络、组播Ｏｖｅｒｌａｙ网络。（３）基于复杂性理论的各种ＱＯＳ的实现方法。（４）基于复杂网络理论的路由机制及其算法的研究以及如何通过适当的路由机制来提高网络的信息传输量。（５）研究网络病传播和网络拓扑行为演化的相互作用机制，提出相应的防范措施。（６）基于复杂网络理论的探讨计算机网络可靠性、抗毁性；提出一个能够真实描述计算机网络鲁棒同时脆弱的动力学模型。（７）研究计算机网络各种同步与控制问题．分析网络的同步现象。提出有害同步行为例如网络拥塞的控制机制。４结束语计算机网络庞大的规模、异质而复杂的体系结构和丰富的动态特性．使传统的随机网络模型难以对其拓扑行为特征作出系统、客观地描述，强调系统整体性的复杂网络理论为网络行为的研究提供了新视角、新方法，有希望成为解决网络行为基础理论研究的有力工具，使网络的基础理论研究带来重大突破。为探索和研究复杂的计算机网络系统的奥秘提供有效的分析理论和方法，为现代计算机网络的科学管理和有效控制、科学规划和合理利用提供科学的依据。（收稿日期：２００６年６月）参考文献：［１］ＡｌｂｅｒｔＲ，ＢａｒａｂａｓｉＬ．Ｓｔａｔｉｓｔｉｃａｌｍｅｃｈａｎｉｃｓｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ［Ｊ］．ＲｅｖｉｅｗｓｏｆＭｏｄｅｒｎＰｈｙｓｉｃｓ，２００２，７４：４７－９７．［２】Ｅｒｄ６ｓＰ，ＲｒｎｙｉＡ．Ｏｎｔｈｅｅｖｏｌｕｔｉｏｎｏｆｒａｎｄｏｍｇｒａｐｈｓ【Ｊ】．Ｐｕｂｌｉｅａ—ｌｉｏｎｓｏｆｔｈｅＭａｔｈｅｍａｔｉｃａｌＩｎｓｔｉｔｕｔｅｏｆｔｈｅＨｕｎｇａｒｉａｎＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅ，１９６０，５：１７－６０．［３］３ＷａｔｔｓＤＪ，ＳｔｒｏｇａｔｚＳＨ．Ｃｏｌｌｅｃｔｉｖｅｄｙｎａｍｉｃｓｏｆｓｍａｌｌ－ｗｏｒｌｄｎｅｔ・ｗｏｒｋｓ［Ｊ］．Ｎａｔｕｒｅ．１９９８．３９３：４４０—４４２．【４】ＮｅｗｍａｎＭＥＪ．Ｍｏｄｅｌｓｏｆｔｈｅｓｍａｌｌｗｏｒｌｄ［Ｊ］ＪＳｔａｔＰｈｙｓ，２０００，１０１．【５】ＢａｒａｂｒｓｉＡＬ，ＡｌｂｅｒｔＲ．Ｅｍｅｒｇｅｎｃｅｏｆｓｃａｌｉｎｇｉｎｒａｎｄｏｍｎｅｔｗｏｒｋｓ［Ｊ］．Ｓｃｉｅｎｃｅ，１９９９，２８６：５０９—５１２．［６】徐恪，吴建平，徐明伟．高等计算机网络一体系结构、协议机制、算法（下转１８０页）１８０２００７，４３（６）ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｗａｉｏｎｓ计算机工程与应用表３训练后状态转移概率矩阵状态转移概率分布如表３。观察值概率分布如表４。根据训练得到的模型．当一个新的用户开始学习这５个知识点时，系统根据初始概率可知应该首先学习知识点１，即广群。又根据观察值概率分布得到在学习知识点ｌ的时候点击页面１的概率最大，因此将页面１提供给用户学习。学习了第一个知识点后，可以根据状态转移矩阵得到接下来最有可能学习的知识点。然后再根据观察值概率分布取得学习该知识点时应该点击的页面。将该页面提供给学习者即可。按照改进后的算法。模型在训练了１００条数据后便收敛，但是如果按照经典算法中，将初始概率随机分配，训练数据将大大增加。试验表明。改进后的算法在保证了结果准确的基础上提高了效率。模型对大量学习序列进行训练，找到隐藏在不同知识点之间的内在关联。并且在用户学习的过程中．根据前面的学习页面，通过推导得到即将应该学习的页面，自动地发送给用户学习。使用隐马尔科夫模型对知识点的关系进行确定，可以使系统在众多的学习序列中。根据用户的习惯和学习效果得到一条最优的序列．从而实现智能引导的功能。（收稿日期：２００６年１０月）参考文献：［１］王梓坤，杨向群．生灭过程与马尔可夫链【Ｍ】．北京：科学出版社，２００５．【２］刘克．实用马尔可夫决策过程［Ｍ］．北京：清华大学出版社，２００４．【３】王辉，王双成，张剑飞．马尔科夫网络中的隐藏变量学习［Ｊ】．小型微型计算机系统，２００５，３（２６）：３４８．【４】ＲａｂｉｎｅｒＬＲ．Ａｉｎｔｕｔｏｒｉａｌｏｎｈｉｄｄｅｎｍａｒｋｏｖｍｏｄｅｌｓａｎｄｓｅｌｅｃｔｅｄ６结论本文主要讨论了如何在智能学习系统中，利用隐马尔科夫（上接１３５页）设计与路由器技术［Ｍ】．北京：机械工业出版社，２００３．【７】Ｖ６ｚｑｕｅｚＡ，Ｐａｓｔｏｒ—ＳａｔｏｒｒａｓＲ，ＶｅｓｐｉｇｎａｎｉＡ．Ｌａｒｇｅ－ｓｃａｌｅｔｏｐｏｌｏｇｉｃａｌａｎｄｄｙｎａｍｉｃａｌｐｒｏｐｅｒｔｉｅｓｏｆｔｈｅ０６６１３０．ａｐｐｌｉｃａｔｉｏｎｓ７７（２）．Ｉｎｔｅｒｎｅｔｓｐｅｅｃｈｒｅｃｏｇｎｉｔｉｏｎ［Ｊ］．ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＥＥＥ，１９８９，ｃｏｎｇｅｓｔｉｏｎｃｏｎｔｒｏｌｍｏｄｅｌ［Ｊ］．Ｃｈａｏｓ，ＳｏｌｉｔｏｎｓａｎｄＦｒａｃｔａｌｓ，２００４，２１（１）：８１—９１．【１４］ＹａｎＧａｎｇ，ＺｈｏｕＴａｏ，ＷａｎｇＪｉｅ，ｅｔａ１．Ｅｐｉｄｅｍｉｃｓｐｒｅａｄｓｃａｌｅ—ｆｒｅｅｉｎｗｅｉｇｈｔｅｄＩｎｔｅｒｎｅｔ［Ｊ］．ＰｈｙｓＲｅｖＥ，２００２，６５（６）：Ｄｎｅｔｗｏｒｋｓ［Ｊ］．ＣｈｉｎＰｈｙｓＵｅｒＩ，ｒ，２００５，２２（２）：５１０．ｅｎ＇ｏｒ［１５】ＡｌｂｅｒｔＲ，ＪｅｏｎｇＨ，ＢａｒａｂａｓｉＡＬ．ＡｔｔａｃｋａｎｄＪＯ，ＳｏｒｋｉｎＧＢ，ＣｈｅｓｓＭ，ｅｔｔｏｌｅｒａｎｃｅｏｆ［８】Ｋｅｐｈａｒｔａ１．Ｆｉｓｈｔｉｎｇｃｏｍｐｕｔｅｒｃｏｍｐｌｅｘｎｅｔｗｏｒｋ［Ｊ］．Ｎａｔｕｒｅ，２０００，４０６：３７８－３８２。ｉｎｖｉｒｕｓｅｓ［Ｊ］．ＳｃｉｅｎｔｉｆｉｃＡｍｅｒｉｃａｎ，１９９７，２７７（５）：５６－６１．【９】ＷａｎｇＸｉａｏ－ｆａｎ，ＣｈｅｎＧｕａｎ－ｒｏｎｇ。Ｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ：ｓｍａｌｌ－ｗｏｒｌｄ，Ｃｉｒｃｕｉｔｓ［１６］ＷａｎｇＸｉａｏ—ｆａｎ，ＣｈｅｎＧｕａｎ－ｌｏｎｇ．Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎｄｙｎａｍｉｃａｌｎｅｔｗｏｒｋｓ：ｒｏｂｕｓｔｎｅｓｓａｎｄＣｉｒｃｕｉｔｓａｎｄＳｙｓｔｅｍｓ，Ｐａｒｔｓｃａｌｅ－ｆｒｅｅｏｎｓｃａｌｅ－ｆｒｅｅ，ａｎｄｂｅｙｏｎｄ［Ｊ］．ＩＥＥＥ２００３，３（２）：６—２０．ａｎｄＳｙｓｔｅｍｓＭａｇａｚｉｎｅ，ｆｒａｇｉｌｉｔｙ［Ｊ］．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓＩ：ＲｅｇｕｌａｒＰａｐｅｒ，２００２，４９（１）：５４－６２．ｓｃｉｅｎｃｅ【１０】ＣｈｅｎＧｕａｎ—ｒｅｎｇ，ＦａｎＺｈｅｎｇ－ｐｉｎｇ，ＬｉＸｉａｎｇ．ＭｏｄｅｌｉｎｇｔｈｅｐｌｅｘＩｎｔｅｒｏｅｔｃｏｍ－【１７】ＢａｋＰ．Ｈｏｗｎａｔｕｒｅｗｏｒｋｓ：ｔｈｅｏｆｓｅｌｆ－ｏｒｇａｎｉｚｅｄｃｒｉｔｉｃａｌｉｔｙ［Ｍ］．ｔｏｐｏｌｏｇｙ［Ｃ］／／ＣｏｍｐｌｅｘＤｙｎａｍｉｃｓｉｎＣｏｍｍｕｎｉｃａｔｉｏｎＮｅｗＹｏｒｋ：Ｓｐｒｉｎｇｅｒ—ＶｅｒｌａｇＴｅｌｏｓ，１９９９．Ｎｅｔｗｏｒｋｓ．ＳｐｒｉｎｇｅｒＰｕｂｌｉｓｈｅｒ，２００４．【１８】ＪａｎｃｚｅｗｓｋＬＪ．Ｃｕｒｒｅｎｔｉｎｆｏｒｍａｔｉｏｎｌｏｏｋｆｏｒｔｈｅｓｏｕｒｃｅｓｓｅｃｕｒｉｔｙｐｒｏｔｏｃｏｌｓａｎｄａｎｏｕｔ—［１ｌ】ＷａｎｇＧｕａｎ－ｒｏｎｇ．Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎｉｎｓｃａｌｅ－ｆｒｅｅｄｙｎａｍｉｃａｌｎｅｔｗｏｒｋｓ：ｒｏｂｕｓｔｎｅｓｓａｎｄｆｒａｇｉｌｉｔｙ叨．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎＣｉｒｃｕｉｔｓａｎｄＳｙｓｔｅｍｓ，ＰａｒｔＩ：ＲｅｇｕｌａｒＰａｐｅｒ，２００２，４９（１）：５４—６２．Ａ，２００３，３２８（１／２）：２７４－２８６．ｉｎＸｉａｏ一协，Ｃｈｅｎｆｕｔｕｒｅ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２０００ＩｎｆｏｒｍａｔｉｏｎＲｅ・ＡｓｓｏｃｉａｔｉｏｎＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｉｎｏｎＭａｎａｇｅｍｅｎｔｏｆＣｈａｌｌｅｎｇｅｓＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙＭａｎａｇｅｍｅｎｔｔｈｅ２１ｓｔ【１２］ＬｉＸｉａｎｇ，ＣｈｅｎＧｕａｎ－ｒｏｎＩ昏Ａｌｏｃａｌ－ｗｏｒｌｄｅｖｏｌｖｉｎｇｎｅｔｗｏｒｋｍｏｄｅｌ口ｌＰｈｙｓｉｃａｌＣｅｎｔｕｒｙ，２０００：１－１０．【１９】Ｐａｓｔｏｒ—ＳａｔｏｒｒａｓＲ，ＶｅｓｐｉｎｇｎａｎｉＡ．Ｅｐｉｄｅｍｉｃｓｐｒｅａｄｉｎｇｉｎｓｃａｌｅ—ｆｒｅｅ【１３］ＣｈｅｎＬｉａｎｇ，ＷａｎｇＸｉａｏ—ｆａｎ，ＨａｎＺｈｅｎｇ－ｚｈｉ．Ｃｏｎｔｒｏｌｌｉｎｇｃｈａｏｓｎｅｔｗｏｒｋｓ［ｊ］．ＰｈｙｓｉｃａｌＲｅｖｉｅｗＬｅｔｔｅｒｓ，２００１，８６（１４）：３２００－３２０３．万方数据　基于复杂网络理论的计算机网络拓扑研究

作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：

雷霆， 余镇危， LEI Ting， YU Zhen-wei

雷霆,LEI Ting(中国矿业大学,计算机系,北京,100083;北京林业大学,理学院,北京,100083)， 余镇危,YU Zhen-wei(中国矿业大学,计算机系,北京,100083)计算机工程与应用

COMPUTER ENGINEERING AND APPLICATIONS2007,43(6)10次

参考文献(19条)

1.Pastor-Satorras R;Vespingnani A Epidemic spreading in scalefree networks[外文期刊] 2001(14)2.Wang Xiao-fan;Chen Guan-rong Complex networks:small-world,scale-free,and beyond 2003(02)3.Kephart J O;Sorkin G B;Chess D M Fighting computer viruses[外文期刊] 1997(05)

4.Vázquez A;Pastor-Satorras R;Vespignani A Large-scale topological and dynamical properties of theInternet 2002(06)

5.徐恪;吴建平;徐明伟 高等计算机网络-体系结构、协议机制、算法设计与路由器技术 20026.Barabási A L;Albert R Emergence of scaling in random networks[外文期刊] 19997.Newman M E J Models of the small world[外文期刊] 2000

8.Watts D J;Strogatz S H Collective dynamics of small-world networks[外文期刊] 1998(6684)9.Erd(o)s P;Rényi A On the evolution of random graphs 1960

10.Janczewsk L J Current information security protocols and an outlook for the future 200011.Bak P How nature works:the science of self-organized criticality 1999

12.Wang Xiao-fan;Chen Guan-reng Synchronization in scale-free dynamical networks:robustness andfragility[外文期刊] 2002(01)

13.Albert R;Jeong H;Barabasi A L Attack and error tolerance of complex network[外文期刊] 200014.Yan Gang;Zhou Tao;Wang Jie Epidemic spread in weighted scale-free networks[期刊论文]-Chin PhysLETI 2005(02)

15.Chen Liang;Wang Xiao-fan;Han Zheng-zhi Controlling chaos in Internet congestion control model[外文期刊] 2004(01)

16.Li Xiang;Chen Guan-rong A local-world evolving network model[外文期刊] 2003(1-2)

17.Wang Xiao-fan;Chen Guan-rong Synchronization in scale-free dynamical networks:robustness andfragility[外文期刊] 2002(01)

18.Chen Guan-rong;Fan Zheng-ping;Li Xiang Modeling the complex Internet topology 200419.Albert R;Barabátsi L Statistical mechanics of complex networks 2002

引证文献(11条)

1.顾明霞 Internet拓扑建模研究评述[期刊论文]-南通大学学报（自然科学版） 2010(3)2.王宏.赵锋.彭伟 一种基于网络顶点割的拓扑优化算法[期刊论文]-计算机科学 2010(11)

3.都吉夔.郑建常.张宇隆.王峰.高玉峰.白春华 地震应急预案信息管理系统的开发技术研究[期刊论文]-西北地震学报 2010(4)

4.丁德武.陆克中.须文波.方康年 代谢途径分析研究进展及其应用[期刊论文]-计算机工程与应用 2009(33)

5.杨光华.李夏苗.谢小良 加权区域物流网络结构分析[期刊论文]-计算机工程与应用 2009(26)6.陈长坤.孙云凤.李智 冰雪灾害危机事件演化及衍生链特征分析[期刊论文]-灾害学 2009(1)

7.LUO Gui-lan.罗桂兰.赵海.赵明 Internet宏观拓扑的协议映射与分析[期刊论文]-计算机工程与应用 2009(12)8.陈长坤.李智.孙云凤 基于复杂网络的灾害信息传播特征研究[期刊论文]-灾害学 2008(4)

9.李敏.陈建二.王建新 基于复杂网络理论的PPI网络拓扑分析[期刊论文]-计算机工程与应用 2008(8)10.雷霆.余镇危 复杂性理论在计算机网络行为研究中的应用[期刊论文]-计算机工程与应用 2007(35)

11.都吉夔.郑建常.张宇隆.王峰.高玉峰.白春华 地震应急预案信息管理系统的开发技术研究[期刊论文]-西北地震学报 2010(4)

本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjgcyyy200706043.aspx