複雜網路綜述1——簡介

來自專欄複雜網路綜述2 人贊了文章

本文基於Mark Newman2003發表的論文——《The Structure and Function of Complex Networks》

網路在現實生活中無處不在，例如網際網路，社交網路和生物網路。多年來，研究者們不斷努力，研究出了一些技術和模型來幫助我們理解和預測這類複雜系統中的行為模式,像小世界效應、度分布、聚類、網路相關性、隨機圖模型、網路的生長和偏好連接模型，當然還有更重要的網路動力學模型。

網路，是由一些節點和節點之間的連邊組成的。數學上，網路也被叫做「圖」，圖論是離散數學中最重要的支柱。大數學家歐拉在1735年對哥尼斯堡七橋問題的證明被認為是圖論研究的起源，在二十世紀，圖論已經發展成了一門重要的學科。網路在社會科學中也被廣泛研究，早在二十世紀三十年代，社會學家就已經認識到人們之間連接模式對理解人類社會功能的重要性。典型的社會網路研究包括通過調查問卷的方式了解受訪者與他人的聯繫，這樣就可以通過反饋來構建一個網路，網路的節點代表個體，連邊代表個體之間的聯繫。這類研究強調中心性（某些個體有著很強的影響力）和連接性（個體是如何通過網路相連的）。接下來的幾十年中，大量的研究從分析單個的小規模網路和網路中節點和連邊的特點轉移到分析大規模網路

的統計特性。計算機和通信網路的普及促進了新方法的形成，使得在比以往更大規模的網路上收集和分析數據成為可能。這種規模上的改變導致了在分析方法上相應的改變，許多問題在大規模的網路上不再適用。例如，在一個社交網路分析中，你也許會問：「對於網路的連通性，網路中的哪個節點會是最關鍵的？如果它被移除之後，網路變得不再連通」，但是這個問題在擁有幾百萬個節點的網路中變得不再有意義，因為在這樣的網路中，沒有哪個節點會有這樣的影響力。另一方面，你也可能會問，「在某種條件下，需要移除多大比例的節點會影響到網路的連通性？」，這類問題在大規模網路中有真正的意義。

然而，近年來有關研究方法的改變還有一個十分重要的原因，儘管它的重要性經常被低估。對於一個只有幾十個或者幾百個節點的網路，最直接的方法就是將點和邊畫成一張圖，通過這張圖來分析網路結構和一些特性。在之前，這是網路分析的主要方法，因為人的眼睛本身就是一個強大的分析工具。但是，當網路中的節點有百萬個甚至上億個時，人的眼睛就無法直接從圖中直接分析出網路結構了。最近形成的量化大規模網路的統計方法是找到一種可以在網路分析中代替人的眼睛的工具，就像二十世紀時那樣。這種統計方法回答了在無法真正看到網路時，如何描述這個網路看起來像什麼」的問題。它試圖解決三件事：第一，找出可以刻畫網路系統中結構和行為的統計特性，例如路徑長度和度分布，並且給出衡量這些統計特性正確的方法；第二，構建網路模型以便幫助我們理解這些統計特性背後的真正意義——它們是如何形成現在的樣子的以及它們之間是交互的；第三，基於這些統計特性，預測網路系統將要表現出的行為和個體的局部規則，例如，網路結構是如何影響網際網路上的流量、搜索引擎的性能，或者是如何影響社會或生物網路上的動力學演變的。學術界從大量的學科中汲取精華，在前兩個目標（刻畫網路結構並對其建模）中已經取得巨大的進展，但是在研究網路結構的影響方面才剛剛開始。

由一些點和它們之間的連邊組成的網路是一種最簡單的網路，然而還有一些網路要比這複雜一些。例如，在網路中存在不止一種類型的節點，或者多種類型的連邊，並且節點和連邊有著各自的特性。以社交網路為例，節點可能代表男性，也可能代表女性，又或者是不同國家、不同地域、不同年齡、不同收入的人。連邊可能代表朋友關係，也可能是敵對關係，或者僅僅是地理位置離得近。連邊上可以有權重，表示兩個人的熟悉程度。連邊也可以是有向的，從一個點指向另一個點，由有向邊組成的圖稱為有向圖，通信網路可以看成是一個有向圖，因為信息只能單向流動。有向圖可以是循環的，意味著圖中包含一個閉圈。

網路中也可以包含超邊——一條邊可以連接任意數量的頂點。由超邊組成的圖稱為超圖。例如，超邊可以用來表示社會網路中的家庭關係紐帶。圖也可以用多種方式來劃分，例如二分圖，它包括兩種類型的節點，只在這兩種不同類型的節點間才存在連邊。最簡單的例子就是天貓上的用戶可以看成一類節點，商品看成另一類節點，那麼用戶購買商品的網路就是一個二分圖。