動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的研究進(jìn)展*

任卓明

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

節(jié)點(diǎn)影響力的識(shí)別和預(yù)測(cè)具有重要的理論意義和應(yīng)用價(jià)值, 是復(fù)雜網(wǎng)絡(luò)的熱點(diǎn)研究領(lǐng)域.目前大多數(shù)研究方法都是針對(duì)靜態(tài)網(wǎng)絡(luò)或動(dòng)態(tài)網(wǎng)絡(luò)某一時(shí)刻的快照進(jìn)行的, 然而在實(shí)際應(yīng)用場(chǎng)景中, 社會(huì)、生物、信息、技術(shù)等復(fù)雜網(wǎng)絡(luò)都是動(dòng)態(tài)演化的.因此在動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)中評(píng)估節(jié)點(diǎn)影響力以及預(yù)測(cè)節(jié)點(diǎn)未來影響力, 特別是在網(wǎng)絡(luò)結(jié)構(gòu)變化之前的預(yù)測(cè)更具意義.本文系統(tǒng)地總結(jié)了動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)影響力算法面臨的三類挑戰(zhàn), 即在增長網(wǎng)絡(luò)中, 節(jié)點(diǎn)影響力算法的計(jì)算復(fù)雜性和時(shí)間偏見; 網(wǎng)絡(luò)實(shí)時(shí)動(dòng)態(tài)演化時(shí), 節(jié)點(diǎn)影響力算法的適應(yīng)性;網(wǎng)絡(luò)結(jié)構(gòu)微擾或突變時(shí), 節(jié)點(diǎn)影響力算法的魯棒性, 以及利用網(wǎng)絡(luò)結(jié)構(gòu)演變闡釋經(jīng)濟(jì)復(fù)雜性涌現(xiàn)的問題.最后總結(jié)了這一研究方向幾個(gè)待解決的問題并指出未來可能的發(fā)展方向.

綜述

1 引 言

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

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

然而上述的這類方法多是從某一角度對(duì)網(wǎng)絡(luò)的某一方面的結(jié)構(gòu)特征進(jìn)行刻畫, 如果目標(biāo)網(wǎng)絡(luò)的結(jié)構(gòu)在該方面表現(xiàn)顯著, 即可得到較好的效果[35].那么這些指標(biāo)在不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)的準(zhǔn)確性又是怎樣呢? Da Silva 等[36]通過隨機(jī)網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和隨機(jī)集合網(wǎng)絡(luò)等網(wǎng)絡(luò)理論模型以及美國航空網(wǎng)絡(luò)的傳播仿真實(shí)驗(yàn), 采用皮爾遜系數(shù), 討論了節(jié)點(diǎn)的拓?fù)湫再|(zhì)如度、可達(dá)性、節(jié)點(diǎn)強(qiáng)度、介數(shù)、K-殼指標(biāo)與該節(jié)點(diǎn)傳播影響力相關(guān)程度.另外由于網(wǎng)絡(luò)結(jié)構(gòu)的異質(zhì)性, 大量的節(jié)點(diǎn)的拓?fù)涮卣魇遣伙@著的, 這些指標(biāo)在不同拓?fù)浣Y(jié)構(gòu)特征不顯著的節(jié)點(diǎn)的影響力預(yù)測(cè)準(zhǔn)確性又是怎樣呢? 任卓明等[37]對(duì)復(fù)雜網(wǎng)絡(luò)中最小K-殼節(jié)點(diǎn)的傳播影響力進(jìn)行了分析,發(fā)現(xiàn)真實(shí)網(wǎng)絡(luò)中存在大量的K-殼值非常小的節(jié)點(diǎn),而傳統(tǒng)的K-殼分解方法無法對(duì)這部分節(jié)點(diǎn)的傳播影響力進(jìn)行度量.

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

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

圖1 動(dòng)態(tài)網(wǎng)絡(luò)示意圖Fig.1.An example of the dynamic network.

網(wǎng)絡(luò)在演化過程中, 網(wǎng)絡(luò)規(guī)?？赡苓M(jìn)一步增大, 結(jié)構(gòu)隨時(shí)發(fā)生改變, 網(wǎng)絡(luò)結(jié)構(gòu)中某種特性有可能是大體保持不變, 也有可能發(fā)生劇烈變化.于是在本文中, 我們根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)演化的特點(diǎn), 分別詳細(xì)討論三類動(dòng)態(tài)網(wǎng)絡(luò)的節(jié)點(diǎn)影響力的研究進(jìn)展.第一類是增長網(wǎng)絡(luò), 節(jié)點(diǎn)影響力算法復(fù)雜性和時(shí)間偏見的問題.因?yàn)樯婕熬W(wǎng)絡(luò)全局結(jié)構(gòu)特征的算法, 雖計(jì)算復(fù)雜但預(yù)測(cè)準(zhǔn)確性高, 為減少算法復(fù)雜性和針對(duì)不同網(wǎng)絡(luò)規(guī)模, 我們介紹將網(wǎng)絡(luò)全局結(jié)構(gòu)特征的算法改進(jìn)成局部到全局的漸進(jìn)式算法; 另外在增長網(wǎng)絡(luò)中, 我們討論新舊節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)涮卣鲙в袝r(shí)間偏見的問題, 特別是基于引文網(wǎng)絡(luò)和合作網(wǎng)絡(luò)等, 評(píng)價(jià)和預(yù)測(cè)科學(xué)家和科技論文影響力尤為明顯.第二類是網(wǎng)絡(luò)結(jié)構(gòu)實(shí)時(shí)動(dòng)態(tài)演化時(shí), 節(jié)點(diǎn)影響力算法適應(yīng)性問題.在社交網(wǎng)絡(luò)領(lǐng)域, 網(wǎng)絡(luò)結(jié)構(gòu)是實(shí)時(shí)動(dòng)態(tài)變化的, 介紹了如何通過分析和預(yù)測(cè)網(wǎng)絡(luò)結(jié)構(gòu)特征的動(dòng)態(tài)演化規(guī)律, 建立有針對(duì)性節(jié)點(diǎn)影響力的算法; 并討論了網(wǎng)絡(luò)結(jié)構(gòu)演變過程中, 節(jié)點(diǎn)影響力的預(yù)測(cè)能力變化的問題.第三類是網(wǎng)絡(luò)隨時(shí)間演化, 結(jié)構(gòu)微擾或突變時(shí), 節(jié)點(diǎn)影響力算法魯棒性問題.總結(jié)了在網(wǎng)絡(luò)結(jié)構(gòu)受到微擾或者突變時(shí), 目前一系列關(guān)于經(jīng)典的算法和設(shè)計(jì)高效的算法預(yù)測(cè)網(wǎng)絡(luò)中超級(jí)穩(wěn)定的節(jié)點(diǎn)和超級(jí)敏感的節(jié)點(diǎn)的工作;并介紹了通過分析結(jié)構(gòu)微擾或突變對(duì)網(wǎng)絡(luò)拓?fù)涮卣鞯挠绊懚靠坍媷医?jīng)濟(jì)復(fù)雜性的研究工作.最后介紹了在動(dòng)態(tài)網(wǎng)絡(luò)中關(guān)于節(jié)點(diǎn)的動(dòng)力學(xué)演化與網(wǎng)絡(luò)結(jié)構(gòu)特征的關(guān)系的研究工作.

2 三類動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)影響力算法

2.1 增長網(wǎng)絡(luò)

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

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

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

2.2 實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)

在實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)中, 節(jié)點(diǎn)影響力算法的適應(yīng)性問題.現(xiàn)實(shí)世界的網(wǎng)絡(luò)的統(tǒng)計(jì)分析表明, 大量網(wǎng)絡(luò)的集聚性[54]、度-度相關(guān)性[55,56]、度分布[57]等基本網(wǎng)絡(luò)結(jié)構(gòu)拓?fù)涮卣魇请S時(shí)間演化的, 諸如社交網(wǎng)絡(luò)之類網(wǎng)絡(luò)結(jié)構(gòu)幾乎是實(shí)時(shí)動(dòng)態(tài)變化的, 圖3給出一個(gè)實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò)示例圖.

圖3 實(shí)時(shí)動(dòng)態(tài)網(wǎng)絡(luò) (a) 含有一段時(shí)間的網(wǎng)絡(luò); (b) 動(dòng)態(tài)演化網(wǎng)絡(luò)Fig.3.An example of the time-variant dynamic network:(a) A network with a period of time; (b) the time-variant dynamic network.

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

2.3 結(jié)構(gòu)微擾或突變的動(dòng)態(tài)網(wǎng)絡(luò)

在生態(tài)網(wǎng)絡(luò)中, 網(wǎng)絡(luò)結(jié)構(gòu)經(jīng)過自然演化基本形成了穩(wěn)定的結(jié)構(gòu), 但是經(jīng)?？赡茉庥鲆恍┳匀灰蛩? 比如極端天氣、自然災(zāi)害或人為因素的干擾,這樣就會(huì)對(duì)原本穩(wěn)定的網(wǎng)絡(luò)結(jié)構(gòu)造成了擾動(dòng).還有就是交通網(wǎng)絡(luò), 節(jié)點(diǎn)代表站點(diǎn), 邊代表客流量, 我們知道在一般的工作日中, 由站點(diǎn)和客流量構(gòu)成網(wǎng)絡(luò)結(jié)構(gòu)基本是固定的, 但是在周末或者節(jié)假日等會(huì)導(dǎo)致某些站點(diǎn)變得異常重要, 特別是在遭遇局部的極端天氣時(shí)會(huì)導(dǎo)致某些站點(diǎn)重要性失效或者其周邊可替代的節(jié)點(diǎn)就變得異常重要.與交通網(wǎng)絡(luò)類似, 還有日常生活中的電網(wǎng), 由于某些節(jié)點(diǎn)突發(fā)原因?qū)е录?jí)聯(lián)失效.另外在國際貿(mào)易網(wǎng)絡(luò)中也有類似的現(xiàn)象, 例如遭遇局部戰(zhàn)爭(zhēng)、局部地區(qū)動(dòng)蕩或者突發(fā)的金融經(jīng)濟(jì)危機(jī)等, 造成網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生微小擾動(dòng)或者重大改變.

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

圖4 4種經(jīng)典節(jié)點(diǎn)影響力算法(度、緊密度、介數(shù)、特征向量中心性)在可變度-度相關(guān)性的無標(biāo)度網(wǎng)絡(luò)中準(zhǔn)確性, 其中β表示傳播參數(shù), r表示可變度-度相關(guān)性的無標(biāo)度網(wǎng)絡(luò)中的度- 度相關(guān)性參數(shù), Kendall's tau值大小表示節(jié)點(diǎn)影響力方法的準(zhǔn)確性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.

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

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

嵌套結(jié)構(gòu)也常用來刻畫非生態(tài)系統(tǒng), 例如全球或地方的經(jīng)濟(jì)貿(mào)易格局的演變[83].圖6給出了牛肉、摩托車、醫(yī)療器械三類不同商品的國際貿(mào)易網(wǎng)絡(luò)的可視化鄰接矩陣, 對(duì)應(yīng)三個(gè)顯著不同的嵌套特性, 圖中的曲線為國際貿(mào)易中786類商品的嵌套性分布圖.隨著科技進(jìn)步和貿(mào)易日趨緊密, 這種貿(mào)易網(wǎng)絡(luò)中對(duì)應(yīng)的嵌套特性演化規(guī)律和機(jī)制, 以及與國家經(jīng)濟(jì)復(fù)雜性和影響力的映射關(guān)系.Bustos等[84]研究發(fā)現(xiàn)在網(wǎng)絡(luò)在演化過程中, 嵌套拓?fù)浣Y(jié)構(gòu)特性保持穩(wěn)定, 但是網(wǎng)絡(luò)中會(huì)有部分連邊消失或新出現(xiàn)一些連邊.這一發(fā)現(xiàn)可以用來描述和預(yù)測(cè)國家某些新產(chǎn)業(yè)的出現(xiàn)或消失的模式, 從而找到經(jīng)濟(jì)發(fā)展的新動(dòng)力, 為國家或地區(qū)經(jīng)濟(jì)的發(fā)展做出前瞻指導(dǎo).

圖6 786 類商品國際貿(mào)易網(wǎng)絡(luò)的嵌套性分布圖, 其中子圖為牛肉、摩托車、醫(yī)療器械三類不同商品的國際貿(mào)易網(wǎng)絡(luò)的可視化鄰接矩陣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 節(jié)點(diǎn)的動(dòng)力學(xué)與網(wǎng)絡(luò)結(jié)構(gòu)特征的關(guān)系預(yù)測(cè)節(jié)點(diǎn)影響力

就傳播影響力來說, 病毒在計(jì)算機(jī)網(wǎng)絡(luò)上的蔓延、傳染病、謠言、信息在現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)或虛擬的社交網(wǎng)絡(luò)中的傳播, 我們必須有效控制和引導(dǎo)復(fù)雜網(wǎng)絡(luò)的傳播行為趨利避害, 最好的方式就是在傳播擴(kuò)散之前預(yù)先推測(cè)或測(cè)定節(jié)點(diǎn)的傳播影響力.這時(shí)可以通過對(duì)計(jì)算機(jī)網(wǎng)絡(luò)、現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)以及虛擬的社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征分析, 對(duì)節(jié)點(diǎn)在特定結(jié)構(gòu)特征中顯著程度進(jìn)行定量分析.如果節(jié)點(diǎn)拓?fù)涮卣餍再|(zhì)與真實(shí)的傳播影響力存在擬合或相關(guān)性之類的映射關(guān)系[85], 那么就可以采用網(wǎng)絡(luò)結(jié)構(gòu)特征來事前推測(cè)或測(cè)定節(jié)點(diǎn)的傳播影響力.針對(duì)真實(shí)的節(jié)點(diǎn)影響力, 可以采用傳播動(dòng)力學(xué)模仿真實(shí)的傳播信息擴(kuò)散過程計(jì)算傳播影響力, 社會(huì)動(dòng)力學(xué)過程模擬計(jì)算社會(huì)影響力, 或者通過真實(shí)的社會(huì)評(píng)價(jià)獲取社會(huì)影響力, 區(qū)域經(jīng)濟(jì)影響力可以通過貿(mào)易流動(dòng)的模擬計(jì)算.針對(duì)不同的動(dòng)力學(xué), Barzel和Barabasi[86,87]給出一個(gè)統(tǒng)一的動(dòng)力學(xué)特征并分析不同動(dòng)力學(xué)的與網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系.一般動(dòng)力學(xué)過程可以簡(jiǎn)化成如下描述,

其中左式為節(jié)點(diǎn)動(dòng)力學(xué)特征隨時(shí)間演化過程, 右式中 Aij為網(wǎng)絡(luò)的鄰接矩陣, W為與節(jié)點(diǎn)自身相關(guān)的時(shí)間函數(shù), Q為節(jié)點(diǎn)對(duì)之間相互作用的時(shí)間函數(shù).節(jié)點(diǎn)的影響力可以通過動(dòng)力學(xué)仿真或數(shù)值解析獲得, 公式中網(wǎng)絡(luò)的鄰接矩陣 Aij代表是網(wǎng)絡(luò), 我們知道現(xiàn)實(shí)中網(wǎng)絡(luò)的拓?fù)潢P(guān)系容易獲得, 可以直接計(jì)算網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)屬性.如果這一結(jié)構(gòu)特征恰好刻畫實(shí)際影響力, 那么這一方法則能準(zhǔn)確預(yù)測(cè)節(jié)點(diǎn)影響力.

另外也可以從從微觀角度出發(fā), 描述節(jié)點(diǎn)生命周期內(nèi)其拓?fù)浜蛣?dòng)力學(xué)特征的普遍演化規(guī)律, 并給出其表達(dá)方式, 建立模型刻畫節(jié)點(diǎn)拓?fù)浜蛣?dòng)力學(xué)結(jié)構(gòu)特征的演化機(jī)制.節(jié)點(diǎn)的拓?fù)浜蛣?dòng)力學(xué)特征演化特征如(4)式[88,89]所示.

右式中 ? fi(t,?t)a表示實(shí)際的網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)涮卣髟?(t,?t) 時(shí)間的變化, ? fi(t,?t)e表示經(jīng)過網(wǎng)絡(luò)模型計(jì)算的理論值.如果 Ri(t,?t)=1 就表明真實(shí)的動(dòng)態(tài)網(wǎng)絡(luò)與網(wǎng)絡(luò)模型規(guī)律一致.如果Ri(t,?t)<1就表明真實(shí)的動(dòng)態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)的屬性演化慢于網(wǎng)絡(luò)模型.如果 Ri(t,?t)>1 就表明真實(shí)的動(dòng)態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)的屬性演化快于網(wǎng)絡(luò)模型.我們以最簡(jiǎn)單的度和無標(biāo)度網(wǎng)絡(luò)中優(yōu)先連接(preferential attachment)為例.在實(shí)際動(dòng)態(tài)演化網(wǎng)絡(luò)中, 節(jié)點(diǎn)在 ?t 獲得度為?ki(t,?t), 那么經(jīng)過PA模型獲得的節(jié)點(diǎn)在 ?t 獲得度為

那么度的演化動(dòng)力學(xué)可以表述為

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

4 結(jié) 論

本文系統(tǒng)總結(jié)了三類動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的一些研究進(jìn)展.在增長網(wǎng)絡(luò)中, 節(jié)點(diǎn)影響力的算法復(fù)雜性和時(shí)間偏見的問題; 網(wǎng)絡(luò)結(jié)構(gòu)實(shí)時(shí)動(dòng)態(tài)演化時(shí), 節(jié)點(diǎn)影響力的算法適應(yīng)性問題; 結(jié)構(gòu)微擾或突變的動(dòng)態(tài)網(wǎng)絡(luò)中, 節(jié)點(diǎn)影響力算法魯棒性問題以及利用網(wǎng)絡(luò)結(jié)構(gòu)演變闡釋經(jīng)濟(jì)復(fù)雜性涌現(xiàn)的問題.可以看出目前這個(gè)方向仍然有諸多挑戰(zhàn)有待解決.正如本文第三節(jié)中提及的節(jié)點(diǎn)的動(dòng)力學(xué)演化與網(wǎng)絡(luò)結(jié)構(gòu)特征的關(guān)系.如何挖掘經(jīng)典的動(dòng)力學(xué)機(jī)制和網(wǎng)絡(luò)結(jié)構(gòu)特征之間的關(guān)系, 分析基于動(dòng)力學(xué)模擬真實(shí)的節(jié)點(diǎn)影響力和基于網(wǎng)絡(luò)結(jié)構(gòu)特征挖掘的節(jié)點(diǎn)影響力之間的統(tǒng)計(jì)特性和關(guān)聯(lián)關(guān)系, 并通過數(shù)學(xué)解析和數(shù)值獲得節(jié)點(diǎn)影響力的精確解或近似解?還有就是基于網(wǎng)絡(luò)異質(zhì)性的考慮, 分析在異質(zhì)網(wǎng)絡(luò)中, 處于“胖尾”分布的大量節(jié)點(diǎn)的動(dòng)力學(xué)和拓?fù)涮卣鞯难莼Ｊ胶鸵?guī)律, 以及在演化過程中的節(jié)點(diǎn)影響力的穩(wěn)定性以及可預(yù)測(cè)性.另外隨著最近幾年大數(shù)據(jù)變得越來越容易獲得, 如何通過相互關(guān)聯(lián)的動(dòng)態(tài)網(wǎng)絡(luò)增強(qiáng)節(jié)點(diǎn)影響力的可預(yù)測(cè)性和設(shè)計(jì)綜合節(jié)點(diǎn)影響力預(yù)測(cè)算法, 這些難題的解決具有廣泛應(yīng)用場(chǎng)景.例如通過引文網(wǎng)絡(luò)和合作網(wǎng)等數(shù)據(jù)構(gòu)建的多層關(guān)聯(lián)網(wǎng)絡(luò), 建立綜合影響力預(yù)測(cè)模型, 預(yù)測(cè)科學(xué)家影響力.再如利用手機(jī)社交數(shù)據(jù)、航空網(wǎng)絡(luò)、貿(mào)易網(wǎng)絡(luò)等多個(gè)地理標(biāo)簽動(dòng)態(tài)網(wǎng)絡(luò), 通過地理映射構(gòu)建多層相互關(guān)聯(lián)演化網(wǎng)絡(luò), 設(shè)計(jì)新的地區(qū)經(jīng)濟(jì)影響力預(yù)測(cè)指標(biāo), 預(yù)測(cè)地區(qū)經(jīng)濟(jì)發(fā)展?jié)摿?最后構(gòu)建相互關(guān)聯(lián)的動(dòng)態(tài)網(wǎng)絡(luò)模型, 系統(tǒng)研究對(duì)節(jié)點(diǎn)影響力的可預(yù)測(cè)性的影響, 從而設(shè)計(jì)綜合影響力指標(biāo).