物流空间布局与优化方法

第三节

物流空间网络

结构特征与优化策略

1学习目标

了解物流网络的测度方法及典型物流网络的结构特征本节主要内容物流空间网络的测度模型及优化策略。SantaFe研究所的科学家合作网45经济物理学科学家合作网中药方剂网虽然中药方剂的数量很大，但目前还没有统计用的数据库。不得不用手工进行统计，因此统计的数据量受到很大限制。选用了1536付药方，681种药物进行了统计。节点（药物），边（在一付方剂中药物的相互作用）。方剂：药物、药物的相互作用构成的固定完全图局域世界，同时也是节点（药物）的合作成果。各个完全图通过共用的节点（药物）架起桥梁，构成网络。网络由完全图连接而成，如下图所示。6中药方剂网示意图点（药材），边（药材之间相互作用），局域世界（方剂）7中国淮扬菜肴网节点——食品边——菜肴中两种食品之间的相互作用通过公共节点连接构成中国淮扬菜肴网。329道菜肴，242个顶点（食品），1713条边。完全类似于中药方剂网的讨论。8社会网络9朋友关系网演员网科学家合著网科学引文网交通运输网络10城市公共交通网道路交通网航空网11小世界实验20世纪60年代美国哈佛大学的社会心理学家StanleyMilgram通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是6。这就是著名的“六度分离”（sixdegreesofseparation）推断。

为了检验“六度分离”的正确性，小世界实验—Bacon数。美国Virginia大学计算机系的科学家建立了一个电影演员的数据库，放在网上供人们随意查询。网站的数据库里目前总共存有近60万个世界各地的演员的信息以及近30万部电影信息。通过简单地输入演员名字就可以知道这个演员的Bacon数。

一个有趣的数学家故事：Erdǒs数证明小世界实验。复杂网络研究小故事小世界实验---六度分离米尔格伦的实验过程是：他计划通过人传人的送信方式来统计人与人之间的联系。首先把信交给志愿者A，告诉他信最终要送给收信人S。如果他不认识S，那么就送信到某个他认识的人B手里，理由是A认为在他的交集圈里B是最可能认识S的。但是如果B也不认识S，那么B同样把信送到他的一个朋友C手中，……，就这样一步步最后信终于到达S那里。这样就从A到B到C到……最后到S连成了一个链。斯坦利•米尔格伦就是通过对这个链做了统计后做出了六度分离的结论。然而在这个实验中，实际上只有三分之一的信送到了收信人那里，因此实验的完成率很低。小世界实验—六度分离我们或许有过这样的经历：偶尔碰到一个陌生人，同他聊了一会后发现你认识的某个人居然他也认识，然后一起发出”这个世界真小”的感叹。那么对于世界上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢？美国社会心理学家斯坦利•米尔格伦(StanleyMilgram)在1967年通过一些实验后得出结论：中间的联系人平均只需要5个。他把这个结论称为“六度分离”。六度分离:平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的”大小”，或者说人与人关系的紧密程度。30多年来，六度分离理论一直被作为社会心理学的经典范例之一。尽管如此，实际上这个理论并没有得到严格的证实。美国心理学教授朱迪斯•克兰菲尔德(JudithKleinfeld)对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低。小世界实验---Bacon数世界电影史上共产生了大约23万部电影，78多万名电影演员（参见互联网电影库）.KavinBacon在许多部电影中饰演小角色。Virginia大学的计算机专家BrettTjaden设计了一个游戏，他声称电影演员KevinBacon是电影界的中心。在游戏里定义了一个所谓的Bacon数：随便想一个演员，如果他（她）和KavinBacon一起演过电影，那么他（她）的Bacon数就为1；如果他（她）没有和Bacon演过电影，但是和Bacon数为1的演员一起演过电影，那么他的Bacon数就为2；依此类推。发现:在曾经参演的美国电影演员中，没有一个人的Bacon数超过4。小世界实验---Bacon数在网上有一个网页。网站的数据库里总共存有有783940个世界各地的演员的信息以及231,088部电影信息。通过简单地输入演员名字就可以知道这个演员的bacon数。目前比如输入StephenChow（周星驰）就可以得到这样的结果：周星驰在1991年的《豪门夜宴(Haomenyeyan)》中与洪金宝(SammoHungKam-Bo)合作；而洪金宝又在李小龙的最后一部电影，即1978年的《死亡的游戏（GameofDeath）》中与ColleenCamp合作；ColleenCamp在去年的电影《Trapped》中与KevinBacon合作。这样周星驰的Bacon数为3。对78万个演员所做的统计：演员的最大Bacon数仅仅为8，平均Bacon数仅为2.948。小世界实验---Erdos数PaulErdos((1913-1996)：是出生于匈牙利的犹太籍数学家，被公认为20世纪最伟大的天才之一。Erdos毕生发表的论文超过1500篇（在数学史上仅次于欧拉(Euler

，1707-1783))，超长的合作者名单,合作者超过450位。但若加上别人所做但曾获他关键性提示之论文，则他的论文应有数万篇。他的研究领域主要是数论和组合数学，但他的论文中涵盖的学科有逼近论、初等几何、集合论、概率论、数理逻辑、格与序代数结构、线性代数、群论、拓扑群、多项式、测度论、单复变函数、差分方程与函数方程、数列、Fourier分析、泛函分析、一般拓扑和代数拓扑、统计、数值分析、计算机科学、信息论等等。"MathematicalReviews"曾把数学划分为大约六十个分支，Erdos的论文涉及到了其中的40%.

小世界实验---Erdos数Erdos从来没有一个固定的职位，从来不定居在一个地方，也没有结婚，带着一半空的手提箱，穿梭于学术研讨会，浪迹天涯，颇富传奇色彩。有人称他为流浪学者(wandering

scholar)。他效忠的是科学的皇后，

而非一特定的地方。各地都有热心的数学家提供他舒适的食宿，安排他的一切，他则对招待他的主人，给出一些挑战性的数学难题，或给予研究上的指导做为回馈。他可以和许多不同领域的数学家合作。数学家常将本身长久解决不了的问题和他讨论，于是很快地一篇论文便诞生了。小世界实验---Erdos数数学家以下述方式来定义Erdos数(Erdos

number)

:

Erdos本人之Erdos数为0，任何人若曾与Erdos合写过论文，

则其Erdos数为1。任何人若曾与一位Erdos数为l(且不曾与有更少的Erdos数)

的人合写过论文，

则他的Erdos数为2…几乎每一个当代数学家都有一个有限的Erdos数，而且这个数往往非常小，小得出乎本人的预料。比如说证明Fermat大定理的AndrewWiles，他的研究方向与Erdos相去甚远，但他的Erdos数只有3，是通过这个途径实现的：Erdos--AndrewOdlyzko--ChrisM.Skinner--AndrewWiles.小世界实验---Erdos数

Fields奖得主的Erdos数都不超过5，（只有Cohen和Grothendieck的Erdos数是5，）

Nevanlinna奖得主的Erdos数不超过3，（只有Valiant的Erdos数是3）Wolf数学奖得主的Erdos数不超过6，（只有V.I.Arnold是6，且只有Kolmogorov是5，）Steele奖的终身成就奖得主的Erdos数不超过4.在具有有限Erdos数的人名单中往往还能发现一些其他领域的专家，如:比尔盖兹(BillGates)，他的Erdos数是4，通过如下途径实现：Erdos--PavolHell--XiaoTieDeng--ChristosH.Papadimitriou--WilliamH.(Bill)Gates.爱因斯坦的Erdos数是2.

复杂网络的统计特征节点度平均路径长度网络聚类系数网络的绝对效率，网络的相对效率网络可靠性度(degree)：节点i的度

ki

定义为与该节点连接的其他节点的数目。

★直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”（“能力大”）。

度分布函数p(k):随机选定节点的度恰好为k的概率节点的聚类系数（簇系数）：在简单图中，设节点v的邻集为N(v),|N(v)|=ki，则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1)★节点v的邻点间关系的密切程度

复杂网络的统计特征网络的聚类系数C：所有节点i的聚类系数Ci的平均值。（0C1）

C=0网络中所有节点都是孤立点

C=1网络中任意节点间都有边相连

★网络节点间联系的密切程度,体现网络的凝聚力

★许多大规模的实际网络都具有明显的聚类效应。事实上，在很多类型的网络(如社会关系网络)中，你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当N→∞时，C=O(1)。这意味着这些实际的复杂网络并不是完全随机