物流空間布局與優(yōu)化方法

第三節(jié)

物流空間網(wǎng)絡(luò)

結(jié)構(gòu)特征與優(yōu)化策略

1學(xué)習(xí)目標

了解物流網(wǎng)絡(luò)的測度方法及典型物流網(wǎng)絡(luò)的結(jié)構(gòu)特征本節(jié)主要內(nèi)容物流空間網(wǎng)絡(luò)的測度模型及優(yōu)化策略。SantaFe研究所的科學(xué)家合作網(wǎng)45經(jīng)濟物理學(xué)科學(xué)家合作網(wǎng)中藥方劑網(wǎng)雖然中藥方劑的數(shù)量很大，但目前還沒有統(tǒng)計用的數(shù)據(jù)庫。不得不用手工進行統(tǒng)計，因此統(tǒng)計的數(shù)據(jù)量受到很大限制。選用了1536付藥方，681種藥物進行了統(tǒng)計。節(jié)點（藥物），邊（在一付方劑中藥物的相互作用）。方劑：藥物、藥物的相互作用構(gòu)成的固定完全圖局域世界，同時也是節(jié)點（藥物）的合作成果。各個完全圖通過共用的節(jié)點（藥物）架起橋梁，構(gòu)成網(wǎng)絡(luò)。網(wǎng)絡(luò)由完全圖連接而成，如下圖所示。6中藥方劑網(wǎng)示意圖點（藥材），邊（藥材之間相互作用），局域世界（方劑）7中國淮揚菜肴網(wǎng)節(jié)點——食品邊——菜肴中兩種食品之間的相互作用通過公共節(jié)點連接構(gòu)成中國淮揚菜肴網(wǎng)。329道菜肴，242個頂點（食品），1713條邊。完全類似于中藥方劑網(wǎng)的討論。8社會網(wǎng)絡(luò)9朋友關(guān)系網(wǎng)演員網(wǎng)科學(xué)家合著網(wǎng)科學(xué)引文網(wǎng)交通運輸網(wǎng)絡(luò)10城市公共交通網(wǎng)道路交通網(wǎng)航空網(wǎng)11小世界實驗20世紀60年代美國哈佛大學(xué)的社會心理學(xué)家StanleyMilgram通過一些社會調(diào)查后給出的推斷是：地球上任意兩個人之間的平均距離是6。這就是著名的“六度分離”（sixdegreesofseparation）推斷。

為了檢驗“六度分離”的正確性，小世界實驗—Bacon數(shù)。美國Virginia大學(xué)計算機系的科學(xué)家建立了一個電影演員的數(shù)據(jù)庫，放在網(wǎng)上供人們隨意查詢。網(wǎng)站的數(shù)據(jù)庫里目前總共存有近60萬個世界各地的演員的信息以及近30萬部電影信息。通過簡單地輸入演員名字就可以知道這個演員的Bacon數(shù)。

一個有趣的數(shù)學(xué)家故事：Erdǒs數(shù)證明小世界實驗。復(fù)雜網(wǎng)絡(luò)研究小故事小世界實驗---六度分離米爾格倫的實驗過程是：他計劃通過人傳人的送信方式來統(tǒng)計人與人之間的聯(lián)系。首先把信交給志愿者A，告訴他信最終要送給收信人S。如果他不認識S，那么就送信到某個他認識的人B手里，理由是A認為在他的交集圈里B是最可能認識S的。但是如果B也不認識S，那么B同樣把信送到他的一個朋友C手中，……，就這樣一步步最后信終于到達S那里。這樣就從A到B到C到……最后到S連成了一個鏈。斯坦利?米爾格倫就是通過對這個鏈做了統(tǒng)計后做出了六度分離的結(jié)論。然而在這個實驗中，實際上只有三分之一的信送到了收信人那里，因此實驗的完成率很低。小世界實驗—六度分離我們或許有過這樣的經(jīng)歷：偶爾碰到一個陌生人，同他聊了一會后發(fā)現(xiàn)你認識的某個人居然他也認識，然后一起發(fā)出”這個世界真小”的感嘆。那么對于世界上任意兩個人來說，借助第三者、第四者這樣的間接關(guān)系來建立起他們兩人的聯(lián)系平均來說最少要通過多少人呢？美國社會心理學(xué)家斯坦利?米爾格倫(StanleyMilgram)在1967年通過一些實驗后得出結(jié)論：中間的聯(lián)系人平均只需要5個。他把這個結(jié)論稱為“六度分離”。六度分離:平均只要通過5個人，你就能與世界任何一個角落的任何一個人發(fā)生聯(lián)系。這個結(jié)論定量地說明了我們世界的”大小”，或者說人與人關(guān)系的緊密程度。30多年來，六度分離理論一直被作為社會心理學(xué)的經(jīng)典范例之一。盡管如此，實際上這個理論并沒有得到嚴格的證實。美國心理學(xué)教授朱迪斯?克蘭菲爾德(JudithKleinfeld)對米爾格倫最初的實驗提出不同意見，因為她發(fā)現(xiàn)實驗的完成率極低。小世界實驗---Bacon數(shù)世界電影史上共產(chǎn)生了大約23萬部電影，78多萬名電影演員（參見互聯(lián)網(wǎng)電影庫）.KavinBacon在許多部電影中飾演小角色。Virginia大學(xué)的計算機專家BrettTjaden設(shè)計了一個游戲，他聲稱電影演員KevinBacon是電影界的中心。在游戲里定義了一個所謂的Bacon數(shù)：隨便想一個演員，如果他（她）和KavinBacon一起演過電影，那么他（她）的Bacon數(shù)就為1；如果他（她）沒有和Bacon演過電影，但是和Bacon數(shù)為1的演員一起演過電影，那么他的Bacon數(shù)就為2；依此類推。發(fā)現(xiàn):在曾經(jīng)參演的美國電影演員中，沒有一個人的Bacon數(shù)超過4。小世界實驗---Bacon數(shù)在網(wǎng)上有一個網(wǎng)頁。網(wǎng)站的數(shù)據(jù)庫里總共存有有783940個世界各地的演員的信息以及231,088部電影信息。通過簡單地輸入演員名字就可以知道這個演員的bacon數(shù)。目前比如輸入StephenChow（周星馳）就可以得到這樣的結(jié)果：周星馳在1991年的《豪門夜宴(Haomenyeyan)》中與洪金寶(SammoHungKam-Bo)合作；而洪金寶又在李小龍的最后一部電影，即1978年的《死亡的游戲（GameofDeath）》中與ColleenCamp合作；ColleenCamp在去年的電影《Trapped》中與KevinBacon合作。這樣周星馳的Bacon數(shù)為3。對78萬個演員所做的統(tǒng)計：演員的最大Bacon數(shù)僅僅為8，平均Bacon數(shù)僅為2.948。小世界實驗---Erdos數(shù)PaulErdos((1913-1996)：是出生于匈牙利的猶太籍數(shù)學(xué)家，被公認為20世紀最偉大的天才之一。Erdos畢生發(fā)表的論文超過1500篇（在數(shù)學(xué)史上僅次于歐拉(Euler

，1707-1783))，超長的合作者名單,合作者超過450位。但若加上別人所做但曾獲他關(guān)鍵性提示之論文，則他的論文應(yīng)有數(shù)萬篇。他的研究領(lǐng)域主要是數(shù)論和組合數(shù)學(xué)，但他的論文中涵蓋的學(xué)科有逼近論、初等幾何、集合論、概率論、數(shù)理邏輯、格與序代數(shù)結(jié)構(gòu)、線性代數(shù)、群論、拓撲群、多項式、測度論、單復(fù)變函數(shù)、差分方程與函數(shù)方程、數(shù)列、Fourier分析、泛函分析、一般拓撲和代數(shù)拓撲、統(tǒng)計、數(shù)值分析、計算機科學(xué)、信息論等等。"MathematicalReviews"曾把數(shù)學(xué)劃分為大約六十個分支，Erdos的論文涉及到了其中的40%.

小世界實驗---Erdos數(shù)Erdos從來沒有一個固定的職位，從來不定居在一個地方，也沒有結(jié)婚，帶著一半空的手提箱，穿梭于學(xué)術(shù)研討會，浪跡天涯，頗富傳奇色彩。有人稱他為流浪學(xué)者(wandering

scholar)。他效忠的是科學(xué)的皇后，

而非一特定的地方。各地都有熱心的數(shù)學(xué)家提供他舒適的食宿，安排他的一切，他則對招待他的主人，給出一些挑戰(zhàn)性的數(shù)學(xué)難題，或給予研究上的指導(dǎo)做為回饋。他可以和許多不同領(lǐng)域的數(shù)學(xué)家合作。數(shù)學(xué)家常將本身長久解決不了的問題和他討論，于是很快地一篇論文便誕生了。小世界實驗---Erdos數(shù)數(shù)學(xué)家以下述方式來定義Erdos數(shù)(Erdos

number)

:

Erdos本人之Erdos數(shù)為0，任何人若曾與Erdos合寫過論文，

則其Erdos數(shù)為1。任何人若曾與一位Erdos數(shù)為l(且不曾與有更少的Erdos數(shù))

的人合寫過論文，

則他的Erdos數(shù)為2…幾乎每一個當代數(shù)學(xué)家都有一個有限的Erdos數(shù)，而且這個數(shù)往往非常小，小得出乎本人的預(yù)料。比如說證明Fermat大定理的AndrewWiles，他的研究方向與Erdos相去甚遠，但他的Erdos數(shù)只有3，是通過這個途徑實現(xiàn)的：Erdos--AndrewOdlyzko--ChrisM.Skinner--AndrewWiles.小世界實驗---Erdos數(shù)

Fields獎得主的Erdos數(shù)都不超過5，（只有Cohen和Grothendieck的Erdos數(shù)是5，）

Nevanlinna獎得主的Erdos數(shù)不超過3，（只有Valiant的Erdos數(shù)是3）Wolf數(shù)學(xué)獎得主的Erdos數(shù)不超過6，（只有V.I.Arnold是6，且只有Kolmogorov是5，）Steele獎的終身成就獎得主的Erdos數(shù)不超過4.在具有有限Erdos數(shù)的人名單中往往還能發(fā)現(xiàn)一些其他領(lǐng)域的專家，如:比爾蓋茲(BillGates)，他的Erdos數(shù)是4，通過如下途徑實現(xiàn)：Erdos--PavolHell--XiaoTieDeng--ChristosH.Papadimitriou--WilliamH.(Bill)Gates.愛因斯坦的Erdos數(shù)是2.

復(fù)雜網(wǎng)絡(luò)的統(tǒng)計特征節(jié)點度平均路徑長度網(wǎng)絡(luò)聚類系數(shù)網(wǎng)絡(luò)的絕對效率，網(wǎng)絡(luò)的相對效率網(wǎng)絡(luò)可靠性度(degree)：節(jié)點i的度

ki

定義為與該節(jié)點連接的其他節(jié)點的數(shù)目。

★直觀上看，一個節(jié)點的度越大就意味著這個節(jié)點在某種意義上越“重要”（“能力大”）。

度分布函數(shù)p(k):隨機選定節(jié)點的度恰好為k的概率節(jié)點的聚類系數(shù)（簇系數(shù)）：在簡單圖中，設(shè)節(jié)點v的鄰集為N(v),|N(v)|=ki，則節(jié)點v的聚類系數(shù)定義為這ki個節(jié)點之間存在邊數(shù)Ei與總的可能邊數(shù)ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1)★節(jié)點v的鄰點間關(guān)系的密切程度

復(fù)雜網(wǎng)絡(luò)的統(tǒng)計特征網(wǎng)絡(luò)的聚類系數(shù)C：所有節(jié)點i的聚類系數(shù)Ci的平均值。（0C1）

C=0網(wǎng)絡(luò)中所有節(jié)點都是孤立點

C=1網(wǎng)絡(luò)中任意節(jié)點間都有邊相連

★網(wǎng)絡(luò)節(jié)點間聯(lián)系的密切程度,體現(xiàn)網(wǎng)絡(luò)的凝聚力

★許多大規(guī)模的實際網(wǎng)絡(luò)都具有明顯的聚類效應(yīng)。事實上，在很多類型的網(wǎng)絡(luò)(如社會關(guān)系網(wǎng)絡(luò))中，你的朋友同時也是朋友的概率會隨著網(wǎng)絡(luò)規(guī)模的增加而趨向于某個非零常數(shù)，即當N→∞時，C=O(1)。這意味著這些實際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機