论文部分内容阅读
摘要：复杂网络是指具有无标度、小世界、吸引子、自相似、自组织中部分或者所有性质的网络。在现实世界中，许多复杂的系统基本上都能以网络来进行描述，而现实中的那些复杂的系统则可以以“复杂网络”来称之，比如社会网、交通网、电力网、万维网、因特网等等都可以称之为复杂网络。本文主要通过对复杂网络理论的介绍，从而对计算机Internet网进行分析，对Internet网这一复杂系统进行探究，揭示Internet拓扑现象的特性、规律及动因。
关键词：复杂网络；计算机网络；网络拓扑
中图分类号：TP393.02 文献标识码：A文章编号：1007-9599 (2011) 13-0000-02
Analysis of Computer Network Topology Based on Complex Network Theory
Lin Yujun
(Civil Aviation Air Traffic Control Branch of Guangxi,Nanning530048,China)
Abstract:A complex network is scale-free,small world,attractor,self-similar,self-organization in the nature of some or all of the network.In the real world,many complex systems can basically be described by the network,while the reality is that complex systems can be"complex network"to call it,such as social networks,transportation networks,power grids,the World Wide Web,Internet etc.,can be called complex networks.In this paper,through the introduction of complex network theory to analyze Internet network of computers,the Internet network to explore this complex system,to reveal the phenomenon of Internet topology characteristics,rules and motivation.
Keywords:Complex networks;Computer network;Network topology
在现实世界中，许多复杂的系统基本上都能以网络来进行描述，而现实中的那些复杂的系统则可以以“复杂网络”来称之，比如社会网、交通网、电力网、万维网、因特网等等都可以称之为复杂网络。在这些复杂系统中，那些现实中的实体往往通过复杂网络的节点来表示，实体跟节点相对应，节点之间的连线（即边）则对应于实体与实体之间的关系。而Internet网络自从诞生开始，其一直沿着更优、更高级、更复杂的路径演化和发展着，现在Internet网络已经成为一个开放的、无中心控制的、异构的、分布式的极其复杂的网络系统。其复杂性主要表现在：第一，Internet网络结构日益复杂。Internet网络的规模在不断的扩大，网络中的节点不断加入和退出，各个节点以及它们之间的链路时常发生失效，链路也经常出现方向和权重的变化。第二，网络中节点日益复杂化。各节点越来越具有复杂非线性行为的动力学系统。第三，复杂因素之间的彼此影响。各个节点之间或者数据包流和节点之间出现了非线性的作用及其各个用户之间的竞争和合作等等都是彼此的影响因素。
一、复杂网络理论简介
复杂网络是指具有无标度、小世界、吸引子、自相似、自组织中部分或者所有性质的网络。复杂网络理论的主要内容有：网络的演化特征、演化规律、演化动力学机制、演化的统计规律以及网络的模型特质、形成机制、几何性质、结构稳定性等。在自然科学中，复杂网络研究的最为基本的内容包括：度、相关性、集聚程度、最短距离、介数以及它们的分布特征。
复杂网络系统一般有着下面几个特征：
（1）小世界。复杂网络通过简单的描述对许多复杂的现实网络进行了解释，认为不管规模多大的网络，其任意两个节点都是由一条路径连接的事实。它阐释无论什么世界都是通过相互关系非常小的无数个节点所连接起来的。比如，在现实的社会网中，每个人的生活圈很小，人跟人认识的数目非常少，但是这个社会却是由无数个关系所组成的，通过一条关系，可以找到跟你相距很远的无关系的陌生人。就好像麦克卢汉所讲的，地球将越来越小，是一个小的地球村，即一个小世界。
（2）集群性。复杂网络会越来越具有集群性。比如，在现实的社会网络中，每个人都有自己的朋友圈、熟人圈，在这个圈子里，每位成员都可能跟其他成员认识。集群性就是指网络具有一种内聚的倾向，即在一个大网络中，会分布着许多个彼此联系的积聚小网络。比如一个朋友圈往往会通过某种关系跟另一个朋友圈联系着。
（3）幂律的度分布。度是指网络中的节点及其节点关系的数量；度的相关性是指各个节点之间的联系紧密程度；介数是指网络中所有最短路径经过某一节点的数量，即有一节点A，在网络中，所有经过A的数量，它反映的是节点A的影响力。无标度网络的特征主要集中反映了集聚的集中性。总之，复杂网络的主要特征有：无标度性、小世界效应、节点度的幂律分布。
二、Internet网络的拓扑分析
（一）Internet拓扑的特点
近些年来对于Internet拓扑的研究，最重要的成果是对于Internet拓扑节点度的幂律分布。这种分布在规模不同的网络拓扑中表现出一定的稳定性，也就是指，在规模不同的Internet拓扑中，它们的节点度表现出一种幂律分布，即：
P（k）=k-β
其中，β一般在2—3这个小范围内进行波动，k是指节点度，P（k）表示度为k的节点出现的概率，即分布率。
Interne作为一个复杂网络，从其通信网络的优化目的来说，其实现节点间平均距离最小化、网络边数最小化是其拓扑优化的主要目标。即未来通信网络的趋势就是小世界网络。可是Internet网络所覆盖的范围非常巨大，具有全球性，其拓扑结构的发展还面临着许多技术上的问题。所以，对于Internet网络拓扑结构的优化目标的实现有点不大可能。但是话又说回来，尽管Internet的发展并不能实现拓扑设计的整体优化，它的小世界、较少边、高聚集等特性足以表明其还是具有小范围优化的特点，这些特点的产生可表现出其一些规律，即Internet网络具有优先连接和生长的规律。生长表示的是Internet具有动态增长的特性，所以Internet的拓扑结构也是一个动态的过程。优先连接规律表示新节点进入Internet网络的规则，即在新节点加入网络时会选择拥有较大连接数的节点进行连接。
（二）基于复杂网络理论的Internet网络拓扑模型的构建
在世人发现Internet网络节点度具有幂律分布的规律之后，Internet网络拓扑模型的构建产生巨大的转变。大家更多的选择从优先连接和生长等这一网络拓扑规律入手进行Internet网络的拓扑建模，其主要是为了让符合现实Internet拓扑性质的模型通过一些简单规则的演化让其自动地产生出来。可利用优先连接来对新节点加入网络的过程进行描述还比较粗糙，首先是因为新节点在加入之前，对网络全局的信息进行了解和把握具有很大的难度，其次一个原因是单一的优先连接不能够描述复杂的加入决策过程，而且在全网中容易形成少量的集散节点。所以要建立更加符合现实Internet拓扑特征的网络模型则需要考虑更完善的加入规则。
现在对于构建Internet模型主要是依据自治域级和路由器级，但由于Internet网络拓扑特性在不同层次和不同规模中表现出某种本质上的相似性，所以，本拓扑模型的构建都适应于这两个级。此模型主要的规则是前面提到的通过生长和局部优先连接，来形成Internet拓扑模型，这种形成机制就好像一个层次化比较强的选举过程，如下图所示：
此模型首先假设在一个平面中分布着n个节点，并存在着一个离散的均匀走动的时钟，这些节点都清楚自己是何时进入网络的，这些节点进入网络的时刻分布是从零时刻开始至具体某一特定时刻内的随机分布。每个节点进入网络前后的动作就是接收和发送消息及依据所接收的消息产生响应。发送和接收的消息中包括了自己的优先度以及消息传达的范围等内容。并且这些节点优先度将对其消息传送的范围即辐射半径产生直接的影响。在节点接收消息之后往往是按照消息源的优先度来确定其是否跟发送消息的节点建立连接，若所接收到的许多消息源节点存在相近的优先度，其将会随机地选择一个消息源节点进行连接。通过这种规则进行不断的演化和发展，将会得出上图的结果。其中a图表示Internet网络形成的初始阶段，那时仅仅只有一小部分节点进行活动，每个节点度都比较小，其发送和接收消息的范围还比较小，所以这些节点往往只跟自己相邻的节点进行连接。而随着时间的不断推进，节点度的不断增加，各个节点的消息所能到达的距离越来越远，即所形成的连接会越来越大、越来越多。在局部区域胜出的节点代表整个区域参与更大范围的竞争，以致形成更大区域的代表。这个过程将持续下去，直到网络中形成几个较大的聚集中心。如图（b）、（c）所示，这种自组织的层次网络并不具有预先设置的层次数。这就是Internet网络拓扑结构的形成模型，是一种消息自组织和传递接收的模型。
三、结束语
综上所述，复杂网络理论最主要的特性是无标度性、小世界效应、节点度的幂律分布。Internet网络延续着这些性质，在其拓扑结构构建和形成中表现出来，具体所形成的拓扑规则是：Internet网络中节点的生长性和优先连接。通过其不断的生长以及生长出的节点的优先连接，从而促使网络拓扑是一种消息自组织和传递的过程。
参考文献：
[1]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版,2009
[2]WattsDJ,StrogatzSH.Collective dynamics of"small-world"networks[J].Nature,2008,393:440-442
[3]方锦清,汪小帆,郑志刚,毕桥,狄增如,李翔.一门崭新的交叉科学:网络科学(上)[J].物理学进展,2010,3
[4]方锦清.非线性网络的动力学复杂性研究的若干进展[J].自然科学进展,2007,7
关键词：复杂网络；计算机网络；网络拓扑
中图分类号：TP393.02 文献标识码：A文章编号：1007-9599 (2011) 13-0000-02
Analysis of Computer Network Topology Based on Complex Network Theory
Lin Yujun
(Civil Aviation Air Traffic Control Branch of Guangxi,Nanning530048,China)
Abstract:A complex network is scale-free,small world,attractor,self-similar,self-organization in the nature of some or all of the network.In the real world,many complex systems can basically be described by the network,while the reality is that complex systems can be"complex network"to call it,such as social networks,transportation networks,power grids,the World Wide Web,Internet etc.,can be called complex networks.In this paper,through the introduction of complex network theory to analyze Internet network of computers,the Internet network to explore this complex system,to reveal the phenomenon of Internet topology characteristics,rules and motivation.
Keywords:Complex networks;Computer network;Network topology
在现实世界中，许多复杂的系统基本上都能以网络来进行描述，而现实中的那些复杂的系统则可以以“复杂网络”来称之，比如社会网、交通网、电力网、万维网、因特网等等都可以称之为复杂网络。在这些复杂系统中，那些现实中的实体往往通过复杂网络的节点来表示，实体跟节点相对应，节点之间的连线（即边）则对应于实体与实体之间的关系。而Internet网络自从诞生开始，其一直沿着更优、更高级、更复杂的路径演化和发展着，现在Internet网络已经成为一个开放的、无中心控制的、异构的、分布式的极其复杂的网络系统。其复杂性主要表现在：第一，Internet网络结构日益复杂。Internet网络的规模在不断的扩大，网络中的节点不断加入和退出，各个节点以及它们之间的链路时常发生失效，链路也经常出现方向和权重的变化。第二，网络中节点日益复杂化。各节点越来越具有复杂非线性行为的动力学系统。第三，复杂因素之间的彼此影响。各个节点之间或者数据包流和节点之间出现了非线性的作用及其各个用户之间的竞争和合作等等都是彼此的影响因素。
一、复杂网络理论简介
复杂网络是指具有无标度、小世界、吸引子、自相似、自组织中部分或者所有性质的网络。复杂网络理论的主要内容有：网络的演化特征、演化规律、演化动力学机制、演化的统计规律以及网络的模型特质、形成机制、几何性质、结构稳定性等。在自然科学中，复杂网络研究的最为基本的内容包括：度、相关性、集聚程度、最短距离、介数以及它们的分布特征。
复杂网络系统一般有着下面几个特征：
（1）小世界。复杂网络通过简单的描述对许多复杂的现实网络进行了解释，认为不管规模多大的网络，其任意两个节点都是由一条路径连接的事实。它阐释无论什么世界都是通过相互关系非常小的无数个节点所连接起来的。比如，在现实的社会网中，每个人的生活圈很小，人跟人认识的数目非常少，但是这个社会却是由无数个关系所组成的，通过一条关系，可以找到跟你相距很远的无关系的陌生人。就好像麦克卢汉所讲的，地球将越来越小，是一个小的地球村，即一个小世界。
（2）集群性。复杂网络会越来越具有集群性。比如，在现实的社会网络中，每个人都有自己的朋友圈、熟人圈，在这个圈子里，每位成员都可能跟其他成员认识。集群性就是指网络具有一种内聚的倾向，即在一个大网络中，会分布着许多个彼此联系的积聚小网络。比如一个朋友圈往往会通过某种关系跟另一个朋友圈联系着。
（3）幂律的度分布。度是指网络中的节点及其节点关系的数量；度的相关性是指各个节点之间的联系紧密程度；介数是指网络中所有最短路径经过某一节点的数量，即有一节点A，在网络中，所有经过A的数量，它反映的是节点A的影响力。无标度网络的特征主要集中反映了集聚的集中性。总之，复杂网络的主要特征有：无标度性、小世界效应、节点度的幂律分布。
二、Internet网络的拓扑分析
（一）Internet拓扑的特点
近些年来对于Internet拓扑的研究，最重要的成果是对于Internet拓扑节点度的幂律分布。这种分布在规模不同的网络拓扑中表现出一定的稳定性，也就是指，在规模不同的Internet拓扑中，它们的节点度表现出一种幂律分布，即：
P（k）=k-β
其中，β一般在2—3这个小范围内进行波动，k是指节点度，P（k）表示度为k的节点出现的概率，即分布率。
Interne作为一个复杂网络，从其通信网络的优化目的来说，其实现节点间平均距离最小化、网络边数最小化是其拓扑优化的主要目标。即未来通信网络的趋势就是小世界网络。可是Internet网络所覆盖的范围非常巨大，具有全球性，其拓扑结构的发展还面临着许多技术上的问题。所以，对于Internet网络拓扑结构的优化目标的实现有点不大可能。但是话又说回来，尽管Internet的发展并不能实现拓扑设计的整体优化，它的小世界、较少边、高聚集等特性足以表明其还是具有小范围优化的特点，这些特点的产生可表现出其一些规律，即Internet网络具有优先连接和生长的规律。生长表示的是Internet具有动态增长的特性，所以Internet的拓扑结构也是一个动态的过程。优先连接规律表示新节点进入Internet网络的规则，即在新节点加入网络时会选择拥有较大连接数的节点进行连接。
（二）基于复杂网络理论的Internet网络拓扑模型的构建
在世人发现Internet网络节点度具有幂律分布的规律之后，Internet网络拓扑模型的构建产生巨大的转变。大家更多的选择从优先连接和生长等这一网络拓扑规律入手进行Internet网络的拓扑建模，其主要是为了让符合现实Internet拓扑性质的模型通过一些简单规则的演化让其自动地产生出来。可利用优先连接来对新节点加入网络的过程进行描述还比较粗糙，首先是因为新节点在加入之前，对网络全局的信息进行了解和把握具有很大的难度，其次一个原因是单一的优先连接不能够描述复杂的加入决策过程，而且在全网中容易形成少量的集散节点。所以要建立更加符合现实Internet拓扑特征的网络模型则需要考虑更完善的加入规则。
现在对于构建Internet模型主要是依据自治域级和路由器级，但由于Internet网络拓扑特性在不同层次和不同规模中表现出某种本质上的相似性，所以，本拓扑模型的构建都适应于这两个级。此模型主要的规则是前面提到的通过生长和局部优先连接，来形成Internet拓扑模型，这种形成机制就好像一个层次化比较强的选举过程，如下图所示：
此模型首先假设在一个平面中分布着n个节点，并存在着一个离散的均匀走动的时钟，这些节点都清楚自己是何时进入网络的，这些节点进入网络的时刻分布是从零时刻开始至具体某一特定时刻内的随机分布。每个节点进入网络前后的动作就是接收和发送消息及依据所接收的消息产生响应。发送和接收的消息中包括了自己的优先度以及消息传达的范围等内容。并且这些节点优先度将对其消息传送的范围即辐射半径产生直接的影响。在节点接收消息之后往往是按照消息源的优先度来确定其是否跟发送消息的节点建立连接，若所接收到的许多消息源节点存在相近的优先度，其将会随机地选择一个消息源节点进行连接。通过这种规则进行不断的演化和发展，将会得出上图的结果。其中a图表示Internet网络形成的初始阶段，那时仅仅只有一小部分节点进行活动，每个节点度都比较小，其发送和接收消息的范围还比较小，所以这些节点往往只跟自己相邻的节点进行连接。而随着时间的不断推进，节点度的不断增加，各个节点的消息所能到达的距离越来越远，即所形成的连接会越来越大、越来越多。在局部区域胜出的节点代表整个区域参与更大范围的竞争，以致形成更大区域的代表。这个过程将持续下去，直到网络中形成几个较大的聚集中心。如图（b）、（c）所示，这种自组织的层次网络并不具有预先设置的层次数。这就是Internet网络拓扑结构的形成模型，是一种消息自组织和传递接收的模型。
三、结束语
综上所述，复杂网络理论最主要的特性是无标度性、小世界效应、节点度的幂律分布。Internet网络延续着这些性质，在其拓扑结构构建和形成中表现出来，具体所形成的拓扑规则是：Internet网络中节点的生长性和优先连接。通过其不断的生长以及生长出的节点的优先连接，从而促使网络拓扑是一种消息自组织和传递的过程。
参考文献：
[1]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版,2009
[2]WattsDJ,StrogatzSH.Collective dynamics of"small-world"networks[J].Nature,2008,393:440-442
[3]方锦清,汪小帆,郑志刚,毕桥,狄增如,李翔.一门崭新的交叉科学:网络科学(上)[J].物理学进展,2010,3
[4]方锦清.非线性网络的动力学复杂性研究的若干进展[J].自然科学进展,2007,7