728
小白學數據：小世界網絡中的大世界
◆ ◆ ◆
導讀
你是否有過這樣的經曆——在火車上或者飛機上，遇到一個陌生人，因為排遣旅途中的無聊時光，你們聊了起來，後來越聊越嗨，最後你們發現竟然會有共同的朋友。
原來周圍的人際圈子真小，你會不由得感慨一句，我們真的是生活在“小世界”—地球村裏啊。在我們時時感歎世界很小的時候，早有科學家們已經通過理論和實踐證明，這就是所謂的小世界網絡。額，這個世界就是這樣，在我們睡醒之後，突然發現世界變了。
Anyway，讓我們也來站在巨人的肩膀上，窺探一下小世界網絡中的大世界。
那麼問題來了——
從很大的人口中任意挑出兩個人，這兩個人彼此認識的概率有多大？
任意挑出的兩個人當中要達到彼此認識的最短鏈接（中間相隔人數）是多長？
（上圖為時代周刊刊出的薩達姆人物關係網絡，把每個人看成節點，有聯係的兩個人即有一條連邊，可以繪製這樣的關係網絡）
小白：首先，請解釋下什麼叫小世界網絡吧~
答：依循小白的慣用做法，咱們顧名思義一下，小世界網絡，就是指網絡很小，小到，你想和世界上任何另外一個陌生人建立關係，隻需要6個左右的中間人。
小白：厲害！這是怎麼發現的？
答：小世界網絡的曆史，可以追溯到1929年。
◆ ◆ ◆
小世界網絡曆史
1929 年，當時，有一個著名的匈牙利著名作家考林蒂（F.Karinthy），他在其短篇小說《鏈條》中給出了著名的“六度分隔”假說。小說中的一個人可以通過其認識的網球冠軍、網球冠軍的球友瑞典國王、瑞典國王又是諾貝爾獎的頒獎者這一路徑，以簡單明了的方式就與一個諾貝爾獎的獲得者連接上了。考林蒂甚至將自己與遠在美國的福特汽車公司的一個工人，僅僅通過三個中間人就聯係了起來。考林蒂的關於人與人之間最多需要 5 層關係就能聯係起來的推斷，可以說是六度分隔假說的最早表述，也是“小世界網絡”概念的雛形。
1967 年，美國哈佛大學社會心理學教授米爾格拉姆 (S. Milgram) 明確提出了“小世界問題”。他通過設計一個信件傳遞實驗，以驗證“六度分隔”假說，並使其成為“小世界問題”研究的基本概念。
米爾格拉姆以美國堪薩斯州的威奇托市（Wichita）和內布拉斯加州的奧馬哈（Omaha）作為實驗起點，在兩地隨機地選擇了 296 位誌願者，要求每位誌願者向指定的目標人——一位居住在馬薩諸塞州首府波士頓郊區的股票經紀人傳遞一封信件。實驗結果是其中的64位誌願者平均通過約5.3個中間人轉手後，成功地將信件送達到目標人手中。這與38年前匈牙利作家考林蒂的“5個相互認識的人”的假設驚人地吻合。米爾格拉姆由此得出結論：任意兩個人都可通過平均 6 個熟人聯係起來，這是“六度分隔”假說的一次成功的實驗驗證。米爾格拉姆實驗展示了大型社會網絡的兩個重要事實：大型社會網絡一定包含了豐富的最短路徑；人們隻需要通過大型社會網絡的局域信息，而不是全局信息，就可以找到這些最短路徑。
1990 年，米爾格拉姆的有趣實驗結果激發了美國百老匯劇作家格雷 (J. Guare)的創作靈感，他在電影《六度分隔》中留下了這樣一句經典台詞：“在這個世界上，任意兩個人之間，隻隔著 6 個人。在這星球上的任何兩人之間，隻有六度分離。”
1998 年，學術界關於“六度分隔”的研究也取得全新的進展。美國Cornell大學的博士生瓦茨（D. Watts）和他的導師斯特羅加茨（S. Strogatz）在《Nature》上發表了題為《Collective dynamic of ‘small-world’ networks》（《小世界網絡的集體動力學》）一文，在 “六度分隔”假設的基礎上，第一次提出了“小世界網絡”的概念和模型。他們把“六度分隔”現象歸類為可以由兩個網絡結構參數——較大的網絡群聚係數和較短的網絡平均距離來描述“小世界現象”。他們發現，在各種社會網絡、電力網絡、神經網絡、生物網絡中均存在小世界現象。
小白：好長的曆史……看來，小世界網絡是人類社會中，普遍存在的現象了。那這個網絡，是怎麼構建起來的呢？
答：其實，建立一個小世界網絡模型很簡單。
假設我們都是幼兒園的小朋友，圍在一起做遊戲。首先規定，我們隻能和離自己最近的，左右各K/2個小朋友之間係上繩子（K要是偶數，你懂的）。接著，幼兒園老師隨機的以概率p選取了若幹條繩子，規定繩子一端小朋友保持不動，另外一端的小朋友可以將繩子解開，並隨機選擇其餘小朋友進行重係。規定是：1、不可以自己和自己係繩子；2、如果我係向了你，你隻能再去找別人係繩子，不可以再選擇我了。
然後，現在想象，從天空中看我們和我們身上係著的繩子，這就構建起了一個小世界網絡模型，稱為小世界網絡模型的典型代表是瓦茨--斯特羅加茨（ WS）小世界網絡模型（如下圖）。
我們還可以用另外一種方式來構建小世界網絡。首先的規定是一樣的，自己隻能和左右各k/2個小朋友係上繩子。然後，幼兒園老師以概率P隨機的選取NK/2對小朋友，並在他們之間再係上繩子，規定是：1、不能重複係兩根繩子在同樣兩個小朋友身上；2、不能將一條繩子隻綁在一個小朋友身上。這就是與紐曼--瓦茨（ NW）小世界網絡模型（如下圖）。
◆ ◆ ◆
小世界網絡的實例
小白：你說世界上存在很多小世界網絡現象。能舉幾個例子嗎？
答：好的。
實例1：互聯網的節點是各個路由器，連邊則是連接各個路由器的光纖。在 1995~1999 年對於互聯網網站及路由器層次都進行了計算，發現互聯網的平均路徑長度是 L= 4.0
實例2：科學引文網絡的節點是發表於科學刊物上的各篇論文，連邊則是互相之間的引用，科學引文網絡也是典型的小世界網絡。
實例3：語言網絡也是小世界網絡。每一個單詞是一個節點，兩個單詞相連接出現在一個句子中即為有連邊。據計算，兩個單詞之間的平均距離是 d = 2~3 (Romaine, 1992)
實例4：2011年Facebook驗證“六度分離”理論，Facebook和米蘭大學公布了共同研究結果，這項研究以Facebook上的721,000,000用戶數據為基礎，通過精確的網絡算法計算，得出每兩個用戶之間平均通過4.74個間接人就能夠建立聯係。在2008年，類似算法測算出的平均分離度還是5.28，如今已經降低至4.74。
小白：這樣看來，那豈不是我和我偶像之間的距離，隻差大概6個人？想想好激動！！
答：呃……可是，即使你知道你與世界上隨機選取的一個人之間的距離也許並不大，但是這並不意味著你就能輕而易舉地找到連接你們的那些人。網絡的可搜索性是與網絡結構關聯在一起的，也就是說，你是否能找到連接你們之間的那些人，是和你與你偶像之間存在的社交網絡結構所關聯的。20世紀末美國Cornell大學的喬恩·克萊因伯格（J. Kleinberg）關於小世界網絡可搜索性的研究是網絡科學的重要突破。現在把每個人都看成一個節點。在小世界網絡上可以有效地實施導航（或搜索）是有條件的前提條件是：，即網絡中的節點在“距離”上是均勻分布的，且網絡中兩節點之間隨機添加長程連接（捷徑）的概率是基於兩節點間的“距離”。
而在實際網絡中，節點的“距離”分布往往是不均勻的，且兩節點間是否實現長程連接（添加捷徑）既有“距離”的因素，也有非“距離”的因素在起作用，如節點在動力學行為上的慣性與情感等。
例如，假設節點之間隨機建立聯係的概率正比於節點之間距離倒數的a冪次，則隻有當a等於網絡的維數時（如對一維網絡，a=1，對二維網絡，a=2），可以最有效的實施搜索。冪次a 的特定取值說明網絡隻有特定的結構才使尋找最短路徑成為可能，這也正是米爾格拉姆實驗隻有在小世界網絡中才能成功的原因。這部分的模型和實證相當有趣，可以參考文獻【2】P245~266.
小白：你說，世界上有很多小世界網絡現象。到目前為止，給我感覺就是社交網絡一定是一個小世界網絡。那麼，還有其他什麼問題可以利用小世界網絡模型來解釋嗎？
答：那我們再來談談同步問題。在自然科學和社會科學中都廣泛存在著同步問題。如一場精彩表演結束後，觀眾給予的熱烈掌聲，往往都是從最初零亂的鼓掌到最後趨於一致的、有節奏性的鼓掌。如果把同步問題放在複雜網絡科學的視域下進行研究，就是用網絡中的諸多節點來代表不同的動力係統（如不同的觀眾），網絡節點間的連邊代表不同節點（不同的觀眾）之間的相互作用。在不同的初始狀態下，由於彼此之間的相互作用，使眾多不同的動力係統（如不同觀眾）的狀態相互接近，並最終達到（或基本達到）全同狀態的過程，即網絡同步。
中國學者汪小帆、陳關榮最早研究了具有小世界結構性質的複雜網絡係統的同步問題。他們發現，小世界特性可以顯著地提高複雜網絡係統的同步能力，即小世界網絡實現同步的能力遠遠高於其對應的規則網絡。必須注意的是，“節點間的平均距離越小，同步能力越強”這一結論隻適用於小世界網絡，而對其他類型的複雜網絡不適用。從同步問題中，研究發現，有些網絡是無法自我同步的，必須要通過某種控製手段才有可能實現同步。我國學者提出的牽製控製（Pinning control），其基本思想是通過有選擇地對網絡中的少部分節點施加控製而使整個網絡達到所預期的行為。
還有，就是流行病傳播問題。例如，傳染病在人群中的流行、病毒在計算機網絡上的蔓延、謠言在人際社會中的擴散等，都可視為流行病在小世界網絡上的傳播問題。
再舉一個例子，博弈問題。具有爭鬥或競爭性的問題，往往可以通過博弈模型來進行描述與分析，這類問題又統稱為博弈問題，如生物體進化過程中的優勝劣汰問題，社會關係中的合作與背叛問題等。複雜網絡上的博弈問題，是指群體博弈者之間的關係構成了一個小世界網絡，基於對該網絡拓撲結構的全新認識，來研究群體博弈者之間的合作與競爭問題。
小白：如果我想深入了解一下小世界網絡，能給一些參考文章嗎？
答：實際上，基於數據的複雜係統的數學模型正以一種全新的視角快速發展成為一個新學科：網絡科學。網絡科學就是旨在探究複雜網絡的奧秘。關於小世界模型的聚類係數，平均距離和度分布等性質，有興趣的讀者可以參考書籍【2】。與《Collective dynamic of‘small-world’networks》這篇文章並列看做是網絡科學興起的標誌的另一篇開創性的文章是時為美國Dame大學物理係教授Laszlo Barabási及其博士生Albert於1999年10月在《Science》上發表的《Emergence of Scaling in Random Networks》（《隨機網絡中標度的湧現》）文章。這兩篇文章分別揭示了複雜網絡的小世界特征和無標度性質，並建立了相應的模型以闡述這些特性的產生機理。有機會我們再介紹無標度性質。
◆ ◆ ◆
結語
複雜性科學(Complexity Science)誕生於上世紀80年代。隨著網絡時代的到來，在本世紀得到了迅勐發展，英國著名物理學家霍金稱“21世紀將是複雜性科學的世紀”。複雜性科學是一門高度交叉的科學，它以社交網絡係統、金融係統、腦神經係統、交通係統等各種複雜性係統為研究對象，試圖揭示和解釋各種複雜係統的運行規律為主要任務，以提高人們認識世界、探究世界和改造世界的能力。尤其是近年海量大數據的湧現，為複雜性科學引入了新的科研範式。在一切都將被記錄，一切都將被數據化的網絡時代，讓我們一起探索數據背後的奧秘。
原文發布時間為：2016-10-17
本文來自雲棲社區合作夥伴“大數據文摘”，了解相關信息可以關注“BigDataDigest”微信公眾號
最後更新：2017-06-02 19:33:03