论文部分内容阅读
追溯网络科学发展的轨迹，网络科学发展史有过三大里程碑，每个里程碑无一不是从网络的理论模型首先取得突破的。国际上提出的经典理论模型最著名的有：欧拉图论、ER随机图以及小世界模型和无标度模型。科学界迄今已经积累了许多有价值的理论模型，开展了许多实际网络的研究，基本揭开了复杂网络的庐山真面目，使人们了解到其复杂性与简单性、多样性与普适性之间错综复杂的关系。
第一个里程碑：欧拉图论
网络科学首先是得益于图论和拓扑学等应用数学的发展。历史上，多位杰出数学家各自独立地建立和研究过图论，他们的贡献功不可没。所谓图论就是由一些点按照一定方式连线组成的一个图(集合)。关于图论的文字记载最早出现在1736年瑞士数学家欧拉的论著中，他所考虑的原始问题具有很强的实际背景，那就是著名的哥尼斯堡七桥问题。
哥尼斯堡是当时东普鲁士的首都，今俄罗斯加里宁格勒市，普莱格尔河横贯其中，这条河上建有七座桥，将河中间的两个岛和河岸联结起来。人们闲暇时经常在这上边散步，有人提出：能不能每座桥都只走一遍，最后又回到原来的位置。这个看起来很简单却很有趣的问题吸引了大家，很多人在尝试各种各样的走法，然而无数次的尝试都没有成功。
1736年，有人带着这个问题找到了当时的大数学家欧拉，欧拉经过一番思考，很快就用一种独特的方法给出了解答。他把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线，如图所示，A、B、C、D表示陆地。于是这个问题就简化成，能不能用一笔就把这个图形画出来。经过进一步的分析，欧拉得出结论：不可能每座桥都走一遍，最后回到原来的位置，并且给出了所有能够一笔画出来的图形所应具有的条件。这项工作使欧拉成为图论(及拓扑学)的创始人。
欧拉的研究开创了图论这门新的数学分支，欧拉因此被誉为“图论之父”。这是第一代科学家对网络科学的开创性贡献。
1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个节点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个节点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起国际上广泛的注意和研究。
在图论的历史中，还有一个最著名的问题——四色猜想，它也是世界近代三大数学难题之一。首先提出四色猜想的人是英国人弗南西斯·格思里，他在给地图着色时，发现了一种有趣的现象：“每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”1878～1880年两年间，著名律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文。但后来数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。所以它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了i00亿判断，终于完成了四色定理的证明。当然，不少数学家还在探索一种更简捷明快的书面证明方法。
在拓扑学的发展历史中，还有一个著名而且重要的关于多面体的定理也和欧拉有关。因此，欧拉开创的图论(现在称为网络科学理论)，当之无愧地处于网络金字塔的最顶端。
第二个里程碑：ER随机图理论
在20世纪五六十年代，两个匈牙利著名的数学家爱多士(Erdos)和瑞尼(Renyi)又一次对图论(网络科学理论)作出了第二个里程碑式的贡献，他们建立了著名的随机图理论，用相对简单的随机图来描述网络，简称ER随机图理论。用图论的语言和符号可以精确简洁地加以描述各种网络，图论不仅为数学家和物理学家提供了描述网络的共同语言和研究平台，而且至今图论的许多研究成果、结论和方法技巧仍然能够自然地应用到现在复杂网络的研究中去，成为网络研究的有力方法和工具之一。
爱多士被称为20世纪的欧拉，于1984年获得沃尔夫奖。他的一生充满着传奇色彩，一无财产、二无妻小、三无固定居所，完全是一个数学“苦行僧”。他善于与人合作，打破了数学领域的喜欢个人独立研究的传统，一生有480多个合作者，留下约1475篇文章，还与那些伟大的理论物理学家和数学家，如爱因斯坦、哥德尔、奥本海默等有密切的学术交往。
第三个里程碑：小世界现象与无标度特性
1998年，网络科学又一次取得突破性进展，出现了第三个里程碑。美国的瓦茨和斯特罗加茨首先冲破了ER理论的框框，发表了题为《“小世界”网络的群体动力行为》的论文，他们推广了“六度分离”的科学假设，提出了小世界网络模型。“六度分离”来自对社会调查的推断，指在大多数人中，任意两个素不相识的人通过朋友的朋友，平均最多通过6个人就能够彼此认识。2003年，瓦茨领导的研究小组发表一个实验报告，他们利用互联网在全世界范围内检验了上述惊人的“六度分离”假说，有6万多志愿者参与利用电子邮件通信实验，确实不到6步就实现了他们的假设，从而利用互联网初步验证了小世界现象。可见，瓦茨和斯特罗加茨的研究结果进一步揭示了复杂网络的小世界效应。
从科学上，小世界效应包含两个基本特征量：平均路径长度APL(指网络中所有节点对之间的平均最短距离)和群聚系数C(用来衡量一个复杂网络的集团化程度)。APL越小越好，C越大越好，这样小世界效应就越突出。这个小世界效应有广泛的应用，可以设计所需要的工程网络和计算机网络等。
紧接小世界效应之后的另一个发现是：1999年美国的巴拉巴西和艾尔伯特发表了《随机网络中标度的涌现》论文，提出了一个无标度网络模型，发现了复杂网络的节点的度分布具有幂指数函数的规律。所谓节点的度是指与该节点连接的边数。度在不同的网络中所代表的含义不尽相同。例如，在城市航空交通网中，度分布表示城市之间的航线的多少和重要程度，度越大的城市，其重要性就越大；在社会网络中，度可表示个体的作用力和影响程度， 一个节点的度越大，一般表示在整个网络系统组织中的作用和影响就越大，反之亦然。因为幂指数函数在双对数坐标中是一条直线，这个分布与系统特征长度无关，所以这个特性被称为无标度性质。它反映网络中度分布的不均匀性，只有很少数的节点与其他节点有很多的连接，成为“中心节点”，而大多数节点度很小。
这个无标度特性是一把“双刃剑”，一是可使网络对意外故障具有惊人的抗攻击能力；另一面对协同式攻击则很脆弱，一旦击中少数“中心节点”，就会导致整个网络崩溃。因此，人们为了避免网络因遭受攻击或意外事故导致的崩溃发生，最有效的办法就是保护好网络中节点度最大和次大的少数“中心节点”。
由巴拉巴西等入编著的《网络的结构与动力学》专著，在国际上产生了广泛而深刻的影响。由于巴拉巴西在网络科学方面的杰出贡献，他于2006年获得了美国冯·诺依曼计算机金奖。这标志着网络研究进入了网络科学的新时代，由此诞生了一门崭新的科学——网络科学。此后，网络科学的文章铺天盖地，网络科学的综述和专著不断涌现，从物理学到生物学，从社会科学到技术网络，从工-程技术到经济管理等众多领域，受到了人们的空前的关注和广泛的重视。因此，这个阶段树起了网络科学的第三个里程碑，极大促进了网络科学及其应用的发展。
网络科学的广阔应用前景
首先，我们举一个军事实例来说明。1991年海湾战争中，当时美军在网络中心作战实践中暴露出一个关键的问题：战后发现伊军网络使用的是当时市场上的因特网路由器，具有先进的动态路由选择技术，使得伊军指挥控制网络具有较好的线路恢复和抗打击能力。因为战争中美军没有对这些路由器进行有效的打击，所以迟迟没能完全切断伊军指挥控制网络，直到最后伊军还保留一条主要干线的光纤电缆。这是现代军事史上最早的一个对因特网攻击的战例。
一直到2003年，巴拉巴西把无标度网络的发现应用于因特网攻击的实验及定量分析，才发现只要进行一次有组织的协同攻击，使5％～10％的节点度大的所谓“中心节点”同时失效，就可使整个因特网系统崩溃。也就是说，只要首先去除具有最大度的节点，再去除次大度的节点，依次类推，就会导致整个网络的崩溃。所以，如果美军能有组织地协同攻击伊军网络中心节点，就能很快地切断伊主要干线的光纤电缆，从而必然加速战争胜利的进程。
有鉴于此，美国海军首次提出“网络作战中心”概念。美国国防部进一步提出了网络中心作战概念框架，以实现美军向网络中心作战的转型。这一任务的复杂性、前沿性，堪比当年美国的“曼哈顿”原子弹工程及“阿波罗”登月工程。
我们同时可以从网络的安全问题来说明网络科学研究的重要性和迫切性。人们不会忘记“爱虫”、“熊猫烧香”等病毒在互联网上大肆传播，震惊世界的“北美大停电”，由于台湾地震演变成史无前例的亚太区通讯网络大灾难等等。人们应该如何阻止和控制病毒在复杂网络上传播蔓延?如何有效地防止黑客侵入?怎样来设计出具有强鲁棒性(能够有效抵抗意外故障和攻击能力)的复杂网络以防止网络上的一系列级联效应?怎样消除不断恶化的生态环境网络而保持生态环境良性平衡等等。这一系列棘手问题无不与社会生活息息相关，涉及到因特网、万维网、各种交通运输网、电力网、各种通信网络、卫星电视网、电子邮件网、生态环境网络和食物链网等复杂网络。一句话，世界上多种多样网络的安全是一个首要问题。
当前，迫切需要网络科学研究的重大问题之一是：对于复杂的、多层次的、全球性的因特网，如何从全局着手，优化网络安全性能和抗打击能力，从根本上消除在网络拓扑结构上存在的不安全因素，预防未来可能发生的灾难性攻击。为此，需要解决一系列具体问题，诸如在故障和蓄意攻击等情况下能快速自动恢复的网络拓扑结构和技术；全球规模的网络监控、入侵检测、网络取证和防范犯罪的网络拓扑结构及相关理论、方法和技术：建立因特网的模型、仿真系统和测试平台，它包含百万级节点并能模拟和预测因特网的复杂行为。这些问题的解决将大大推进人类物质和精神文明的建设，造福于人类。(文章代码：0405)
[责任编辑]庞云
第一个里程碑：欧拉图论
网络科学首先是得益于图论和拓扑学等应用数学的发展。历史上，多位杰出数学家各自独立地建立和研究过图论，他们的贡献功不可没。所谓图论就是由一些点按照一定方式连线组成的一个图(集合)。关于图论的文字记载最早出现在1736年瑞士数学家欧拉的论著中，他所考虑的原始问题具有很强的实际背景，那就是著名的哥尼斯堡七桥问题。
哥尼斯堡是当时东普鲁士的首都，今俄罗斯加里宁格勒市，普莱格尔河横贯其中，这条河上建有七座桥，将河中间的两个岛和河岸联结起来。人们闲暇时经常在这上边散步，有人提出：能不能每座桥都只走一遍，最后又回到原来的位置。这个看起来很简单却很有趣的问题吸引了大家，很多人在尝试各种各样的走法，然而无数次的尝试都没有成功。
1736年，有人带着这个问题找到了当时的大数学家欧拉，欧拉经过一番思考，很快就用一种独特的方法给出了解答。他把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线，如图所示，A、B、C、D表示陆地。于是这个问题就简化成，能不能用一笔就把这个图形画出来。经过进一步的分析，欧拉得出结论：不可能每座桥都走一遍，最后回到原来的位置，并且给出了所有能够一笔画出来的图形所应具有的条件。这项工作使欧拉成为图论(及拓扑学)的创始人。
欧拉的研究开创了图论这门新的数学分支，欧拉因此被誉为“图论之父”。这是第一代科学家对网络科学的开创性贡献。
1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个节点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个节点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起国际上广泛的注意和研究。
在图论的历史中，还有一个最著名的问题——四色猜想，它也是世界近代三大数学难题之一。首先提出四色猜想的人是英国人弗南西斯·格思里，他在给地图着色时，发现了一种有趣的现象：“每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”1878～1880年两年间，著名律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文。但后来数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。所以它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年，美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了i00亿判断，终于完成了四色定理的证明。当然，不少数学家还在探索一种更简捷明快的书面证明方法。
在拓扑学的发展历史中，还有一个著名而且重要的关于多面体的定理也和欧拉有关。因此，欧拉开创的图论(现在称为网络科学理论)，当之无愧地处于网络金字塔的最顶端。
第二个里程碑：ER随机图理论
在20世纪五六十年代，两个匈牙利著名的数学家爱多士(Erdos)和瑞尼(Renyi)又一次对图论(网络科学理论)作出了第二个里程碑式的贡献，他们建立了著名的随机图理论，用相对简单的随机图来描述网络，简称ER随机图理论。用图论的语言和符号可以精确简洁地加以描述各种网络，图论不仅为数学家和物理学家提供了描述网络的共同语言和研究平台，而且至今图论的许多研究成果、结论和方法技巧仍然能够自然地应用到现在复杂网络的研究中去，成为网络研究的有力方法和工具之一。
爱多士被称为20世纪的欧拉，于1984年获得沃尔夫奖。他的一生充满着传奇色彩，一无财产、二无妻小、三无固定居所，完全是一个数学“苦行僧”。他善于与人合作，打破了数学领域的喜欢个人独立研究的传统，一生有480多个合作者，留下约1475篇文章，还与那些伟大的理论物理学家和数学家，如爱因斯坦、哥德尔、奥本海默等有密切的学术交往。
第三个里程碑：小世界现象与无标度特性
1998年，网络科学又一次取得突破性进展，出现了第三个里程碑。美国的瓦茨和斯特罗加茨首先冲破了ER理论的框框，发表了题为《“小世界”网络的群体动力行为》的论文，他们推广了“六度分离”的科学假设，提出了小世界网络模型。“六度分离”来自对社会调查的推断，指在大多数人中，任意两个素不相识的人通过朋友的朋友，平均最多通过6个人就能够彼此认识。2003年，瓦茨领导的研究小组发表一个实验报告，他们利用互联网在全世界范围内检验了上述惊人的“六度分离”假说，有6万多志愿者参与利用电子邮件通信实验，确实不到6步就实现了他们的假设，从而利用互联网初步验证了小世界现象。可见，瓦茨和斯特罗加茨的研究结果进一步揭示了复杂网络的小世界效应。
从科学上，小世界效应包含两个基本特征量：平均路径长度APL(指网络中所有节点对之间的平均最短距离)和群聚系数C(用来衡量一个复杂网络的集团化程度)。APL越小越好，C越大越好，这样小世界效应就越突出。这个小世界效应有广泛的应用，可以设计所需要的工程网络和计算机网络等。
紧接小世界效应之后的另一个发现是：1999年美国的巴拉巴西和艾尔伯特发表了《随机网络中标度的涌现》论文，提出了一个无标度网络模型，发现了复杂网络的节点的度分布具有幂指数函数的规律。所谓节点的度是指与该节点连接的边数。度在不同的网络中所代表的含义不尽相同。例如，在城市航空交通网中，度分布表示城市之间的航线的多少和重要程度，度越大的城市，其重要性就越大；在社会网络中，度可表示个体的作用力和影响程度， 一个节点的度越大，一般表示在整个网络系统组织中的作用和影响就越大，反之亦然。因为幂指数函数在双对数坐标中是一条直线，这个分布与系统特征长度无关，所以这个特性被称为无标度性质。它反映网络中度分布的不均匀性，只有很少数的节点与其他节点有很多的连接，成为“中心节点”，而大多数节点度很小。
这个无标度特性是一把“双刃剑”，一是可使网络对意外故障具有惊人的抗攻击能力；另一面对协同式攻击则很脆弱，一旦击中少数“中心节点”，就会导致整个网络崩溃。因此，人们为了避免网络因遭受攻击或意外事故导致的崩溃发生，最有效的办法就是保护好网络中节点度最大和次大的少数“中心节点”。
由巴拉巴西等入编著的《网络的结构与动力学》专著，在国际上产生了广泛而深刻的影响。由于巴拉巴西在网络科学方面的杰出贡献，他于2006年获得了美国冯·诺依曼计算机金奖。这标志着网络研究进入了网络科学的新时代，由此诞生了一门崭新的科学——网络科学。此后，网络科学的文章铺天盖地，网络科学的综述和专著不断涌现，从物理学到生物学，从社会科学到技术网络，从工-程技术到经济管理等众多领域，受到了人们的空前的关注和广泛的重视。因此，这个阶段树起了网络科学的第三个里程碑，极大促进了网络科学及其应用的发展。
网络科学的广阔应用前景
首先，我们举一个军事实例来说明。1991年海湾战争中，当时美军在网络中心作战实践中暴露出一个关键的问题：战后发现伊军网络使用的是当时市场上的因特网路由器，具有先进的动态路由选择技术，使得伊军指挥控制网络具有较好的线路恢复和抗打击能力。因为战争中美军没有对这些路由器进行有效的打击，所以迟迟没能完全切断伊军指挥控制网络，直到最后伊军还保留一条主要干线的光纤电缆。这是现代军事史上最早的一个对因特网攻击的战例。
一直到2003年，巴拉巴西把无标度网络的发现应用于因特网攻击的实验及定量分析，才发现只要进行一次有组织的协同攻击，使5％～10％的节点度大的所谓“中心节点”同时失效，就可使整个因特网系统崩溃。也就是说，只要首先去除具有最大度的节点，再去除次大度的节点，依次类推，就会导致整个网络的崩溃。所以，如果美军能有组织地协同攻击伊军网络中心节点，就能很快地切断伊主要干线的光纤电缆，从而必然加速战争胜利的进程。
有鉴于此，美国海军首次提出“网络作战中心”概念。美国国防部进一步提出了网络中心作战概念框架，以实现美军向网络中心作战的转型。这一任务的复杂性、前沿性，堪比当年美国的“曼哈顿”原子弹工程及“阿波罗”登月工程。
我们同时可以从网络的安全问题来说明网络科学研究的重要性和迫切性。人们不会忘记“爱虫”、“熊猫烧香”等病毒在互联网上大肆传播，震惊世界的“北美大停电”，由于台湾地震演变成史无前例的亚太区通讯网络大灾难等等。人们应该如何阻止和控制病毒在复杂网络上传播蔓延?如何有效地防止黑客侵入?怎样来设计出具有强鲁棒性(能够有效抵抗意外故障和攻击能力)的复杂网络以防止网络上的一系列级联效应?怎样消除不断恶化的生态环境网络而保持生态环境良性平衡等等。这一系列棘手问题无不与社会生活息息相关，涉及到因特网、万维网、各种交通运输网、电力网、各种通信网络、卫星电视网、电子邮件网、生态环境网络和食物链网等复杂网络。一句话，世界上多种多样网络的安全是一个首要问题。
当前，迫切需要网络科学研究的重大问题之一是：对于复杂的、多层次的、全球性的因特网，如何从全局着手，优化网络安全性能和抗打击能力，从根本上消除在网络拓扑结构上存在的不安全因素，预防未来可能发生的灾难性攻击。为此，需要解决一系列具体问题，诸如在故障和蓄意攻击等情况下能快速自动恢复的网络拓扑结构和技术；全球规模的网络监控、入侵检测、网络取证和防范犯罪的网络拓扑结构及相关理论、方法和技术：建立因特网的模型、仿真系统和测试平台，它包含百万级节点并能模拟和预测因特网的复杂行为。这些问题的解决将大大推进人类物质和精神文明的建设，造福于人类。(文章代码：0405)
[责任编辑]庞云