网络科学发展简史

时间：2023-02-25 02:27:01 | 来源：营销百科

时间：2023-02-25 02:27:01 来源：营销百科

网络科学发展简史：图论和拓扑学

网络科学首先得益于图论和拓扑学等应用数学的发展。关于图论的文字记载最早出现在欧拉1736年的论着中,他所考虑的原始问题具有很强的实际背景。在数学上,关于哥尼斯堡七桥问题、多面体的欧拉定理、四色问题等都是拓扑学发展史的重要问题。而在欧拉身后，一些数学大师如柯西、汉密尔顿、凯利、基尔霍夫、波利亚等都对图论作出了贡献，使这门科学得到了快速的发展。

1、哥尼斯堡七桥问题^[2]

哥尼斯堡是东普鲁士的首都,今俄罗斯加里宁格勒市,普莱格尔河横贯其中。18世纪在这条河上建有七座桥,将河中间的两个岛和河岸连结起来。人们闲暇时经常在这上边散步,有人提出:能不能每座桥都只走一遍,最后又回到原来的位置。这个看起来很简单却很有趣的问题吸引了大家,很多人在尝试各种各样的走法,然而无数次的尝试都没有成功。谁也没有做到,看来要得到一个明确、理想的答案决非那么容易。

1736年,有人带着这个问题找到了当时的大数学家欧拉,欧拉经过一番思考,很快就用一种独特的方法给出了解答。欧拉首先把这个问题简化,他把两座小岛和河的两岸分别看作四个点,而把七座桥看作这四个点之间的连线.欧拉图的研究开创了'图论'这门新的数学分支[7],因此,这是第一代科学家对网络的开创性贡献,于是欧拉被誉为图论之父。问题是要从这四块陆地中任何一块开始,通过每一座桥正好一次,再回到起点。即这个问题就简化成,能不能用一笔就把这个图形画出来。经过进一步的分析,欧拉得出结论———不可能每座桥都走一遍,最后回到原来的位置。并且给出了所有能够一笔画出来的图形所应具有的条件。这是拓扑学的'先声'。欧拉在1736年解决了这个问题,他用抽象分析法将这个问题化为第一个图论问题:即把每一块陆地用一个点来代替,将每一座桥用联接相应的两个点的一条线来代替,从而相当于得到一个图。欧拉证明了这个问题没有解,并且推广了这个问题,给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使欧拉成为图论〔及拓扑学〕的创始人。因此,关于哥尼斯堡七桥问题、多面体的欧拉定理、四色问题等成为拓扑学发展史上的着名问题。

2、四色问题（四色定理）

在图论的历史中,还有一个最着名的问题———四色猜想（四色定理）。提出四色猜想的人来自英国,有一段有趣的历史。1852年,毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时,发现了一种有趣的现象:'看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家都被着上不同的颜色。'每个国家必须由一个单连通域构成,而两个国家相邻是指它们有一段公共的边界,而不仅仅只有一个公共点。1872年,英国当时最着名的数学家凯利正式向伦敦数学学会提出了这个问题,于是四色猜想成了世界数学界关注的问题,它是图论中的一个着名的问题,并且是世界近代三大数学难题之一。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878~1880年两年间,着名律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文,宣布证明了四色定理。但后来数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久,泰勒的证明也被人们否定了。于是,人们开始认识到,这个貌似容易的题目,其实是一个可与费马猜想相媲美的难题。所以它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。进入20世纪以来,科学家们对四色猜想的证明基本上是按照肯普的想法在进行。电子计算机问世以后,由于演算速度迅速提高,加之人机对话的出现,大大加快了对四色猜想证明的进程。1976年,美国数学家阿佩尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿判断,终于完成了四色定理的证明。当然,不少数学家还在探索一种更简捷明快的书面证明方法。

随机图理论

两个匈牙利着名的数学家Paul Edo''s(保罗·爱尔德)和Alfred Renyi（阿尔弗雷德·莱利）,他们在20世纪50年代末和60年代合作发表了8篇论文，这8篇论文在历史上首次探讨了我们所处的相互关联的宇宙的基本问题：网络是如何形成的？建立了着名的随机图理论,奠定了随机网络理论的基础。这一理论最重要的假设为：网络节点之间的链接是随机选择建立连接的。他们认为网络图和它所代表的世界从根本上说是随机的。随机网络模型的前提是深刻的平等主义：我们完全随机的安排链接，因此所有的节点都有等同的机会获得链接。^[3]

他们用相对简单的随机图来描述网络,简称ER随机图理论,他们的最重要发现是ER随机图中许多重要性质都是随着网络规模的增大突然涌现的。他们创立的ER随机图理论为图类的阈函数和巨大分支涌现的相变等提供了研究网络,的一种重要的数学理论。

确实,用图论的语言和符号可以精确简洁地加以描述各种网络,图论不仅为数学家和物理学家提供了描述网络的共同语言和研究平台,而且至今图论的许多研究成果、结论和方法技巧仍然能够自然地应用到现在复杂网络的研究中去,成为网络科学研究的有力方法和工具之一。在长达40年的ER随机图对于图论理论的影响大而广泛。

小世界理论和六度分离

1998年,科学家迎来了复杂网络的又一次突破性进展,首先冲破了ER理论的框框的人是,美国康奈尔(Cornell )大学理论和应用力学系的博士生Watts及其导师Strogatz在《Nature》杂志上发表了题为《'小世界'网络的群体动力行为》的论文,提出了小世界网络模型。这实际上是20世纪60年代美国哈佛大学的心理学家Milgram曾经作过的着名的小世界实验的一种拓广,Milgram提出的'六度分离'(six degrees of separation )社会调查后的推断,它原意是指在美国大多数人中,任意两个人平均最多通过6个人就能够彼此认识。不管是谁如果想认识一个素不相识的人,只要通过六个他的朋友的朋友转达之后,一般就能够联系得上。人们常有这么体验,当参加国内外会议或访问或旅游时,经常与遇到一些新朋友交谈时,你很快就发现:他认识你的朋友,你认识他的朋友的朋友,于是大家不约而同地脱口而出:这个世界真小啊!这就是'小世界效应(现象)',这里包含了'六度分离概念'的基本思想,那么你现在想与世界上任何一个人(例如史蒂芬·霍金等)联系交朋友吗?咋看似乎不太可能。如果你真想联络到他,应该怎么办?你可这样做:找一个最有可能和他有联系的亲友,把问候转达给他,然后他也照样去找下一位亲友。这样你一共需要多少个亲友作为'中转站'就能找到对方呢?这个问题的答案或许有点让人吃惊:不论你想找地球上哪人(壮汉或名人),大约只需要6步,最后一步就是'中转'的最终目标。2003年哥伦比亚大学社会学系的的瓦茨(DuncanWatts)领导的研究小组在《科学》杂志上,发表实验报告,他们利用互联网在全世界范围内初步检验了上述惊人的假说,有六万多志愿者参与利用电子邮件通信试验,例如从分布世界各地某同学的同学进行通信试验表明,确实不到6步就实现了,这是利用互联网初步验证了小世界现象。但是这个试验还不够多,他们准备做上亿的互联网进一步试验。可见,Watts和Strogatz的研究结果进一步揭示了复杂网络的小世界效应。

无标度网络模型（Scale-free Network）

1999年美国圣母(Notre Dame )大学物理系的Barabási教授(见图1.3)及其博士生Albert在《Science》杂志上发表了题为《随机网络中标度的涌现》一文[3],提出了一个无标度网络模型,发现了复杂网络的无标度性质,并和M. Newmann,D. J. Watts共同编辑了'网络的结构与动力学'(The Structure and Dynamics,普林斯顿大学出版社,普林斯顿, 2003年)专着,该书在国际上产生了广泛的影响,引起了全世界的高度重视。正是他在网络科学方面的杰出贡献,因此于2006年获得了美国von Neumann (冯纽曼)计算金奖。

标志着复杂网络研究进入了网络科学的新时代,由此诞生了一门崭新的科学:网络科学。网络科学的二大发现,以及随后许多真实网络的实证研究表明,真实世界网络既不是规则网络,也不是随机网络,而是兼具小世界和无标度特性,具有与规则网络和随机图完全不同的统计特性。这在全世界学术界激起了千重浪,复杂网络文章铺天盖地,网络科学的综述和专着不断涌现[11~22],从物理学到生物学,从社会科学到技术网络,从工程技术到经济管理等众多领域,受到了人们的空前的广泛关注和重视,正在突飞猛进。