複雜網路綜述2——現實世界中的網路

來自專欄複雜網路綜述

近些年來，大量的工作通過觀察真實網路的特性試圖對其建模，研究不同類型的網路具有重大意義。在這方面，Watts和Strogatz起了主要的推動作用，二人於1998年發表的論文《Collective dynamics of small-world networks》被公認為是一項開創性的工作，它從不同角度研究網路結構特性。寬泛的看，現實世界中的網路可以分為四種——社交網路、信息網路、技術網路和生物網路。

• 社交網路

社交網路是由一些人或者一些群體和他們之間的一些聯繫和交互模式構成的網路。過去研究個體間的朋友關係、公司間的商業關係和家庭間的近親婚姻關係都屬於這種網路。在各類學科中，社會科學在研究真實世界網路方面有著悠久的歷史，早期有記錄的工作有：1934年J.L.Moreno研究在小群體內的朋友關係網路；1941年Davis等人做的「southern women」的研究；1939年Elton Mayo等人以工廠工人為研究對象，提出了Rapoport數學模型，成為第一個強調各種網路中（不僅僅在社交網路中）度分布的重要性的模型。

另外一些重要的實驗，例如著名的由Milgram做的「小世界」實驗，儘管在這些實驗中並沒有構建出真實的網路，但它們無一例外都揭示了具體的網路結構。通過在熟人網路中讓參與者儘可能的將信件送達至一個特定的人，參與者需要指定最有可能認識該人的朋友，然後將信件轉交給朋友，因此得出在熟人網路中路徑長度的分布。實驗中大多數信件都丟失了，但是大約有四分之一的信件僅僅通過六個人就成功送至目標。儘管在Milgram的論文中沒有出現「six degrees of separation」這樣的字眼，但是該實驗被認為是六度分離理論的起源，該理論在1990年由Guare正式提出，而再早之前類似的研究要追溯到1979年Garfield的《Its a small world after all》。

傳統的社交網路研究受限於數據不精確、假設帶有主觀性和樣本數量小的問題。除了極少數像Milgram這樣獨創性的間接研究，數據採集大都是通過調查問卷的方式完成的，這種方法限制了網路的規模。此外，調查數據經常帶有主觀性，例如，不同的人可能對朋友的定義不同。儘管在消除這種差異性方面做出了很大的努力，但是不得不承認大多數研究中存在著大量不可控的誤差，這類問題Marsden做出了總結。

這些問題的出現使得很多研究者轉向其他的研究方法。一個豐富並且可靠的數據集是合作網路，在這種典型的「隸屬網路」中，參與者在不同的群組內合作，組內之間的參與者有連邊。一個典型的例子就是電影演員網路，如果兩個演員共同出演了一部電影，那麼就認為兩人之間有一條連邊；另外一個例子是公司董事網路，如果兩個董事隸屬同一個董事會，那麼他倆之間就會有連邊；還有像學術界的合作者網路，如果兩位學者共同發表一篇或者多篇論文，那麼他們之間就存在連邊；還有一種叫「共現網路」，在這種網路中，個體間如果包含相同內容則二者間會有鏈接，這種情況多出現在網頁或新聞報道之間。

另一個較為可靠的數據集是人們之間的通信網路。例如，可以構建一個網路，網路中兩人的連邊（有向）表示一封郵件從一個人發往另一個人。Aiello,Chung和Lu等人分析了一段時間內的電話網路，節點代表電話號碼，連邊代表從一次通話（一個電話號碼到另外一個電話號碼），儘管實驗只進行了幾天，這個網路也是巨大的——大約有5千萬個節點。Ebel,Mielsch和Bornholdt在Kiel大學的5000個學生中重構了email網路，節點代表郵件地址，有向邊代表從一個地址到另一個地址。Newman,Forrest和Balthrop等人對Email網路也做了深入研究。

• 信息網路

「信息網路」有時候也叫「知識網路」，學術論文之間的相互引用就是一個典型的信息網路。這些引用所形成的網路中，節點表示一篇文章，從A指向B的邊表示A引用了B，引用網路的結構反映了蘊含在節點內的信息結構。引用網路是非周期的，因為一篇文章只能引用已經被發表的文章，而不是未發表的。所以，網路中不存在閉圈，即使存在，也很少。

引用網路作為科學研究中的對象，在數據集的豐富性和精確性方面有著極大的優勢。對出版物進行定量研究最早要追溯到1926年由Alfred Lotka開創性的發現——Law of Scientific Productivity, 該發現表明，科學家發表的論文數服從power law分布，也即發表了k篇論文的科學家的數量為 人（ 為常數）。事實上，該發現也適用於藝術和人文科學 。由於Eugene Garfield等人在文獻計量學領域的工作推動了引用資料庫的開放，第一個正式的有關引用模式的工作在1960年進行。Price在之前更早的一篇文章中討論了引用網路，文章指出網路中的入度和出度都服從power law分布。從那之後，通過使用有史以來最好的引用資料庫，出現了許多關於引用網路的研究。

另一個十分重要的信息網路是萬維網(World Wide Web)，與引用網路不同的是，萬維網是周期的，裡面不存在對站點的自然排序，但是會包含閉圈。對於網頁的研究早在20世紀90年代就開始了，Albert、Kleinberg和Broder等人做出了突出的貢獻。

值得注意的是，數據是在網路上爬取的，通過超鏈接可以從一個網頁跳轉到另一個網頁。網頁只能通過指向它的鏈接被找到，一個網頁有越多的鏈接指向它，就越可能被找到。這表明，網路中有著較小入度的網頁的比例被低估了。這正好與引用網路形成對照，在引用網路中，一篇論文即使從未被引用過，也會出現在引用索引中（其實大多數論文從未被引用過）。

一些其他的信息網路則沒有得到廣泛研究。例如，Jaffe和Trajtenberg研究了美國專利引用網路，結果顯示在一些方面與學術論文的引用網路相似。還有一些學者關注P2P網路，這是一種虛擬的網路，它可以在計算機用戶間共享文件。Knuth等人研究在一個詞庫中，各個單詞之間的關係，這種網路也可以看成是一個信息網路，詞庫的使用者在網路中瀏覽單詞來找到想要的。然而，它也可以看做是一個代表語言結構的概念網路。

偏好網路是一個二分的信息網路，這種網路中包含兩類節點，分別代表個體和他們各自喜好的客體，比如書籍或電影，個體和客體之間存在連邊（邊上的權重表示喜好程度）。由此衍生出的協同過濾演算法和推薦系統可以預測個體的喜好，協同過濾演算法在推薦商品和定向投放廣告方面取得了巨大的成功。偏好網路還可以看做是社交網路，連邊不僅僅連接個體和客體，還可以存在個體與個體之間，Kautz等人使用了這種演算法。

• 技術網路

技術網路是用來分配一些商品或者資源的人工網路，比如電網。電網將高壓電在三相傳輸線上跨越一個或者多個城市進行傳輸，Watts和Strogatz, Watts, Amaral等人對電網進行了統計研究。其他的一些分散式網路，比如航空網，公路網、鐵路網、電話網路和運輸網路也有一些研究。

另一個被廣泛研究的網路是網際網路，這裡指的是由計算機通過物理連接形成的網路。網際網路上的計算機數量巨大且千變萬化，因此，網路結構只能在粗粒度上來衡量，要麼看路由器的數量，要麼看自治系統的數量。事實上，網際網路上的物理連接並不容易被觀察得到，因為基礎設施大都由分散的組織來管理。因此，研究者們通過路由器之間的數據交換來重構網路，這裡要用到一些網路技術，雖然不能保證重構的網路是完美的，但其基本結構保持不變。

然而這些技術網路都有一個有趣的特點——網路結構很大程度上由空間地理位置決定。電網，航空網，公路網，鐵路網，這些網路中相互連接的節點大都既能滿足某項功能，又能在地理位置上行得通，儘管現在還不是很清楚這些因素是如何相互作用的。

• 生物網路

大量的生物系統都可以用網路來表示，最經典的生物網路是代謝網路。Jeong, Fell和Wagner,Stelling等人對代謝網路做了大量的統計工作。

另外一個十分重要的生物網路是基因調控網路，基因的表達可以看做是轉錄並翻譯蛋白質的過程，這種過程因為其他蛋白質的出現而表現出兩種不同的行為——激活和抑制，因此，基因組本身就形成了一個switching網路，節點代表蛋白質，有向邊代表一種蛋白質的產生對另一種蛋白質的依賴。基因調控網路事實上是第一個我們試圖去建模的大規模動態網路。

另一個被大量研究的生物網路是食物鏈，頂點代表生物系統中的一個物種，有向邊從A指向B表示A捕食B。構建完整的食物鏈是一項艱難的任務，對食草動物的食物鏈做了徹底研究的是Jordano,Bascompte和Olesen等人，他們統計了至少53種不同的網路。

神經網路是另一種生物網路，刻畫真正的神經網路的拓撲結構是極其困難的，但是在一些小的例子中卻可以實現，最有名的例子是重構線蟲282個神經元網路。在對大腦神經網路結構的研究中，Sporns和Tononi,Edelman等人研究了大腦的功能區。

四種網路的一些例子：