近年來,學界關於複雜網路的研究正方興未艾。特別是,國際上有兩項開創性工作掀起了一股不小的研究複雜網路的熱潮。一是1998年Watts和Strogatz在Nature雜誌上發表文章,引入了小世界(Small-World)網路模型,以描述從完全規則網路到完全隨機網路的轉變。小世界網路既具有與規則網路類似的聚類特性,又具有與隨機網路類似的較小的平均路徑長度。(Watts&Strogatz,p.440-442)。二是1999年Barabasi和Albert在Science上發表文章指出,許多實際的複雜網路的連線度分布具有冪律形式。由於冪律分布沒有明顯的特徵長度,該類網路又被稱為無標度(Scale-Free)網路。(Barabasi&Albert,p.509-512)而後科學家們又研究了各種複雜網路的各種特性。(Strogatz,p.268-276)國內學界也已經注意到了這種趨勢,並且也開始展開研究。(吳金閃、狄增如,第18-46頁)加入複雜網路研究的學者主要來自圖論、統計物理學、計算機網路研究、生態學、社會學以及經濟學等領域,研究所涉及的網路主要有:生命科學領域的各種網路(如細胞網路、蛋白質-蛋白質作用網路、蛋白質摺疊網路、神經網路、生態網路)、Internet/WWW網路、社會網路,包括流行性疾病的傳播網路、科學家合作網路、人類性關係網路、語言學網路,等等;所使用的主要方法是數學上的圖論、物理學中的統計物理學方法和社會網路分析方法。
錢學森給出了複雜網路的一個較嚴格的定義:具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質的網路稱為複雜網路。
複雜網路簡而言之即呈現高度複雜性的網路。其複雜性主要表現在以下幾個方面:1)結構複雜,表現在節點數目巨大,網路結構呈現多種不同特徵。2)網路進化:表現在節點或連線的產生與消失。例如world-widenetwork,網頁或連結隨時可能出現或斷開,導致網路結構不斷發生變化。3)連線多樣性:節點之間的連線權重存在詫異,且有可能存在方向性。4)動力學複雜性:節點集可能屬於非線性動力學系統,例如節點狀態隨時間發生複雜變化。5)節點多樣性:複雜網路中的節點可以代表任何事物,例如,人際關係構成的複雜網路節點代表單獨個體,全球資訊網組成的複雜網路節點可以表示不同網頁。6)多重複雜性融合:即以上多重複雜性相互影響,導致更為難以預料的結果。例如,設計一個電力供應網路需要考慮此網路的進化過程,其進化過程決定網路的拓撲結構。當兩個節點之間頻繁進行能量傳輸時,他們之間的連線權重會隨之增加,通過不斷的學習與記憶逐步改善網路性能。
目前,複雜網路研究的內容主要包括:網路的幾何性質,網路的形成機制,網路演化的統計規律,網路上的模型性質,以及網路的結構穩定性,網路的演化動力學機制等問題。其中在自然科學領域,網路研究的基本測度包括:度(degree)及其分布特徵,度的相關性,集聚程度及其分布特徵,最短距離及其分布特徵,介數(betweenness)及其分布特徵,連通集團的規模分布。
複雜網路一般具有以下特性:
第一,小世界。它以簡單的措辭描述了大多數網路儘管規模很大但是任意兩個節(頂)點間卻有一條相當短的路徑的事實。以日常語言看,它反映的是相互關係的數目可以很小但卻能夠連線世界的事實,例如,在社會網路中,人與人相互認識的關係很少,但是卻可以找到很遠的無關係的其他人。正如麥克盧漢所說,地球變得越來越小,變成一個地球村,也就是說,變成一個小世界。
第二,集群即集聚程度(clustering coefficient)的概念。例如,社會網路中總是存在熟人圈或朋友圈,其中每個成員都認識其他成員。集聚程度的意義是網路集團化的程度;這是一種網路的內聚傾向。連通集團概念反映的是一個大網路中各集聚的小網路分布和相互聯繫的狀況。例如,它可以反映這個朋友圈與另一個朋友圈的相互關係。
第三,冪律(power law)的度分布概念。度指的是網路中頂(節)點(相當於一個個體)與頂點關係(用網路中的邊表達)的數量;度的相關性指頂點之間關係的聯繫緊密性;介數是一個重要的全局幾何量。頂點u的介數含義為網路中所有的最短路徑之中,經過u的數量。它反映了頂點u(即網路中有關聯的個體)的影響力。無標度網路(Scale-freenetwork)的特徵主要集中反映了集聚的集中性。