動態復雜網絡中節點影響力的研究進展*

任卓明

(杭州師范大學阿里巴巴商學院復雜科學研究中心, 杭州 311121)

節點影響力的識別和預測具有重要的理論意義和應用價值, 是復雜網絡的熱點研究領域.目前大多數研究方法都是針對靜態網絡或動態網絡某一時刻的快照進行的, 然而在實際應用場景中, 社會、生物、信息、技術等復雜網絡都是動態演化的.因此在動態復雜網絡中評估節點影響力以及預測節點未來影響力, 特別是在網絡結構變化之前的預測更具意義.本文系統地總結了動態復雜網絡中節點影響力算法面臨的三類挑戰, 即在增長網絡中, 節點影響力算法的計算復雜性和時間偏見; 網絡實時動態演化時, 節點影響力算法的適應性;網絡結構微擾或突變時, 節點影響力算法的魯棒性, 以及利用網絡結構演變闡釋經濟復雜性涌現的問題.最后總結了這一研究方向幾個待解決的問題并指出未來可能的發展方向.

綜述

1 引 言

復雜網絡中節點影響力的識別和預測作為復雜網絡的一個熱點研究領域[1?4], 有助于我們理解很多實際系統的內在結構特征并幫助我們解決一系列自然和社會系統中的重要問題, 具有重要理論意義以及現實應用價值[5?7].常見的如計算機病毒在網絡上的擴散、傳染病在人群中的蔓延、謠言在社會中的傳播等都可以看作是服從某種規律的網絡傳播行為.識別和預測節點的傳播影響力, 從而有效控制和引導復雜網絡的傳播行為[8].再如用來評估科學家的潛力, 科研成果的影響力、專利的創新性等, 也可以通過科研合作網絡、引文網絡、專利引用網路等的拓撲結構計算其影響力, 有助于建立更加客觀和具有前瞻性的科學評價體系[9].在社交網絡中也可以通過網絡拓撲結構計算網絡中節點的影響力, 用來識別在線用戶的社會影響力, 同樣電商網絡中也可以通過網絡拓撲結構計算網絡中節點的影響力, 用來評價消費者和商家的聲譽,商品的流行度和口碑等, 有助于建立客觀的電子商務交易評價體系[10].另外隨著互聯網和電子產品在全球范圍內獲得普及, 人們大部分的社會活動都要借助互聯網和電子產品, 同時互聯網也忠實地記錄下人們在社會經濟系統中的大量行為數據, 而海量數據的開放和使用進一步會對社會經濟研究產生深遠影響.目前已經有一些開創性的工作利用國際貿易、手機記錄、社交媒體、網絡檢索、網絡購物等數據構建復雜網絡, 利用網絡拓撲結構計算節點的影響力, 用來評估區域經濟影響力, 預測經濟發展潛力, 甚至提前預測一些關鍵經濟指標[11,12].

采用復雜網絡的方法預測節點影響力一般是基于網絡拓撲結構[13].基本思路是如果目標節點在網絡中的拓撲特征非常顯著, 我們就認為該節點在網絡中具有重要作用或影響力, 從而用來預測節點實際的影響力, 如傳播影響力、社會影響力、區域經濟影響力.例如最簡單的網絡拓撲結構方法—-度(Degree)[14]即計算節點在網絡中鄰居個數.在一個社交網絡中, 有大量的鄰居數目的用戶(即該節點的度拓撲特征非常顯著)可能有較大的社會影響力; 又如在引文網絡中, 利用文章的引用次數來評價科學論文的影響力; 再如在國際貿易網絡中, 通過出口國家數目度量國家的貿易影響力.經典的網絡拓撲結構方法除度外, 還有度量網絡中的節點對其他節點施加影響的能力的緊密度指標(Closeness)[15], 衡量個體社會地位的介數指標(Betweenness)[16], 將單個節點的影響力看成是所有其他節點影響力的線性組合的特征向量指標(Eigenvector)[17], 以及通過節點在網絡中的位置來挖掘節點影響力的K- 殼(K-shell)分解方法[18].不過研究者們并不滿足于僅使用這些經典的指標.例如直接改進度[19,20]、緊密度及介數[21,22]等經典指標, 設法降低特征向量的計算復雜度[23], 優化K-殼分解方法[24?26].Lü等[27]提出 H-index指標可以刻畫節點度到K-殼的變化, 并依據H-index選擇高影響力節點, 以及探索K-殼擴展的度量指標[28?30].這些都是為了使復雜網絡中節點影響力預測和識別更有效.另外還有一類基于隨機游走的節點影響力排序方法如PageRank[31,32],LeaderRank[33]和HITS算法[34].

然而上述的這類方法多是從某一角度對網絡的某一方面的結構特征進行刻畫, 如果目標網絡的結構在該方面表現顯著, 即可得到較好的效果[35].那么這些指標在不同拓撲結構的網絡的準確性又是怎樣呢? Da Silva 等[36]通過隨機網絡、小世界網絡和隨機集合網絡等網絡理論模型以及美國航空網絡的傳播仿真實驗, 采用皮爾遜系數, 討論了節點的拓撲性質如度、可達性、節點強度、介數、K-殼指標與該節點傳播影響力相關程度.另外由于網絡結構的異質性, 大量的節點的拓撲特征是不顯著的, 這些指標在不同拓撲結構特征不顯著的節點的影響力預測準確性又是怎樣呢? 任卓明等[37]對復雜網絡中最小K-殼節點的傳播影響力進行了分析,發現真實網絡中存在大量的K-殼值非常小的節點,而傳統的K-殼分解方法無法對這部分節點的傳播影響力進行度量.

近5年來已有多篇綜述文獻對現有的復雜網絡中節點影響力研究進行了系統的回顧, 總結了最新研究進展.如劉建國等[38]從網絡結構和傳播動力學的角度總結了節點影響力排序方法的最新研究進展, 并對各種方法的優缺點以及適用環境進行了分析.任曉龍和呂琳媛[39]系統地介紹了復雜網絡領域具有代表性的30余種重要節點挖掘方法,并詳細比較各種方法的計算思路、應用場景和優缺點.Pei和Makse[40]總結了識別和預測復雜網絡中傳播影響力的方法, 給出了在不同場景下有效識別和預測傳播影響力的策略.Lü等[3]在物理科學和復雜交叉科學的綜述期刊之一Physics Reports上撰文深度總結了復雜網絡中節點影響力近年來的研究現狀及并討論了發展動態.目前這幾篇綜述的被引用次數都已經超過百次, 表明節點影響力依然是復雜網絡的一個熱點研究領域.

在這幾篇綜述的總結和展望中都提到一個問題: 節點影響力的識別和預測局限于特定網絡拓撲結構, 一旦該方法在對應拓撲結構上不顯著, 那么該方法的識別和預測的準確性就令人存疑, 并且在實際應用場景中, 幾乎所有的復雜網絡, 比如社會、生物、信息、技術、交通運輸都在不停地演化中, 網絡的規模和結構也的確是在不斷變化的[41].當網絡規模小, 結構單一時, 我們可選擇的節點影響力方法也多, 但是隨著時間推移, 網絡規模變得足夠大, 網絡結構變得更加復雜, 那么之前介紹的節點影響力算法就面臨巨大的挑戰和局限.如圖1所示, 我們給出一個動態復雜網絡示例圖, 在t0時刻綠色節點的影響力可以用度衡量, 但在t0+l和 t0+l+k時刻, 綠色節點的節點影響力就不再適合用度的方法評估.

圖1 動態網絡示意圖Fig.1.An example of the dynamic network.

網絡在演化過程中, 網絡規模可能進一步增大, 結構隨時發生改變, 網絡結構中某種特性有可能是大體保持不變, 也有可能發生劇烈變化.于是在本文中, 我們根據網絡結構演化的特點, 分別詳細討論三類動態網絡的節點影響力的研究進展.第一類是增長網絡, 節點影響力算法復雜性和時間偏見的問題.因為涉及網絡全局結構特征的算法, 雖計算復雜但預測準確性高, 為減少算法復雜性和針對不同網絡規模, 我們介紹將網絡全局結構特征的算法改進成局部到全局的漸進式算法; 另外在增長網絡中, 我們討論新舊節點的網絡拓撲特征帶有時間偏見的問題, 特別是基于引文網絡和合作網絡等, 評價和預測科學家和科技論文影響力尤為明顯.第二類是網絡結構實時動態演化時, 節點影響力算法適應性問題.在社交網絡領域, 網絡結構是實時動態變化的, 介紹了如何通過分析和預測網絡結構特征的動態演化規律, 建立有針對性節點影響力的算法; 并討論了網絡結構演變過程中, 節點影響力的預測能力變化的問題.第三類是網絡隨時間演化, 結構微擾或突變時, 節點影響力算法魯棒性問題.總結了在網絡結構受到微擾或者突變時, 目前一系列關于經典的算法和設計高效的算法預測網絡中超級穩定的節點和超級敏感的節點的工作;并介紹了通過分析結構微擾或突變對網絡拓撲特征的影響定量刻畫國家經濟復雜性的研究工作.最后介紹了在動態網絡中關于節點的動力學演化與網絡結構特征的關系的研究工作.

2 三類動態復雜網絡中節點影響力算法

2.1 增長網絡

增長網絡最顯著的特征是網絡規模不斷地變大, 最常見的例子比如因特網、合作網絡、引文網絡.網絡增長導致算法的復雜性和成本提高, 因此有必要設計針對不同算法復雜性和不同網絡規模,利用節點局部到全局信息的漸進式的算法.像緊密度、介數還有基于矩陣特征向量等網絡結構全局信息的方法計算復雜性太高導致難以在大規模網絡中應用[42], 而像度等這樣局部特征的算法雖然算法復雜性低但預測的準確性低.那么如何在網絡規模增長到上千萬甚至過億節點的情況下快速而準確地預測節點影響力, Ercse-Ravasz等[43,44]提出了如圖2所示的局部介數方法, 該方法可以只計算節點的局部信息就可以預測節點的介數.Lü等[45]也通過節點的局部特征近似計算katz指標用于復雜網絡鏈路預測.

圖2 局部到全局的漸進式算法的示意圖 (a) 全局算法;(b) 漸進式算法Fig.2.The diagram of local to global progressive algorithm:(a) Global algorithm; (b) The local to global progressive algorithm.

另外在增長網絡中, 因為節點加入網絡的先后不同, 節點影響力方法具有時間偏見, 即對舊節點更有優勢.特別是基于引文網絡和合作網絡等評價和預測科學家和科技論文影響力尤為明顯, Mariani等[46,47]和Wasserman等[48]發現了 PageRank算法[31,32]在增長網絡模型中存在缺陷, 即原始的PageRank算法過于偏向于舊節點, 網絡中具有潛力的新節點往往會被PageRank算法壓制, 進而提出了一個重標(Rescaled)的含時PageRank算法.該算法將每個節點與其相鄰時間的節點相比較, 消除了時間偏向, 彌補了PageRank算法的不足.在該算法中, 不同時代的節點不會因為加入網絡的早晚受到影響, 而且該算法相比于傳統算法, 能夠及早甄別出極具潛力的重要節點.目前常見的度量影響力的算法有 Citations和PageRank, 還有諸如Long Gap[49,50], CiteRank[51], Rescaled Citations和Rescaled PageRank[47]等算法基于修正節點加入網絡的時間的影響.Ren等[52,53]利用美國電影引用數據和科學家引文數據, 分析了這6種節點影響力算法, 比較了這些算法的優劣.雖然這些指標將每個節點與其相鄰時間的節點相比較, 消除了對老的節點的時間偏向, 彌補了傳統算法的不足, 仍有兩個問題待解決: 1)如何修改這個方法以便在不同學科方向的論文都能夠廣泛適用? (不同學科的論文引用模式差別非常大, 例如在生物方面的論文引用要遠遠高出別的學科方向); 2)如何利用這個方法來衡量科研人員的表現, 也能更好地識別出具有潛力的科研工作者?

2.2 實時動態網絡

在實時動態網絡中, 節點影響力算法的適應性問題.現實世界的網絡的統計分析表明, 大量網絡的集聚性[54]、度-度相關性[55,56]、度分布[57]等基本網絡結構拓撲特征是隨時間演化的, 諸如社交網絡之類網絡結構幾乎是實時動態變化的, 圖3給出一個實時動態網絡示例圖.

圖3 實時動態網絡 (a) 含有一段時間的網絡; (b) 動態演化網絡Fig.3.An example of the time-variant dynamic network:(a) A network with a period of time; (b) the time-variant dynamic network.

在社交網絡中, 大量的研究表明網絡集聚性會影響網絡的傳播、同步、控制等功能[58].Klemm等[59]研究表明集群動力學中節點的影響力是由網絡拓撲結構和集群動力學機制共同決定的.Aral和Walker[60]研究網絡上的用戶傳播行為時,發現有影響力的節點更具有集聚性.Centola[61]發現傳播行為在高集聚類網絡中傳播更快.Bond等[62]以2010年美國大選為實例研究時發現Facebook用戶的影響力與網絡結構和傳播機制兩者都相關.宋玉萍和倪靜[63]通過構建可變集聚系數的無標度網絡模擬現實中的實時動態網絡的結構演化, 以及通過采用經典傳播模型進行傳播影響力的仿真實驗, 系統分析了在不同集聚系數的無標度網絡中預測節點影響力算法的準確性.結果發現度和介數的準確性在低集聚系數的網絡中表現更好, 特征向量則在高集聚網絡中更準確, 而緊密度的準確性受網絡集聚系數的變化影響較小.因此當網絡的集聚系數較低時, 可選擇度或者介數進行網絡節點影響力評價; 反之則需要選擇緊密度指標或特征向量指標.另一方面, 傳播過程的感染率越高,度指標和介數指標越可靠, 緊密度和特征向量則相反.另外Ma等[64]和邵鳳等[65]也進行其他網絡特征屬性的研究, 結果如圖4所示.4種經典節點影響力算法 (度、緊密度、介數、特征向量中心性) 在可變度-度相關性的無標度網絡中的準確性也是不同的.另外也可以通過將實時動態網絡變成高階網絡[66,67], 這時原來網絡的結構就發生改變.如Xu等[68]和Tao等[69]將全球航運網絡轉換為高階網絡, 分析Pagerank的排序變化情況.

2.3 結構微擾或突變的動態網絡

在生態網絡中, 網絡結構經過自然演化基本形成了穩定的結構, 但是經常可能遭遇一些自然因素, 比如極端天氣、自然災害或人為因素的干擾,這樣就會對原本穩定的網絡結構造成了擾動.還有就是交通網絡, 節點代表站點, 邊代表客流量, 我們知道在一般的工作日中, 由站點和客流量構成網絡結構基本是固定的, 但是在周末或者節假日等會導致某些站點變得異常重要, 特別是在遭遇局部的極端天氣時會導致某些站點重要性失效或者其周邊可替代的節點就變得異常重要.與交通網絡類似, 還有日常生活中的電網, 由于某些節點突發原因導致級聯失效.另外在國際貿易網絡中也有類似的現象, 例如遭遇局部戰爭、局部地區動蕩或者突發的金融經濟危機等, 造成網絡結構發生微小擾動或者重大改變.

對于這類問題, 抽象成復雜網絡問題就是網絡結構在演化過程中保持某種狀態, 但是隨時會遇到網絡中部分節點和邊的狀態發生變化即結構微擾或突變.那么在這種復雜動態網絡中, 如何預測節點影響力? 這就涉及到節點影響力方法的魯棒性問題.美國東北大學的Ghoshal和Barabasi[70]研究了對隨機網絡和無標度網絡結構微擾時, 通過PageRank算法的計算所得的節點影響力排序的穩定性.結果表明PageRank面對經過微擾過的隨機網絡進行節點影響力排序表現很敏感, 而對經過微擾過的無標度網絡的節點排序時表現很好的魯棒性, 特別地還存在排序超級穩定(super-stable)的節點.Lü等[71]也將結構微擾理論用于預測復雜網絡連邊.

圖4 4種經典節點影響力算法(度、緊密度、介數、特征向量中心性)在可變度-度相關性的無標度網絡中準確性, 其中β表示傳播參數, r表示可變度-度相關性的無標度網絡中的度- 度相關性參數, Kendall's tau值大小表示節點影響力方法的準確性Fig.4.The accuracy analysis of four centrality (degree, closeness, betweenness, eigenvector) methods on the scale-free network model with tunable assortative coefficient r and different infectious rate β.

圖5 鄰接矩陣的嵌套性示意圖 (a) 鄰接矩陣的嵌套值為 0; (b) 鄰接矩陣的嵌套值為 0.5; (c) 鄰接矩陣的嵌套值為 1Fig.5.The nestedness of the adjacency matrix: (a) The nestedness of the adjacency matrix is 0; (b)the nestedness of the adjacency matrix is 0.5; (c)the nestedness of the adjacency matrix is 1.

最近出現一個熱門領域, 即經濟復雜性-基于數據驅動預測經濟發展潛力[11,12].其基本想法是通過國家進出口貿易數據構建一個國家-產品的二部分網絡(網絡中邊代表國家或地區有能力生產和出口某種產品), 通過對這個二部分網絡的結構特征分析, 定量刻畫國家的經濟復雜性.研究結果發現未來經濟的發展狀況, 至少在短期內, 主要由國家產業結構復雜性所決定的.如果想要實現持續的經濟增長和繁榮, 就應該把力氣花在滿足自身經濟復雜性涌現的條件上, 而這就取決于二部分網絡的結構特征.目前該研究主題方興未艾, 國內外主要有意大利羅馬大學Pietronero小組[72?74]、美國麻省理工學院的Hidalgo小組[75?77]、瑞士弗里堡大學Zhang小組[78,79]、電子科技大學周濤小組[11,80,81]等在這方面做了一系列的研究工作.一般國家競爭力或影響力與其進出口的產品組合(即國際貿易網絡的嵌套結構(nested structure))緊密相連.嵌套結構的定義原本來自生態學中, 簡單講就是島嶼生物系統中, 在小島嶼中出現的物種多數也出現在物種相對豐富的大島嶼中, 這一非隨機分布格局被命名為嵌套結構[5].圖5 給出了三個網絡嵌套性分別為 0, 0.5, 1 的進出口網絡的示意圖.這里選取經典網絡的嵌套性算法NODF[82]如下.首先對鄰接矩陣的列和行按照度降序排列, 然后按照(1)式和(2)式計算網絡的嵌套性.

其中k為節點的度.最終求得的鄰接矩陣的嵌套值為 [ 0 ,1] .其中0表示鄰接矩陣沒有嵌套性質, 如圖5(a),1表示網絡擁有完美的嵌套特性, 如圖5(c).

嵌套結構也常用來刻畫非生態系統, 例如全球或地方的經濟貿易格局的演變[83].圖6給出了牛肉、摩托車、醫療器械三類不同商品的國際貿易網絡的可視化鄰接矩陣, 對應三個顯著不同的嵌套特性, 圖中的曲線為國際貿易中786類商品的嵌套性分布圖.隨著科技進步和貿易日趨緊密, 這種貿易網絡中對應的嵌套特性演化規律和機制, 以及與國家經濟復雜性和影響力的映射關系.Bustos等[84]研究發現在網絡在演化過程中, 嵌套拓撲結構特性保持穩定, 但是網絡中會有部分連邊消失或新出現一些連邊.這一發現可以用來描述和預測國家某些新產業的出現或消失的模式, 從而找到經濟發展的新動力, 為國家或地區經濟的發展做出前瞻指導.

圖6 786 類商品國際貿易網絡的嵌套性分布圖, 其中子圖為牛肉、摩托車、醫療器械三類不同商品的國際貿易網絡的可視化鄰接矩陣Fig.6.Distribution of the nestedness in the international trade networks with 786 kinds of goods.(subgraphs) The matrices are representations of the different layer of world trade networks which respectively corresponds to the network of Bovine, Motorcycles, and Medical Instruments.

3 節點的動力學與網絡結構特征的關系預測節點影響力

就傳播影響力來說, 病毒在計算機網絡上的蔓延、傳染病、謠言、信息在現實社會網絡或虛擬的社交網絡中的傳播, 我們必須有效控制和引導復雜網絡的傳播行為趨利避害, 最好的方式就是在傳播擴散之前預先推測或測定節點的傳播影響力.這時可以通過對計算機網絡、現實社會網絡以及虛擬的社交網絡的拓撲結構特征分析, 對節點在特定結構特征中顯著程度進行定量分析.如果節點拓撲特征性質與真實的傳播影響力存在擬合或相關性之類的映射關系[85], 那么就可以采用網絡結構特征來事前推測或測定節點的傳播影響力.針對真實的節點影響力, 可以采用傳播動力學模仿真實的傳播信息擴散過程計算傳播影響力, 社會動力學過程模擬計算社會影響力, 或者通過真實的社會評價獲取社會影響力, 區域經濟影響力可以通過貿易流動的模擬計算.針對不同的動力學, Barzel和Barabasi[86,87]給出一個統一的動力學特征并分析不同動力學的與網絡結構的關系.一般動力學過程可以簡化成如下描述,

其中左式為節點動力學特征隨時間演化過程, 右式中 Aij為網絡的鄰接矩陣, W為與節點自身相關的時間函數, Q為節點對之間相互作用的時間函數.節點的影響力可以通過動力學仿真或數值解析獲得, 公式中網絡的鄰接矩陣 Aij代表是網絡, 我們知道現實中網絡的拓撲關系容易獲得, 可以直接計算網絡每個節點的拓撲結構屬性.如果這一結構特征恰好刻畫實際影響力, 那么這一方法則能準確預測節點影響力.

另外也可以從從微觀角度出發, 描述節點生命周期內其拓撲和動力學特征的普遍演化規律, 并給出其表達方式, 建立模型刻畫節點拓撲和動力學結構特征的演化機制.節點的拓撲和動力學特征演化特征如(4)式[88,89]所示.

右式中 ? fi(t,?t)a表示實際的網絡節點拓撲特征在 (t,?t) 時間的變化, ? fi(t,?t)e表示經過網絡模型計算的理論值.如果 Ri(t,?t)=1 就表明真實的動態網絡與網絡模型規律一致.如果Ri(t,?t)<1就表明真實的動態網絡節點的屬性演化慢于網絡模型.如果 Ri(t,?t)>1 就表明真實的動態網絡節點的屬性演化快于網絡模型.我們以最簡單的度和無標度網絡中優先連接(preferential attachment)為例.在實際動態演化網絡中, 節點在 ?t 獲得度為?ki(t,?t), 那么經過PA模型獲得的節點在 ?t 獲得度為

那么度的演化動力學可以表述為

Ren等[90]分析了用戶-電影的二部分動態網絡中, 電影的流行度的演化分析, 電影的流行度可以簡單定義為觀眾點擊或觀看的次數, 可以理解為電影的受歡迎程度, 即電影的影響力.采用(6)式計算, 發現在電影剛上市時, Ri(t,?t)? 1 表明真實的動態網絡節點的屬性演化遠遠快于網絡模型,而后漸漸減緩到 Ri(t,?t)=1 , 表明真實的動態網絡與網絡模型規律一致.

4 結 論

本文系統總結了三類動態復雜網絡中節點影響力的一些研究進展.在增長網絡中, 節點影響力的算法復雜性和時間偏見的問題; 網絡結構實時動態演化時, 節點影響力的算法適應性問題; 結構微擾或突變的動態網絡中, 節點影響力算法魯棒性問題以及利用網絡結構演變闡釋經濟復雜性涌現的問題.可以看出目前這個方向仍然有諸多挑戰有待解決.正如本文第三節中提及的節點的動力學演化與網絡結構特征的關系.如何挖掘經典的動力學機制和網絡結構特征之間的關系, 分析基于動力學模擬真實的節點影響力和基于網絡結構特征挖掘的節點影響力之間的統計特性和關聯關系, 并通過數學解析和數值獲得節點影響力的精確解或近似解?還有就是基于網絡異質性的考慮, 分析在異質網絡中, 處于“胖尾”分布的大量節點的動力學和拓撲特征的演化模式和規律, 以及在演化過程中的節點影響力的穩定性以及可預測性.另外隨著最近幾年大數據變得越來越容易獲得, 如何通過相互關聯的動態網絡增強節點影響力的可預測性和設計綜合節點影響力預測算法, 這些難題的解決具有廣泛應用場景.例如通過引文網絡和合作網等數據構建的多層關聯網絡, 建立綜合影響力預測模型, 預測科學家影響力.再如利用手機社交數據、航空網絡、貿易網絡等多個地理標簽動態網絡, 通過地理映射構建多層相互關聯演化網絡, 設計新的地區經濟影響力預測指標, 預測地區經濟發展潛力.最后構建相互關聯的動態網絡模型, 系統研究對節點影響力的可預測性的影響, 從而設計綜合影響力指標.