第三節

物流空間網絡

結構特征與優化策略

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)。這意味著這些實際的復雜網絡并不是完全隨機