【正文】 簡介 : 復雜網絡理論及其應用 王繼民 2021年 5月 21日 信息管理系 outline ?小世界實驗 六度分離、 Erdos數、 bacon數等 ?一些實際的復雜網絡系統(tǒng) Web、科學家合作網絡、經濟網絡、交通網絡、疾病傳播 等 ?復雜網絡的靜態(tài)幾何量 度分布、聚類系數、平均路徑長度等 ?網絡拓撲的基本模型及其性質 隨機網絡、 Small World網絡、 Scale Free網絡等 ?近幾年的研究態(tài)勢 發(fā)展歷程、會議、論文、軟件、實證等 信息管理系 小世界實驗 六度分離 ? 我們或許有過這樣的經歷：偶爾碰到一個陌生人，同他聊了一會后發(fā)現你認識的某個人居然他也認識，然后一起發(fā)出”這個世界真小”的感嘆。那么對于世界上任意兩個人來說，借助第三者、第四者這樣的間接關系來建立起他們兩人的聯(lián)系平均來說最少要通過多少人呢？ ? 美國社會心理學家斯坦利 ?米爾格倫 (Stanley Milgram)在 1967年通過一些實驗后得出結論：中間的聯(lián)系人平均只需要 5個。他把這個結論稱為” 六度分離 ” (six degrees of separation)。 ? 六度分離 : 平均只要通過 5個人，你就能與世界任何一個角落的任何一個人發(fā)生聯(lián)系。這個結論定量地說明了我們世界的”大小”，或者說人與人關系的緊密程度。 ? 30多年來，六度分離理論一直被作為社會心理學的經典范例之一。 ? 盡管如此，實際上這個理論并沒有得到嚴格的證實。美國心理學教授朱迪斯 ?克蘭菲爾德 (Judith Kleinfeld)對米爾格倫最初的實驗提出不同意見，因為她發(fā)現實驗的完成率極低。 信息管理系 小世界實驗 六度分離 ? 米爾格倫的 實驗過程 是：他計劃通過人傳人的送信方式來統(tǒng)計人與人之間的聯(lián)系。 ? 首先把信交給志愿者 A，告訴他信最終要送給收信人 S。如果他不認識 S，那么就送信到某個他認識的人 B手里，理由是 A認為在他的交集圈里 B是最可能認識 S的。但是如果 B也不認識 S，那么 B同樣把信送到他的一個朋友 C手中， ……，就這樣一步步最后信終于到達 S哪里。這樣就從 A到 B到 C到 ……最后到S連成了一個鏈。斯坦利 ?米爾格倫就是通過對這個鏈做了統(tǒng)計后做出了六度分離的結論。 ? 然而在這個實驗中，實際上只有三分之一的信送到了收信人哪里，因此實驗的完成率很低。 信息管理系 小世界實驗 Erdos數 ? Paul Erdos((19131996)， 出生于匈牙利的猶太籍數學家，被公認為本世紀最偉大的天才之一。 ? Erdos畢生發(fā)表的論文超過 1500篇 （在數學史上僅次于歐拉 (Euler ， 17071783))，超長的合作者名單 ,合作者超過 450位 。但若加上別人所做但曾獲他關鍵性的提示之論文，則他的論文應有數萬篇。 ? 他的 研究領域 主要是數論和組合數學，但他的論文中涵蓋的學科有逼近論、初等幾何、集合論、概率論、數理邏輯、格與序代數結構、線性代數、群論、拓撲群、多項式、測度論、單復變函數、差分方程與函數方程、數列、 Fourier分析、泛函分析、一般拓撲和代數拓撲、統(tǒng)計、數值分析、計算機科學、信息論等等。 ? Mathematical Reviews 曾把數學劃分為大約六十個分支， Erdos的論文涉及到了其中的 40%. 信息管理系 小世界實驗 Erdos數 ? Erdos從來沒有一固定的職位，從來不定居在一個地方，也沒有結婚，帶著一半空的手提箱，穿梭于學術研討會，浪跡天涯，頗富傳奇色彩。有人稱他為流浪學者 (wande ring scholar)。 ? 他效忠的是科學的皇后， 而非一特定的地方。各地都有熱心的數學家提供他舒適的食宿，安排他的一切，他則對招待他的主人，給出一些挑戰(zhàn)性的數學難題，或給予研究上的指導做為回饋。 ? 他可以和許多不同領域的數學家合作。數學家常將本身長久解決不了的問題和他討論，于是很快地一篇論文便誕生了。 信息管理系 小世界實驗 Erdos數 ? 數學家以下述方式來定義 Erdos數(Erdos number) : Erdos本人之 Erdos數為 0，任何人若曾與 Erdos合寫過論文，則其 Erdos數為 1。任何人若曾與一位 Erdos數為 l(且不曾與有更少的 Erdos數 ) 的人合寫過論文， 則他的 Erdos數為 2… ? 幾乎每一個當代數學家都有一個有限的 Erdos數，而且這個數往往非常小，小得出乎本人的預料。比如說證明Fermat大定理的 Andrew Wiles，他的研究方向與Erdos相去甚遠，但他的 Erdos數只有 3，是通過這個途徑實現的： ErdosAndrew OdlyzkoChris Wiles. 信息管理系 小世界實驗 Erdos數 ? Fields獎 得主的 Erdos數都不超過 5，（只有 Cohen和Grothendieck的 Erdos數是 5，） ? Nevanlinna獎得主的 Erdos數不超過 3，（只有 Valiant的Erdos數是 3） ? Wolf數學獎 得主的 Erdos數不超過 6，（只有 是 6，且只有 Kolmogorov是 5，） ? Steele獎的終身成就獎得主的 Erdos數不超過 4. ? 在具有有限 Erdos數的人名單中往往還能發(fā)現一些其他領域的專家，如 : 比爾蓋茲 (Bill Gates)， 他的 Erdos數是 4，通過如下途徑實現： ErdosPavol HellXiao Tie DengChristos H. PapadimitriouWilliam H. (Bill) Gates. ? 愛因斯坦是 2. 信息管理系