復雜網絡理論研究綜述①

安沈昊,于榮歡

(航天工程大學 復雜電子系統仿真實驗室,北京 101400)

復雜網絡理論研究最早可追溯到18世紀由數學家歐拉提出的“七橋問題”,將陸地抽象為點,將連接陸地的橋梁抽象為邊,點與連接點的邊就組成了網絡.隨著復雜系統的快速發展,復雜網絡的分析方法被廣泛應用于社會、經濟、軍事等領域,如在線社交網絡、國際貿易、現代化信息作戰系統等.

目前,復雜網絡各分支方向的研究已引起廣泛關注,國內多名學者先后對復雜網絡的相關理論、研究和應用方向進行系統的整理和總結[1-6].朱涵等最早介紹了復雜網絡理論[7],何宇等從部件、權重、機制、動態變化及側重條件5 個方面整理其演化模型并分類[8],周濤等詳述大數據時代下復雜網絡亟需解決的十大問題[9].隨著復雜網絡理論研究的發展,有必要繼續對其理論進行歸納和整理,以推動進一步研究.

1 復雜網絡基本概念

關于什么是復雜網絡,目前還沒有一個統一的定義.錢學森先生認為具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質的網絡可稱為復雜網絡.在研究網絡時,人們往往只關注節點之間是否存在連邊,忽視節點位置、邊的性質等因素.復雜網絡就可看作復雜系統的高度抽象,將網絡中的節點抽象為復雜系統中的個體,網絡中的邊抽象為復雜系統中個體之間的關系,這樣由大量的節點及節點間相互連接的邊所構成的網絡就可稱為復雜網絡.

1.1 度分布

節點的度定義為與該節點相連的邊的個數,反映該節點在網絡中的重要程度.網絡中所有節點的度的平均值是該網絡的平均度.網絡中節點的度分布表示為分布函數P(k),代表該節點的度等于k的概率,也可代表網絡中度為k的節點數在總節點數中所占的比例.

1.2 平均路徑長度

連接兩個節點的最短路徑所用邊的個數為兩節點之間的距離,網絡中所有節點對之間距離的平均值為網絡的平均路徑長度.平均路徑長度反映了節點之間聯系的緊密程度和網絡的大小.

1.3 集聚系數

節點的集聚系數表示為鄰居節點之間實際存在的邊數與最大可能邊數之比,反映一個節點的相鄰節點之間相互連接的情況.網絡的集聚系數表示為所有節點集聚系數的平均值,反映了網絡的社團結構特性.

1.4 介數

介數分為點介數和邊介數.點介數表示為經過該節點的最短路徑數目占所有最短路徑數目的比例,邊介數表示為所有經過該邊的最短路徑數目占所有最短路徑數目的比例.介數反映了相應節點或邊在整個網絡中的作用和地位.

2 典型復雜網絡模型

網絡的結構與功能聯系緊密,拓撲結構決定功能,功能影響拓撲結構演化.為研究復雜網絡拓撲結構特性,Erdos 與Renyi 最早根據隨機圖理論構建了隨機網絡模型(ER 模型)[10],但ER 模型的連接規則與節點分布的隨機性使其不適合研究真實復雜網絡.因此,基于已有網絡模型的缺陷與真實網絡研究的需求,學者們提出了大量不同的復雜網絡模型.

2.1 小世界網絡模型

通常認為如果網絡的平均路徑長度L與節點數N的對數成正比,則稱該網絡具有小世界效應.絕大部分真實復雜網絡都具有小世界效應,即具有較小的平均路徑長度和較大的集聚系數.

基于此,Watts 和Strogatz 提出了小世界網絡模型(WS 模型)[11].在一個包含N個節點的環狀規則網絡中,以順時針方向訪問每個節點并選取與當前節點連接的邊,以概率p對每條邊進行刪除和重連,將邊的另一端隨機連接到其他節點上,在這個過程中可能會出現長程邊從而減小網絡的平均路徑長度,以概率1-p保留原有邊,整個過程中不允許出現重復連接和自環.可以改變p值來調節網絡的隨機性,并保持網絡中邊數的平衡,p=0 時對應規則網絡,p=1 時對應隨機網絡.通過這種方法構造出來的小世界網絡具有較小的平均路徑長度和較大的集聚系數.

考慮到WS 模型的構造方法可能會破壞網絡的連通性,Newman 和Watts 對其進行了改進,提出了NW模型[12].NW 模型的改進之處在于用隨機化加邊取代了隨機化重連,即以概率p在隨機選取的節點對之間添加連接邊,不改動原有連接邊,且不允許出現重復連接和自環.當網絡規模N足夠大而p足夠小時,WS 模型與NW 模型在本質上是一樣的.

2.2 無標度網絡模型

在隨機網絡和小世界網絡中,節點的度分布近似為泊松分布.但研究者發現大多數真實復雜網絡的度分布服從冪律分布,即隨著節點度k增大,分布函數P(k)衰減速度變小.

針對這種情況,Barabas 和Albert 提出了無標度網絡模型(BA 模型)[13]從兩方面來描述其產生機制,即網絡增長和優先連接.網絡增長意味著網絡中不斷有新節點加入并連接到已存在的節點上,初始網絡包含m0個節點和m1條邊,每個時間步增加一個新節點和m(m≤m0)條邊,連接到m個已有的節點上;優先連接意味著新增加的節點會優先連接度值較大的節點,將節點i的度ki和所有節點度的總和k的比值作為新增加的節點連接到節點i的概率,新增加的節點根據此概率選擇所要連接的m個節點.經過t個時間步后初始網絡就會演化成具有m0+t個節點和m1+mt條邊的網絡,其中大多數節點度值較小,少數節點度值很大.結果顯示,BA 網絡不僅兼具小世界效應和較大的集群系數,其度分布也滿足冪律分布.

2.3 局域世界網絡模型

BA 模型中的優先連接機制存在于全局網絡,然而Li 等通過對真實復雜網絡的研究,發現優先連接機制僅存在于局部網絡,因此在BA 模型的基礎上提出一種簡單局域世界網絡模型(LC 模型)[14].該模型首先隨機選取m個節點作為新增節點的局域世界,新增節點會優先連接所對應的局域世界中度值較大的節點,而不是選擇全局網絡中度值較大的節點進行連接.

在BA 模型中,新增節點擁有全局信息;在LC 模型中,新增節點僅擁有局部信息.在真實復雜網絡中,總是存在少數節點擁有全局信息,大部分節點僅擁有局部信息.基于此,Qin 等對LC 模型進行了改進,建立了一種新的局域世界網絡模型[15].該模型引入了全局節點數與總結點數的比值作為新增節點屬于全局節點的概率p.當p=0 時,該模型對應于LC 模型;當p=1時,對應于BA 模型.

2.4 權重網絡模型

上述網絡模型均將網絡視為無權網絡,忽略了節點之間的相互作用程度或節點和邊的物理量等信息.而真實網絡往往為節點或邊具有權重的有權網絡,相比于無權網絡,有權網絡更能反映真實情況.

Yook 提出了一種基于BA 模型的簡單加權網絡模型[16],通過賦予邊權重來描述節點之間的相互作用強度與連接邊之間的異質性.

Barrat 等提出了具有較強代表性的BBV 模型[17].該模型綜合考慮了拓撲結構和權重在網絡動態演化過程中的影響,隨著網絡規模的增大,其度分布、邊權分布和節點權分布都具有無標度特性.

周健等把局域世界特征引入到BBV 模型中,提出了一種基于局域世界演化的BBV 模型[18].該模型的構建考慮了局域世界內新節點和新連接的產生、局域世界內舊連接的消亡、局域世界外新連接的產生、權值優先連接這4 個方面.

周鵬堯等在BBV 模型的基礎上,提出一種廣義的加權網絡演化(FBBV)模型[19].該模型與BBV 模型的不同之處在于,當網絡中加入新節點時,網絡中所有邊權都會發生變化,變化程度取決于各邊所處的實際位置.

3 復雜網絡研究現狀

3.1 社團結構研究

在現實生活中人們可能因各種因素處于不同的團體中,成員之間聯系頻繁,而團體之間僅偶爾有往來.在復雜網絡中同樣有著類似的社團現象,社團結構是復雜網絡的一個重要特征.

關于社團結構的定義,根據連接密度可理解為社團是對網絡內節點的分組,組內節點之間聯系緊密,組間節點聯系稀疏;根據連通性可將社團看作一個派系,即由兩個以上的節點組成的全連通子圖,其中任意兩個節點之間都存在連接邊.

復雜網絡中的社團根據不同的標準可分為不同的類型.根據社團內部節點聯系的緊密程度,可分為強社團和弱社團;根據社團之間是否有重疊節點,可分為重疊社團與非重疊社團.

如何對隱藏在復雜網絡中的社團結構進行檢測與劃分,是復雜網絡研究中的一個重要內容.關于社團結構的檢測算法,汪小帆等首先介紹了計算機科學中的譜平分法和Kernighan-Lin 算法、社會學中具有代表性的分裂算法和凝聚算法[20].

復雜網絡中多數節點的“多屬性”特征使重疊社團的檢測算法具有更高的實用性.為準確檢測出權重網絡中的重疊社團,賈鄭磊等提出了一種基于Jaccard系數的BGLL 模塊密度優化算法,相比于傳統BGLL算法,該算法能充分利用局部、全局信息,將有權節點與社團相似度相結合,具有更高準確率[21].李歡等從不同角度將重疊社團檢測算法分為基于派系過濾的算法、基于局部拓展的算法、基于邊劃分的算法、基于動力學的算法和基于模糊檢測的算法[22].

針對無權無向網絡中非重疊社團的檢測,張鵬改進了密度峰值聚類算法,通過自定義加權集合密度算法尋找聚類中心,然后計算節點之間的相似性,最終完成社團劃分[23].

3.2 抗毀性研究

網絡的抗毀性可理解為當網絡受到攻擊或出現故障時所表現出的恢復性或適應性,或在部分節點或邊失效的情況下仍能繼續提供服務的能力.如果一個網絡在受到攻擊而被移除少量節點后,剩余節點之間仍然是連通的,那么該網絡對這種攻擊具有較強抗毀性.

Albert 等最早開始研究復雜網絡在節點失效情況下的抗毀性[24].他們用隨機攻擊與選擇性攻擊兩種不同策略分別對隨機網絡和無標度網絡進行攻擊.隨機攻擊指的是隨機移除網絡中的節點,選擇性攻擊即按照節點度從大到小的順序移除節點.結果表明:無標度網絡在隨機攻擊下表現出較強的抗毀性,在選擇性攻擊下卻非常脆弱,若移除有大量連接的關鍵節點,網絡將立刻崩潰.

與最初基于圖論的研究方法不同,目前復雜網絡抗毀性的研究方法已發展為基于統計物理的方法,其方向包括抗毀性指標測度和抗毀性策略優化.

在抗毀性指標測度方面,孫成雨等對二進制粒子群算法的概率映射函數和位置更新式進行改進,并結合適應度函數求解算法,設計出點韌性度算法,該算法能夠快速獲取網絡點韌性度以衡量其抗毀性性能,還可用于求解邊韌性度[25].

有關研究顯示,根據網絡實際情況選擇合適的、包含多種信息的抗毀性指標,對抗毀性策略的優化有重要的意義[26,27].此外,張煜等從拓撲結構、網絡容量和路由策略等3 個方面介紹了抗毀性優化策略的研究進展[28],并指出除了拓撲結構,網絡的防御與故障修復策略都將成為重要研究方向.

3.3 節點影響力研究

小世界效應與無標度特性使得復雜網絡中的節點分布呈現不均勻的現象,少數節點具有大量連接,處于重要地位,例如在國際貿易中對整個貿易體系有重要影響的一些國家,相比于大多數普通節點,這些少數節點對于整體網絡有著更大的影響.因此準確識別復雜網絡中的重要節點,對于優化復雜網絡的結構與功能具有重要意義.

節點影響力研究包括節點重要性排序和影響力最大化,李夢甜對二者進行了深入研究,提出了一種中心性方法對節點傳播力進行評估與排序,該方法將本節點聚類系數與相鄰節點度值結合,具有良好的分辨率與排序準確性,運用該方法找出的節點集合能夠影響更多的節點[29].

考慮到節點影響力指標受節點屬性、網絡結構等因素影響,張應青等將節點影響力測度方法分為基于節點多屬性的多指標測度方法、基于節點局部信息和基于網絡全局信息的單屬性指標測度,并介紹了貪心算法、啟發式算法和滲流方法3 種尋找影響力節點集合的方法[30].

上述重要節點的識別方法僅局限于尋找在靜態網絡中具有深刻拓撲特征的節點,而真實復雜網絡的規模與結構時刻都在變化.基于此,任卓明討論了節點影響力算法在增長網絡、實時動態網絡與結構突變或微擾的動態網絡中遇到的問題,對于動態網絡的節點影響力研究有重要的意義[31].

3.4 信息傳播研究

如今網絡已成為信息的主要傳播渠道,這使得人們的社交網絡從線下接觸式拓展至線上非接觸式.對信息在社交網絡上傳播的動力學機理進行研究,是有效實施風險管控的基礎.建立合適的信息傳播模型能準確反映網絡個體之間信息傳播情況隨時間產生的變化.

典型的信息傳播模型主要參照流行病傳播模型,包括SI 模型、SIS 模型、SIR 模型、SEIR 模型、SIRS模型等.李丹丹等從經典謠言傳播模型到社會網絡上的謠言傳播模型、從微觀機制和宏觀機制,分別評述了謠言傳播模型的發展歷程[32].錢亞飛分析了元胞自動機模型、多數決定模型、Ising 模型、有界信任模型、Sznajd 模型這5 種輿情演化模型,將其分為離散與連續兩類觀點模型,指出網絡輿情研究應當注重真實數據集的獲取與多學科的有機結合[33].

謠言在實際社交網絡中的傳播率是非一致性的,每個用戶對謠言的抵抗力不同,用戶之間的親密程度也會影響謠言的傳播.翟倩倩等建立了一種S2IR 網絡謠言傳播模型,該模型充分考慮謠言傳播的差異性與謠言免疫策略,更加符合實際網絡中的謠言傳播,不足之處是未能進一步對謠言未知節點進行細分[34].

3.5 同步控制研究

無論是在日常生活中還是在專業領域內,同步都是一種常見的現象,例如魚群中每條魚的同時擺動、超導體中電子的一致前進等.由于同步既會產生有益結果也會產生有害結果,因此有必要對復雜網絡中的同步進行控制.復雜網絡中的同步控制就是指通過對網絡施加外力對其進行控制,使內部多個節點動力系統達到相同狀態并保持穩定.如何實現復雜網絡的同步控制,從而維持有益同步規避有害同步,已成為當前研究的熱點問題.

信息在網絡中的傳播速度會受到各種因素的影響與限制,這就導致在控制器接受與發送節點狀態信息的過程中出現滯后現象[35].針對復雜動態網絡節點本身可能存在的滯后現象,王亞楠分別從馬爾可夫切換轉移率部分已知和完全已知兩種情況出發研究復雜動態網絡系統的同步控制問題[36].

由于網絡中節點數量眾多,對所有節點進行控制顯然是不切實際的,因此牽制控制策略的研究受到廣泛關注,即僅對一部分節點進行控制進而使全局網絡保持同步.王瑞峰等引入事件激發函數實現牽制節點集的實時更新,依據合適的節點集選取規則,有效提高了同步效率與資源使用率[37].曹進德等從控制條件、節點選取策略、影響因素、算法、應用等方面概述了復雜網絡牽制同步的研究進展[38],在目前大多數牽制控制策略依賴全局信息的背景下,如何利用局部信息實現分布式的牽制控制值得深入研究.

3.6 隨機行走研究

隨機行走是復雜網絡領域研究的諸多動力學行為之一,并且與信息傳播、同步等其它動力學行為存在緊密聯系.復雜網絡上的隨機行走是指隨機行走粒子以復雜網絡結構為載體,從初始節點出發,在每個時間步以一定概率選擇當前節點的鄰居節點進行傳輸最終到達目的節點的過程.

景興利等運用圖譜理論,給出一般網絡上隨機行走平均到達時間的精確解,對加權網絡的平均首到達時間和平均陷阱時間進行分析,發現二者與網絡規模、陷阱點度值、權重系數、平均度有密切關系[39].

4 結論與展望

本文從復雜網絡的基本概念、網絡模型、研究現狀3 個層面簡要介紹了近幾年復雜網絡領域的研究成果和進展.從中可以看到:大多數復雜網絡模型是在BA 模型的基礎上,通過新的機制演化而來,BA 模型將繼續為復雜網絡模型研究提供重要的參考價值;當前復雜網絡的研究更側重于結構特性和網絡動力學兩個領域,并且兩個領域間的研究相互影響,如何描述并分析網絡結構特性與動力學行為之間的關系,將是眾多學者面臨的難題.

隨著科技發展與眾多復雜巨系統的出現,復雜網絡的結構和動力學行為趨向復雜化.人們僅依靠數字、表格等傳統形式已無法有效對復雜網絡進行全局性的規劃與管理,需要運用可視化技術全面、直觀、清晰、實時地描述復雜網絡拓撲結構與動力學行為,以便對其進行分析、管理與評估.對復雜網絡進行可視化處理,既可以幫助人們從視覺層面上理解復雜網絡的結構,也便于學者研究復雜網絡拓撲結構變化對其動力學行為的影響.因此,復雜網絡可視化將是未來復雜網絡研究的熱點之一,具體有以下幾個方向:

(1)可視化算法

可視化算法按照適用規模,可分為布點算法和可視化壓縮算法[40];按照布局方式,可分為基于節點-鏈接的可視化方法、基于鄰接矩陣的可視化方法和基于圖嵌入的可視化方法[41].隨著大數據的興起與節點關系的復雜化,可視化算法在性能與可觀性等方面遇到了巨大的挑戰.對此,一是可以對現有算法進行改進,提高計算效率,以減少計算資源的占用;二是可以引入“可視化分層”的概念,將運算壓力與可視化結果隨著用戶的交互操作分配到不同的層面上.

(2)網絡拓撲可視化

網絡拓撲可視化是一種將點和線構成圖形、圖像來對網絡中的拓撲信息進行描述與分析的技術[42].在大數據處理與云計算等技術的推動下,能夠合理運用有限資源,高效地管理大量關系復雜的節點,并簡潔、直觀地展示其運行狀態等信息,具有重要的意義.因此,如何實現拓撲特性、布局算法和可視化方式三者的結合,是當前面臨的難點.

(3)動態網絡可視化

復雜網絡所具有“無標度”特性使其處在一個數據不斷更新的狀態,且新數據會對原始可視化效果帶來不可控、不可估計的影響,為其可視化帶來了巨大的挑戰[43].目前的可視化算法與工具大多用于靜態網絡的可視化,無法準確描述持續演變的真實動態網絡,怎樣有效實現動態網絡可視化也是一個值得關注的問題.

時至今日,復雜網絡的應用已遠遠超出物理學和數學的范疇,其分析與應用也為諸多學科提出了新的具有挑戰性的難題.把復雜網絡理論與實際問題聯系起來,增強其實用性,進而應用到實際復雜系統中,將是復雜網絡理論研究未來的發展趨勢.