基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的無向加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估

孔江濤 黃健 龔建興 李爾玉

(國(guó)防科技大學(xué)機(jī)電工程與自動(dòng)化學(xué)院,長(zhǎng)沙 410073)

1 引 言

隨著時(shí)代的發(fā)展,人們的生產(chǎn)生活與各種復(fù)雜網(wǎng)絡(luò)系統(tǒng)的聯(lián)系越來越緊密,如計(jì)算機(jī)網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等,這些復(fù)雜網(wǎng)絡(luò)系統(tǒng)給人們提供了極大的便利.但是伴隨復(fù)雜網(wǎng)絡(luò)系統(tǒng)的危害也時(shí)有發(fā)生,如俄亥俄州克利夫蘭市的幾條高壓線路短路造成了北美大停電事故,WannaCry勒索病毒的全球大爆發(fā),傳染病的爆發(fā)和輿情危機(jī)等.網(wǎng)絡(luò)帶來的危害通常是從一小部分節(jié)點(diǎn)開始最終蔓延擴(kuò)展到整個(gè)網(wǎng)絡(luò)系統(tǒng)[1,2].復(fù)雜網(wǎng)絡(luò)系統(tǒng)中各個(gè)節(jié)點(diǎn)所處的拓?fù)浣Y(jié)構(gòu)不同,甚至各個(gè)節(jié)點(diǎn)的特性也不相同,使用定量方法對(duì)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性進(jìn)行分析意義重大,可有效指導(dǎo)人們對(duì)重要節(jié)點(diǎn)進(jìn)行性能改進(jìn)和防護(hù)加強(qiáng),達(dá)到避免危害發(fā)生或控制危害程度的目的.另一方面,分析出復(fù)雜網(wǎng)絡(luò)中重要節(jié)點(diǎn)可以幫助用戶確定雇傭社交網(wǎng)絡(luò)中哪些賬號(hào)進(jìn)行營(yíng)銷效果最好、打擊網(wǎng)絡(luò)中的哪些節(jié)點(diǎn)破壞效果最佳等.近年來,關(guān)于復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性評(píng)估方法已成為復(fù)雜網(wǎng)絡(luò)理論研究的一個(gè)重要方面,已有的研究成果多集中在挖掘復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息上,而基于網(wǎng)絡(luò)動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)估方法研究成果較少,復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性評(píng)估方法的研究仍具有很大的空間.

復(fù)雜網(wǎng)絡(luò)的重要節(jié)點(diǎn)是指相比網(wǎng)絡(luò)其他節(jié)點(diǎn)而言,能夠在更大程度上影響網(wǎng)絡(luò)的結(jié)構(gòu)與功能的一些特殊節(jié)點(diǎn)[3],現(xiàn)已衍生出很多復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性的評(píng)估方法.從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)出發(fā)的經(jīng)典方法包括度中心性方法[4]、介數(shù)中心性方法[5]、K-殼分解法[6]、PageRank方法[7]等.度中心性計(jì)算高效,但是只能反映復(fù)雜網(wǎng)絡(luò)局部信息.Chen等[8]提出了半局部中心性,其涉及了節(jié)點(diǎn)的四階鄰居信息.阮逸潤(rùn)等[9]提出了一種考慮節(jié)點(diǎn)度以及鄰居節(jié)點(diǎn)拓?fù)渲睾隙鹊墓?jié)點(diǎn)重要性評(píng)估方法,該方法只需獲取節(jié)點(diǎn)兩跳內(nèi)鄰居就可以計(jì)算出節(jié)點(diǎn)的重要度值.介數(shù)中心性僅考慮了最短路徑,Freeman[10]進(jìn)一步提出了流介數(shù)中心性,他認(rèn)為網(wǎng)絡(luò)中所有不重復(fù)的路徑中,經(jīng)過節(jié)點(diǎn)的路徑比例越大該節(jié)點(diǎn)就越重要.同時(shí),可將所有路徑通過某節(jié)點(diǎn)的路徑都賦予一個(gè)權(quán)重,并對(duì)這些權(quán)重求和用于表示該節(jié)點(diǎn)的重要程度[11].PageRank方法中假設(shè)節(jié)點(diǎn)跳轉(zhuǎn)概率相同并且算法參數(shù)依靠經(jīng)驗(yàn)決定,LeaderRank方法很好地解決了這些問題,實(shí)驗(yàn)表明LeaderRank方法擁有更好的收斂性和更強(qiáng)的魯棒性[12].此外,還有HITs(hyperlink-induced topic search)算法、基于節(jié)點(diǎn)移除的評(píng)估方法和基于Dempster-Shafer(D-S)證據(jù)理論的評(píng)估方法.HITs算法從權(quán)威值和樞紐值兩個(gè)維度表示節(jié)點(diǎn)的重要性[13].基于節(jié)點(diǎn)移除的評(píng)估方法則是通過考察移除節(jié)點(diǎn)后網(wǎng)絡(luò)結(jié)構(gòu)的破壞程度,破壞程度越大,對(duì)應(yīng)的節(jié)點(diǎn)越重要[14].基于D-S證據(jù)理論的評(píng)估方法利用證據(jù)理論將節(jié)點(diǎn)的度和節(jié)點(diǎn)的強(qiáng)度進(jìn)行融合,利用融合后形成新指標(biāo)表示節(jié)點(diǎn)的重要程度[15].類似的多指標(biāo)融合的方法還有基于多重影響力矩陣的有向加權(quán)網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法[16].僅僅從拓?fù)浣Y(jié)構(gòu)角度出發(fā)去評(píng)估節(jié)點(diǎn)重要性沒有考慮到每個(gè)節(jié)點(diǎn)的自身特點(diǎn).

考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的同時(shí),對(duì)節(jié)點(diǎn)的行為和特性進(jìn)行動(dòng)力學(xué)建模,可以得到復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型.基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型進(jìn)行節(jié)點(diǎn)重要性評(píng)估也是研究熱點(diǎn).目前較為成熟的用于節(jié)點(diǎn)重要性評(píng)估的動(dòng)力學(xué)模型是傳染病模型,在該類模型中節(jié)點(diǎn)是指可以得傳染病的人,并且這些人具有自愈的能力,其中主流的模型有病人可以反復(fù)多次得病的SIS模型[6]和病人生病治愈后具有終生免疫力的SIR模型[17],基本思路是依次設(shè)置不同節(jié)點(diǎn)處于感染狀態(tài),并通過對(duì)比一定時(shí)間內(nèi)病毒傳播的速度和范圍來評(píng)價(jià)每個(gè)節(jié)點(diǎn)的重要程度.Yan等[18]在加權(quán)無標(biāo)度網(wǎng)絡(luò)上的病毒傳播實(shí)驗(yàn)表明網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響疾病傳播過程的同時(shí),強(qiáng)度越大的節(jié)點(diǎn)越易被感染.隨著復(fù)雜網(wǎng)絡(luò)研究的深入,級(jí)聯(lián)失效現(xiàn)象逐漸引起了人們的重視,級(jí)聯(lián)失效模型是在復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上賦予節(jié)點(diǎn)一定的負(fù)載能力,并設(shè)置節(jié)點(diǎn)因負(fù)載過大失效后其負(fù)載重新分配機(jī)制,然后通過測(cè)試不同節(jié)點(diǎn)失效后網(wǎng)絡(luò)級(jí)聯(lián)失效的程度進(jìn)行節(jié)點(diǎn)的重要性評(píng)估[19].杜文舉等[20]建立了公交網(wǎng)絡(luò)耦合映象格子模型用于描述網(wǎng)絡(luò)級(jí)聯(lián)失效行為,并通過實(shí)驗(yàn)說明節(jié)點(diǎn)度越大越容易造成網(wǎng)絡(luò)全局故障.在復(fù)雜網(wǎng)絡(luò)可控性研究領(lǐng)域,可以將最佳驅(qū)動(dòng)節(jié)點(diǎn)看作重要的節(jié)點(diǎn)[9].Liu等[21]發(fā)現(xiàn)在節(jié)點(diǎn)自身動(dòng)力學(xué)模型相同的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)系統(tǒng)中,驅(qū)動(dòng)節(jié)點(diǎn)傾向于避免高度節(jié)點(diǎn).進(jìn)一步,Jia和Barabási等[22]對(duì)最小的驅(qū)動(dòng)節(jié)點(diǎn)集進(jìn)行研究,發(fā)現(xiàn)節(jié)點(diǎn)的入度越大,其成為驅(qū)動(dòng)節(jié)點(diǎn)的可能性越小,節(jié)點(diǎn)是否為驅(qū)動(dòng)節(jié)點(diǎn)與節(jié)點(diǎn)的出度無關(guān).基于動(dòng)力學(xué)模型的方法包含網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息,也包含對(duì)節(jié)點(diǎn)的建模,并且能夠在時(shí)域上對(duì)網(wǎng)絡(luò)狀態(tài)的變化進(jìn)行描述,所以評(píng)價(jià)比較全面.但是目前已有的基于動(dòng)力學(xué)模型的網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法也有不足.級(jí)聯(lián)失效模型主要適用于會(huì)發(fā)生“雪崩”式故障的復(fù)雜網(wǎng)絡(luò).利用傳染病模型進(jìn)行復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)評(píng)估時(shí),疫情的傳播最后應(yīng)具有穩(wěn)定規(guī)模,穩(wěn)定的疫情規(guī)模是進(jìn)行節(jié)點(diǎn)重要性評(píng)估的前提,基于復(fù)雜網(wǎng)絡(luò)可控性研究領(lǐng)域的動(dòng)力學(xué)模型進(jìn)行節(jié)點(diǎn)重要性分析時(shí)同樣要求建立的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型穩(wěn)定可控,但是針對(duì)復(fù)雜網(wǎng)絡(luò)建立其對(duì)應(yīng)的滿足節(jié)點(diǎn)重要性評(píng)估條件的傳染病模型和動(dòng)力學(xué)模型困難,故這兩種方法難以直接推廣使用.

本文提出了基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)估方法,其適用于任意無向加權(quán)網(wǎng)絡(luò)的節(jié)點(diǎn)重要性評(píng)估,具有良好的通用性.復(fù)雜網(wǎng)絡(luò)的正常狀態(tài)是所有節(jié)點(diǎn)都處于各自的穩(wěn)定平衡態(tài),節(jié)點(diǎn)偏離自己的穩(wěn)定平衡態(tài)后,這種非穩(wěn)定狀態(tài)會(huì)通過網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)影響到整個(gè)網(wǎng)絡(luò).本文提出的節(jié)點(diǎn)重要性評(píng)估方法就是根據(jù)節(jié)點(diǎn)偏離穩(wěn)定平衡態(tài)對(duì)整個(gè)網(wǎng)絡(luò)的影響程度來確定節(jié)點(diǎn)的重要性,對(duì)網(wǎng)絡(luò)的影響程度越大,對(duì)應(yīng)的節(jié)點(diǎn)越重要.本文提出的方法不僅包含了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息,還包含了單個(gè)節(jié)點(diǎn)的動(dòng)力學(xué)模型,并通過仿真方法對(duì)網(wǎng)絡(luò)動(dòng)力學(xué)模型狀態(tài)變化進(jìn)行分析,最終完成對(duì)節(jié)點(diǎn)重要性的評(píng)估.本文的具體結(jié)構(gòu)如下:第二部分提出了無向加權(quán)網(wǎng)絡(luò)對(duì)應(yīng)的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的構(gòu)建方法,并證明了構(gòu)建的動(dòng)力學(xué)模型都是大范圍內(nèi)一致漸近穩(wěn)定的,同時(shí)建立了基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo);第三部分提出了基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型進(jìn)行節(jié)點(diǎn)重要性評(píng)估的擾動(dòng)測(cè)試方法和破壞測(cè)試方法;第四部分對(duì)本文提出的節(jié)點(diǎn)重要性評(píng)估方法進(jìn)行實(shí)驗(yàn)驗(yàn)證;最后給出結(jié)論.

2 復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的構(gòu)建及節(jié)點(diǎn)重要性評(píng)估標(biāo)準(zhǔn)

本節(jié)首先介紹構(gòu)建無向加權(quán)網(wǎng)絡(luò)動(dòng)力學(xué)模型的方法,進(jìn)一步利用李雅普諾夫穩(wěn)定性定理證明該類復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型是大范圍內(nèi)一致漸近穩(wěn)定的,最后提出基于動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)估標(biāo)準(zhǔn).

2.1 復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型構(gòu)建方法

線性耦合常微分方程組在時(shí)空復(fù)雜網(wǎng)絡(luò)和復(fù)雜系統(tǒng)研究中有廣泛的應(yīng)用,本文用線性耦合常微分方程組描述復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型.給定無向加權(quán)網(wǎng)絡(luò)模型為三元組G={V,E,W},式中V={v1,v2,···,vn}表示節(jié)點(diǎn)集合.文中網(wǎng)絡(luò)模型節(jié)點(diǎn)個(gè)數(shù)都為n;E={e1,e2,···,em}表示邊的集合,(vi,vj)∈E表示從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的連邊;為連邊的權(quán)重矩陣,其中wii=0且wij>0,wij(ij)表示邊(vi,vj)的權(quán)重.無向加權(quán)網(wǎng)絡(luò)的權(quán)重矩陣W滿足

根據(jù)W可以得出無向加權(quán)圖的拉普拉斯矩陣其中

顯然有本文假定權(quán)重值越大,其連接的節(jié)點(diǎn)關(guān)系越緊密.對(duì)復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)vi建立如下線性耦合常微分方程:

其中,xi(t)∈R表示節(jié)點(diǎn)vi在t時(shí)刻的狀態(tài),c>0表示網(wǎng)絡(luò)整體耦合強(qiáng)度,aij為網(wǎng)絡(luò)拉普拉斯矩陣對(duì)應(yīng)位置上的元素.本文設(shè)定c=1,fi(·):R→R是一個(gè)連續(xù)函數(shù),為節(jié)點(diǎn)vi的自身動(dòng)力學(xué)模型.

復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)的自身動(dòng)力學(xué)模型可以分為兩類.如果復(fù)雜網(wǎng)絡(luò)中所有節(jié)點(diǎn)的自身動(dòng)力學(xué)模型都相同,那么構(gòu)建的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型就是同質(zhì)網(wǎng)絡(luò).如果復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)都有各自的自身動(dòng)力學(xué)模型,那么構(gòu)建的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型就是異質(zhì)網(wǎng)絡(luò).構(gòu)建同質(zhì)網(wǎng)絡(luò)時(shí),任意節(jié)點(diǎn)vi的自身動(dòng)力學(xué)模型如下:

構(gòu)建異質(zhì)網(wǎng)絡(luò)時(shí),每個(gè)節(jié)點(diǎn)的自身動(dòng)力學(xué)模型根據(jù)實(shí)際問題進(jìn)行確定,節(jié)點(diǎn)自身動(dòng)力學(xué)模型具有一個(gè)可調(diào)參數(shù),節(jié)點(diǎn)vi的自身動(dòng)力學(xué)模型如下:

其中γi∈R為節(jié)點(diǎn)vi自身動(dòng)力學(xué)模型的可調(diào)參數(shù),其取值范圍為γi<0(i=1,2,···,n).γi的取值反映節(jié)點(diǎn)自身的穩(wěn)定性.節(jié)點(diǎn)自身動(dòng)力學(xué)模型的可調(diào)參數(shù)|γi|值大時(shí),增益小,抗干擾能力強(qiáng),并且恢復(fù)穩(wěn)定的時(shí)間短,所以穩(wěn)定性好.

本文提出的建立復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的方法也適用于對(duì)稱有向加權(quán)網(wǎng)絡(luò).對(duì)稱有向加權(quán)網(wǎng)絡(luò),其權(quán)重矩陣為對(duì)稱矩陣,根據(jù)(2)式可以得出其拉普拉斯矩陣,進(jìn)而建立(3)式所示的對(duì)稱有向加權(quán)網(wǎng)絡(luò)動(dòng)力學(xué)模型.

2.2 復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型穩(wěn)定性分析

建立復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型后,需要對(duì)動(dòng)力學(xué)模型的穩(wěn)定性進(jìn)行分析.正常運(yùn)轉(zhuǎn)時(shí)復(fù)雜網(wǎng)絡(luò)系統(tǒng)處于穩(wěn)定的平衡態(tài).只有建立的動(dòng)力學(xué)模型穩(wěn)定,才能通過測(cè)量復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型偏離穩(wěn)態(tài)的程度衡量網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的重要性,所以建立穩(wěn)定的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型是后續(xù)展開節(jié)點(diǎn)重要性分析的基礎(chǔ).本文根據(jù)李雅普諾夫穩(wěn)定性定理,對(duì)復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的穩(wěn)定性進(jìn)行證明.這里先介紹三個(gè)定理.

定理1[24]如果方陣是實(shí)矩陣,滿足則|B|>0.

定理2如果方陣是實(shí)對(duì)稱矩陣,其特征值都為實(shí)數(shù),且存在正交矩陣Q,使QTBQ=Q?1BQ為對(duì)角陣.

定理3[25]設(shè)有一動(dòng)態(tài)系統(tǒng),其狀態(tài)方程為

其中X(t)∈Rn為狀態(tài)向量,f(·):Rn×T→Rn是狀態(tài)和時(shí)間的函數(shù).如果系統(tǒng)在平衡狀態(tài)Xe的某些鄰域內(nèi)存在一個(gè)正定的具有連續(xù)一階偏導(dǎo)數(shù)的標(biāo)量函數(shù)V[X(t),t],其導(dǎo)數(shù)[X(t),t]是負(fù)定的,當(dāng)∥X∥→∞時(shí),有V[X(t),t]→∞,則該平衡態(tài)是大范圍內(nèi)一致漸近穩(wěn)定的.

為了便于分析,將無向加權(quán)網(wǎng)絡(luò)的動(dòng)力學(xué)模型寫成狀態(tài)方程:

其中X(t)=(x1(t),x2(t),···,xn(t))T, 偶和強(qiáng)度c=1,F=diag{γ1,γ2,···,γn}為對(duì)角矩陣,γi(i=1,2,···,n)為節(jié)點(diǎn)vi自身動(dòng)力學(xué)模型的可調(diào)參數(shù),A為復(fù)雜網(wǎng)絡(luò)的拉普拉斯矩陣.取復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的平衡狀態(tài)Xe=0,定義李雅普諾夫函數(shù)

其中P∈Rn×n為正定矩陣.取P為單位矩陣,顯然正定,當(dāng)X(t)Xe時(shí),有V[X(t),t]>0,并且當(dāng)∥X∥→∞時(shí),有V[X(t),t]→∞.

進(jìn)一步,對(duì)V[X(t),t]求導(dǎo)可以得到

設(shè)V1[X(t),t]=XT(t)(FT+F)X(t),V2[X(t),t]=cXT(t)(AT+A)X(t).下面對(duì)V1[X(t),t]和V2[X(t),t]分別進(jìn)行分析.對(duì)于V1[X(t),t],由于F為一個(gè)對(duì)角矩陣且對(duì)角元γi<0,所以當(dāng)X(t)Xe有

對(duì)于V2[X(t),t],設(shè)矩陣且A′=為對(duì)稱矩陣,其任意特征值都非正實(shí)數(shù).因?yàn)?/p>

存在n維列向量滿足A′Y′=0Y′,所以0是矩陣A′的特征值.假設(shè)矩陣A′存在一個(gè)特征值λ>0,則有|λI?A′|=0,其中I為單位陣.矩陣A′中任意對(duì)角元任意非對(duì)角元并且

設(shè)矩陣所以矩陣D的任意對(duì)角元素顯然有

根據(jù)定理1可得|D|=|λI?A′|>0,所以矩陣A′不存在正實(shí)數(shù)特征值.同時(shí)A′為對(duì)稱實(shí)矩陣,根據(jù)定理2可知,其可進(jìn)行正交對(duì)角線化,假設(shè)A′的特征值為0=λ1>λ2>···>λn以及其正交化矩陣為Φ,然后有

其中ΦX(t)=(z1(t),z2(t),···,zn(t))T.故當(dāng)X(t)Xe時(shí)有V1[X(t),t]<0 和V2[X(t),t]6 0,所以˙V[X(t),t]<0,根據(jù)定理3可知,本文針對(duì)無向加權(quán)網(wǎng)絡(luò)和對(duì)稱有向加權(quán)網(wǎng)絡(luò)構(gòu)建的動(dòng)力學(xué)模型簇都是大范圍內(nèi)一致漸近穩(wěn)定的,并且該模型簇具有相同的穩(wěn)定平衡狀態(tài)Xe=0.

值得注意的是,構(gòu)建的動(dòng)力學(xué)模型的李雅普諾夫函數(shù)的導(dǎo)數(shù)滿足

所以對(duì)應(yīng)的李雅普諾夫函數(shù)成指數(shù)級(jí)收斂,

其中γmax<0.指數(shù)級(jí)收斂特性保證了構(gòu)建的動(dòng)力學(xué)模型能夠在有限的時(shí)間內(nèi)恢復(fù)穩(wěn)定.此外,當(dāng)有向加權(quán)網(wǎng)絡(luò)圖的權(quán)重矩陣滿足

可以稱其為有向加權(quán)平衡網(wǎng)絡(luò)圖[26],對(duì)于有向加權(quán)平衡網(wǎng)絡(luò),利用本文提出的構(gòu)建復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型方法構(gòu)建的動(dòng)力學(xué)模型同樣是大范圍內(nèi)一致漸近穩(wěn)定的.

2.3 基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)估標(biāo)準(zhǔn)

本文利用復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型描述復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)間的相互影響活動(dòng).當(dāng)單個(gè)節(jié)點(diǎn)狀態(tài)變化時(shí),這種變化會(huì)在網(wǎng)絡(luò)中傳播,進(jìn)而影響網(wǎng)絡(luò)整體平衡態(tài),這種平衡態(tài)的變化可以用來衡量節(jié)點(diǎn)的重要性.通過對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行測(cè)試,測(cè)量測(cè)試開始至動(dòng)力學(xué)模型重新穩(wěn)定的時(shí)期內(nèi)動(dòng)力學(xué)模型偏離平衡態(tài)Xe的程度.測(cè)試的節(jié)點(diǎn)致使復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型偏離穩(wěn)定平衡態(tài)的程度越大,該節(jié)點(diǎn)的重要程度越高.基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型,本文建立了兩級(jí)指標(biāo)衡量復(fù)雜網(wǎng)絡(luò)偏離穩(wěn)定平衡態(tài)的程度.首先是復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的偏離均值,該指標(biāo)衡量模型總體的偏離穩(wěn)定平衡態(tài)Xe的距離.假設(shè)測(cè)試模型為S,需要分析其在測(cè)試開始至穩(wěn)定的時(shí)期T內(nèi)的狀態(tài)變化情況.復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的偏離均值計(jì)算公式如下:

其中n為復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型中的節(jié)點(diǎn)個(gè)數(shù);T0為測(cè)試開始時(shí)間;?t為時(shí)間步長(zhǎng),且有m?t=T.復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的基于偏離均值的方差是衡量所有節(jié)點(diǎn)在偏離均值附近波動(dòng)的情況.基于偏離均值的方差的計(jì)算公式如下:

基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型進(jìn)行節(jié)點(diǎn)重要性評(píng)估時(shí),本文提出了兩種測(cè)試方法,分別為擾動(dòng)測(cè)試方法和破壞測(cè)試方法,具體見第3節(jié).需要說明的是:在同質(zhì)網(wǎng)絡(luò)擾動(dòng)測(cè)試中,僅使用基于偏離均值的方差作為節(jié)點(diǎn)重要性評(píng)估的評(píng)估指標(biāo);而在同質(zhì)網(wǎng)絡(luò)破壞測(cè)試、異質(zhì)網(wǎng)絡(luò)擾動(dòng)測(cè)試和破壞測(cè)試中,則是先比較復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的偏離均值,如果偏離均值無法區(qū)分節(jié)點(diǎn)重要度,進(jìn)一步使用基于偏離均值的方差.無論是偏離均值還是基于偏離均值的方差,都是值越小對(duì)應(yīng)的節(jié)點(diǎn)重要性越低.

3 基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)估方法

在同質(zhì)和異質(zhì)網(wǎng)絡(luò)中,節(jié)點(diǎn)自身動(dòng)力學(xué)模型描述節(jié)點(diǎn)自身的工作狀態(tài)變化,其受影響的性質(zhì)可分為兩種:一種是節(jié)點(diǎn)受到干擾后并未被破壞,可以自行恢復(fù);另一種是受到擾動(dòng)后節(jié)點(diǎn)被破壞,即節(jié)點(diǎn)狀態(tài)始終處于一種非正常狀態(tài).為了在兩種不同情況下進(jìn)行節(jié)點(diǎn)重要性評(píng)估,本文分別提出了擾動(dòng)測(cè)試方法和破壞測(cè)試方法.

3.1 基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的擾動(dòng)測(cè)試方法

擾動(dòng)測(cè)試方法是對(duì)復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型中的測(cè)試節(jié)點(diǎn)施加一個(gè)脈沖輸入,然后觀察自脈沖輸入起到復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型重新穩(wěn)定的時(shí)期T內(nèi)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的狀態(tài)變化,對(duì)節(jié)點(diǎn)vi進(jìn)行擾動(dòng)測(cè)試的情形如圖1所示.

圖1 擾動(dòng)測(cè)試示意圖Fig.1.Schematic diagram of the perturbation test.

對(duì)(7)式所示的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型進(jìn)行擾動(dòng)測(cè)試,其對(duì)應(yīng)的擾動(dòng)測(cè)試模型如下:

其中F,c和A與(7)式中的定義相同;B=[b1,b2,···,bn]為輸入矩陣,如果測(cè)試節(jié)點(diǎn)為vi,則bi=1 并且bj=0(ji;j=1,2,···,n);u為脈沖輸入;C為n階單位矩陣.在擾動(dòng)測(cè)試模型中,節(jié)點(diǎn)的初始狀態(tài)為X(T0)=Xe,由于C為單位陣,節(jié)點(diǎn)的狀態(tài)即測(cè)試模型的輸出Y(t).在對(duì)同質(zhì)網(wǎng)絡(luò)中任意節(jié)點(diǎn)進(jìn)行擾動(dòng)測(cè)試時(shí),對(duì)應(yīng)的復(fù)雜網(wǎng)絡(luò)擾動(dòng)測(cè)試模型都具有相同的偏離均值,所以需要利用基于偏離均值的方差區(qū)分不同節(jié)點(diǎn)的重要性.初始狀態(tài)為零的情況下,(16)式表示的同質(zhì)網(wǎng)絡(luò)擾動(dòng)測(cè)試的偏離均值為

其中,C′是一個(gè)元素都為1的n維行向量,e(F+cA)(T+T0?t)為狀態(tài)轉(zhuǎn)移矩陣.因?yàn)槔绽咕仃嘇滿足所以有

其中由(18)式可知,對(duì)于任意兩個(gè)輸入矩陣和只要有那么輸入矩陣B1和B2對(duì)應(yīng)的動(dòng)力學(xué)模型的偏離均值相等.在同質(zhì)網(wǎng)絡(luò)擾動(dòng)測(cè)試中,不同節(jié)點(diǎn)的擾動(dòng)測(cè)試動(dòng)力學(xué)模型的輸入矩陣元素加和都為1,所以同質(zhì)網(wǎng)絡(luò)的所有擾動(dòng)測(cè)試動(dòng)力學(xué)模型都有相同的偏離均值.

3.2 基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的破壞測(cè)試方法

破壞測(cè)試是指使測(cè)試節(jié)點(diǎn)狀態(tài)始終處于某個(gè)固定的非平衡態(tài),如圖2所示,當(dāng)設(shè)置節(jié)點(diǎn)vi為破壞節(jié)點(diǎn),則有節(jié)點(diǎn)狀態(tài)xi(t)≡1,該節(jié)點(diǎn)非穩(wěn)定狀態(tài)會(huì)直接影響與它相連的鄰居節(jié)點(diǎn),進(jìn)而影響整個(gè)網(wǎng)絡(luò)的穩(wěn)定平衡態(tài),觀察自測(cè)試節(jié)點(diǎn)被破壞起到復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型重新穩(wěn)定的時(shí)期T內(nèi)各個(gè)節(jié)點(diǎn)的狀態(tài)變化.

圖2 破壞測(cè)試示意圖Fig.2.Schematic diagram of the destructive test.

針對(duì)(7)式所示復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型進(jìn)行破壞測(cè)試,如果測(cè)試節(jié)點(diǎn)為vi,其對(duì)應(yīng)的破壞測(cè)試模型如下:

參照2.2節(jié)動(dòng)力學(xué)模型穩(wěn)定性分析的過程,可以證明該狀態(tài)演變模型除測(cè)試節(jié)點(diǎn)外的其他節(jié)點(diǎn)狀態(tài)是大范圍內(nèi)一致漸近穩(wěn)定的.在進(jìn)行破壞測(cè)試過程中,如果測(cè)試節(jié)點(diǎn)為vi,節(jié)點(diǎn)的初始狀態(tài)都設(shè)定為并且滿足(ji;j=1,2,···,n),并且有最后對(duì)不同節(jié)點(diǎn)的破壞測(cè)試數(shù)據(jù)進(jìn)行分析,按照先比較偏離均值,再比較基于偏離均值的方差的順序,對(duì)節(jié)點(diǎn)進(jìn)行重要性評(píng)估.

4 實(shí)驗(yàn)分析

基于動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)估方法的驗(yàn)證實(shí)驗(yàn)可以分為同質(zhì)網(wǎng)絡(luò)的擾動(dòng)測(cè)試、同質(zhì)網(wǎng)絡(luò)的破壞測(cè)試、異質(zhì)網(wǎng)絡(luò)的擾動(dòng)測(cè)試和異質(zhì)網(wǎng)絡(luò)的破壞測(cè)試共四類.本節(jié)具體的安排是通過實(shí)驗(yàn)對(duì)同質(zhì)網(wǎng)絡(luò)擾動(dòng)測(cè)試方法的有效性進(jìn)行解釋說明;進(jìn)一步選取度中心性方法、互信息方法[27]、PageRank[28]方法和介數(shù)中心性方法與同質(zhì)網(wǎng)絡(luò)破壞測(cè)試方法進(jìn)行比較,說明同質(zhì)網(wǎng)絡(luò)破壞測(cè)試方法的有效性;而在異質(zhì)網(wǎng)絡(luò)的擾動(dòng)測(cè)試和破壞測(cè)試中,本文通過設(shè)置不同的節(jié)點(diǎn)自身動(dòng)力學(xué)模型可調(diào)參數(shù)并進(jìn)行分組實(shí)驗(yàn),對(duì)分組實(shí)驗(yàn)的評(píng)估結(jié)果進(jìn)行比較分析,說明異質(zhì)網(wǎng)絡(luò)的擾動(dòng)測(cè)試方法和破壞測(cè)試方法的有效性.

4.1 擾動(dòng)測(cè)試的有效性分析

擾動(dòng)測(cè)試分為同質(zhì)網(wǎng)絡(luò)的擾動(dòng)測(cè)試和異質(zhì)網(wǎng)絡(luò)的擾動(dòng)測(cè)試,本文分別利用ARPA(advanced research project agency)網(wǎng)絡(luò)和DWS(Dobbs-Watts-Sabel)網(wǎng)絡(luò)進(jìn)行擾動(dòng)測(cè)試.對(duì)ARPA網(wǎng)絡(luò)的邊賦予權(quán)重[29],得到如圖3所示的無向加權(quán)ARPA網(wǎng)絡(luò)并建立其同質(zhì)網(wǎng)絡(luò)動(dòng)力學(xué)模型.依次對(duì)每個(gè)節(jié)點(diǎn)施加脈沖輸入,計(jì)算脈沖輸入下測(cè)試模型的基于偏離均值的方差,具體結(jié)果如圖4所示.擾動(dòng)測(cè)試方法下,節(jié)點(diǎn)v9,v8,v10比較重要,從圖3可以發(fā)現(xiàn),這些節(jié)點(diǎn)屬于邊緣節(jié)點(diǎn),這些節(jié)點(diǎn)的度比較小,而節(jié)點(diǎn)v2,v3,v14受到脈沖輸入后,對(duì)應(yīng)的擾動(dòng)測(cè)試模型的基于偏離均值的方差較小,重要程度低,所以結(jié)論是節(jié)點(diǎn)度數(shù)低的重要程度高,而節(jié)點(diǎn)度數(shù)高的重要程度低.可以看出擾動(dòng)測(cè)試的結(jié)論與Jia和Barabási[22]發(fā)現(xiàn)驅(qū)動(dòng)節(jié)點(diǎn)傾向于避免高度節(jié)點(diǎn)的結(jié)論一致.本質(zhì)原因是當(dāng)節(jié)點(diǎn)的度較高時(shí),與其相連接的節(jié)點(diǎn)多,在不破壞該節(jié)點(diǎn)的前提下,該節(jié)點(diǎn)會(huì)將沖擊向周圍節(jié)點(diǎn)分?jǐn)偛⒔柚麄€(gè)復(fù)雜網(wǎng)絡(luò)快速恢復(fù)穩(wěn)定狀態(tài).

圖3 無向加權(quán)ARPA圖絡(luò)Fig.3.Undirected weighted network obtained by the ARPA network.

圖4 ARPA網(wǎng)絡(luò)節(jié)點(diǎn)按基于偏離均值的方差大小排序Fig.4.Nodes in ARPA sorted by the variance from the mean deviation.

在異質(zhì)網(wǎng)絡(luò)擾動(dòng)測(cè)試上,本文建立了DWS網(wǎng)絡(luò)的異質(zhì)網(wǎng)絡(luò)動(dòng)力學(xué)模型.DWS網(wǎng)絡(luò)既含有規(guī)則的樹形骨架,又含有隨機(jī)的連接[30].從DWS網(wǎng)絡(luò)反映的實(shí)際物理系統(tǒng)上看,層級(jí)之間有隸屬關(guān)系,第一層節(jié)點(diǎn)只有一個(gè),級(jí)別最高,層級(jí)越高的節(jié)點(diǎn)級(jí)別越低.本文假設(shè)處于樹形骨架層級(jí)越低的節(jié)點(diǎn),其自身動(dòng)力學(xué)模型的穩(wěn)定性越好,節(jié)點(diǎn)vi自身動(dòng)力學(xué)模型的可調(diào)參數(shù)表示網(wǎng)絡(luò)的平均度,fG(vi)表示節(jié)點(diǎn)vi所屬的層級(jí).本文建立了四層共100個(gè)節(jié)點(diǎn)的DWS網(wǎng)絡(luò),添加連接的算法是任意選擇兩個(gè)節(jié)點(diǎn)i和j,依概率

在節(jié)點(diǎn)vi和節(jié)點(diǎn)vj間添加隨機(jī)的連接,其中Dij表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj最近共同上級(jí)的深度,di和dj分別表示節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的深度,并且所有邊的權(quán)重皆為1.通過對(duì)DWS網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)進(jìn)行擾動(dòng)測(cè)試,得到的節(jié)點(diǎn)重要性排序如圖5所示.圖中橫坐標(biāo)表示排序,縱坐標(biāo)表示節(jié)點(diǎn)的編號(hào),圖中紫色的三條橫線將所有點(diǎn)分為4個(gè)部分,從下往上分別對(duì)應(yīng)于第一層節(jié)點(diǎn)、第二層節(jié)點(diǎn)、第三層節(jié)點(diǎn)和第四層節(jié)點(diǎn),級(jí)別最高的第一層節(jié)點(diǎn)只有一個(gè)節(jié)點(diǎn),第二層節(jié)點(diǎn)有5個(gè),第三層節(jié)點(diǎn)有19個(gè),其余的都是第四層的節(jié)點(diǎn).可見級(jí)別越低的節(jié)點(diǎn)重要性越高,這不僅是因?yàn)榧?jí)別低的節(jié)點(diǎn)度數(shù)小,同時(shí)也是因?yàn)榧?jí)別低的節(jié)點(diǎn)自身動(dòng)力學(xué)模型穩(wěn)定性差,容易受擾動(dòng)影響,這與對(duì)DWS網(wǎng)絡(luò)進(jìn)行級(jí)聯(lián)失效時(shí)選擇從末端節(jié)點(diǎn)進(jìn)行打擊相符[31].進(jìn)一步,如果將第一層和第二層的所有節(jié)點(diǎn)自身動(dòng)力學(xué)模型可調(diào)參數(shù)都設(shè)置為經(jīng)過擾動(dòng)測(cè)試得出的節(jié)點(diǎn)重要性排序如圖6所示,與圖5相比,可以發(fā)現(xiàn)第一層和第二層節(jié)點(diǎn)重要性有明顯提高,并且都高于第三層節(jié)點(diǎn),特別是節(jié)點(diǎn)1從第100位提高至第57位,節(jié)點(diǎn)5從第98位提高至第54位.該變化符合實(shí)際,因?yàn)樵诙炔蛔兊那闆r下節(jié)點(diǎn)自身穩(wěn)定性與節(jié)點(diǎn)的重要程度負(fù)相關(guān),即穩(wěn)定性越差的節(jié)點(diǎn),其重要程度越高.

圖5 擾動(dòng)測(cè)試條件下DWS網(wǎng)絡(luò)節(jié)點(diǎn)的重要性排序Fig.5.Rank of important nodes in DWS under disturbance test.

圖6 擾動(dòng)測(cè)試條件下調(diào)整后的DWS網(wǎng)絡(luò)節(jié)點(diǎn)的重要性排序Fig.6.Rank of important nodes in adjusted DWS under disturbance test.

4.2 破壞測(cè)試的有效性分析

本節(jié)先對(duì)同質(zhì)網(wǎng)絡(luò)破壞測(cè)試方法的有效性進(jìn)行驗(yàn)證,然后對(duì)異質(zhì)網(wǎng)絡(luò)破壞測(cè)試方法的有效性進(jìn)行驗(yàn)證.同質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)自身動(dòng)力學(xué)模型相同,所以同質(zhì)網(wǎng)絡(luò)破壞測(cè)試方法可以與其他基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的節(jié)點(diǎn)重要性方法進(jìn)行對(duì)比分析,本文選用了度中心性方法、互信息方法、PageRank方法和介數(shù)中心性方法與同質(zhì)網(wǎng)絡(luò)破壞測(cè)試方法進(jìn)行比較.首先在三種典型網(wǎng)絡(luò)上進(jìn)行對(duì)比驗(yàn)證,其分別為圖3所示的ARPA網(wǎng)絡(luò)、圖7所示的對(duì)稱無向加權(quán)網(wǎng)絡(luò)[27]以及圖8所示的典型社交網(wǎng)絡(luò)——Karate俱樂部網(wǎng)絡(luò)[32].表1—表3分別列出了在這三種網(wǎng)絡(luò)上不同方法得到的前10個(gè)重要節(jié)點(diǎn),表中括號(hào)前數(shù)值為節(jié)點(diǎn)編號(hào);括號(hào)內(nèi)為對(duì)應(yīng)方法計(jì)算所得數(shù)值,這些數(shù)值是節(jié)點(diǎn)排序的依據(jù).對(duì)于ARPA網(wǎng)來說,破壞性測(cè)試方法得出的前4個(gè)重要節(jié)點(diǎn)一定程度上是另外四種方法的綜合,即和其余四種方法中的兩種方法結(jié)論相同.值得注意的是,破壞性測(cè)試方法的結(jié)論與PageRank方法的結(jié)論差異最小.對(duì)于對(duì)稱無向加權(quán)網(wǎng)絡(luò)來說,破壞性測(cè)試得出的前4個(gè)重要節(jié)點(diǎn)也是度中心性方法、互信息方法、PageRank方法和介數(shù)中心性方法得出的前4個(gè)重要節(jié)點(diǎn).對(duì)于Karate俱樂部網(wǎng)絡(luò)來說,五種方法得出的最重要的五個(gè)重要節(jié)點(diǎn)基本相同,只有互信息方法得出的第4、第5重要節(jié)點(diǎn)的順序和其他四種方法的不同.這三個(gè)網(wǎng)絡(luò)上的實(shí)驗(yàn)表明破壞測(cè)試方法是合理有效的.此外,與另外四種方法相比,破壞性測(cè)試方法在節(jié)點(diǎn)重要性評(píng)估上的區(qū)分度最好,主要體現(xiàn)在表1中節(jié)點(diǎn)12和節(jié)點(diǎn)19,除破壞性測(cè)試方法和介數(shù)中心性方法,其余三種方法無法區(qū)分這兩個(gè)節(jié)點(diǎn),以及在表2中破壞性測(cè)試方法計(jì)算出的節(jié)點(diǎn)偏離均值完全反映出了節(jié)點(diǎn)對(duì)稱關(guān)系,明顯優(yōu)于其他四種方法.

圖7 對(duì)稱無向加權(quán)網(wǎng)絡(luò)Fig.7.Undirected weighted network with symmetric structure.

圖8 Karate俱樂部網(wǎng)絡(luò)Fig.8.Karate club network.

表1 無向加權(quán)ARPA網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序結(jié)果Table 1.Importance ranking results of the undirected weighted ARPA network.

表2 圖7對(duì)稱網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序結(jié)果Table 2.Importance ranking results of the undirected symmetric weighted network in Fig.7.

表3 加權(quán)Karate俱樂部網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序結(jié)果Table 3.Importance ranking results of the Karate club network.

在實(shí)際復(fù)雜網(wǎng)絡(luò)系統(tǒng)中,很多網(wǎng)絡(luò)都是BBV(Barrat-Barthelemy-Vespignani)網(wǎng)絡(luò),即網(wǎng)絡(luò)的度和節(jié)點(diǎn)權(quán)重都滿足冪律分布.本文隨機(jī)建立了七類BBV網(wǎng)絡(luò)模型[33],它們的初始節(jié)點(diǎn)數(shù)為9,10,11,12,13,14,15,初始邊權(quán)均為1,新增邊帶來的額外流量為1,每次增加1個(gè)節(jié)點(diǎn)新增加的邊分別為9,10,11,12,13,14,15.每類模型都建立50個(gè)具體網(wǎng)絡(luò)進(jìn)行分析.本文使用網(wǎng)絡(luò)效率下降比例指標(biāo),用于衡量移除最重要節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)效率的影響,具體在七類共350個(gè)隨機(jī)產(chǎn)生的BBV網(wǎng)絡(luò)上,利用該指標(biāo)對(duì)破壞性測(cè)試方法和度中心性方法、互信息方法、PageRank方法、介數(shù)中心性方法得出的重要節(jié)點(diǎn)進(jìn)行比較分析.網(wǎng)絡(luò)效率下降比例可表示為[34]

其中η為節(jié)點(diǎn)移除后網(wǎng)絡(luò)效率,η0為未移除節(jié)點(diǎn)時(shí)的網(wǎng)絡(luò)效率.針對(duì)本文中權(quán)重越大表示聯(lián)系越緊密的情況,設(shè)定相鄰節(jié)點(diǎn)的路徑為對(duì)應(yīng)邊權(quán)的倒數(shù),具體的節(jié)點(diǎn)移除后網(wǎng)絡(luò)效率為

圖9 新增節(jié)點(diǎn)與之前9個(gè)節(jié)點(diǎn)相連的BBV網(wǎng)絡(luò)的效率差值分布函數(shù)Fig.9.Efficiency difference distribution function of the BBV network with every new node connected to the previous 9 nodes.

圖10 新增節(jié)點(diǎn)與之前10個(gè)節(jié)點(diǎn)相連的BBV網(wǎng)絡(luò)的效率差值分布函數(shù)Fig.10.Efficiency difference distribution function of the BBV network with every new node connected to the previous 10 nodes.

圖11 新增節(jié)點(diǎn)與之前11個(gè)節(jié)點(diǎn)相連的BBV網(wǎng)絡(luò)的效率差值分布函數(shù)Fig.11.Efficiency difference distribution function of the BBV network with every new node connected to the previous 11 nodes.

圖12 新增節(jié)點(diǎn)與之前12個(gè)節(jié)點(diǎn)相連的BBV網(wǎng)絡(luò)的效率差值分布函數(shù)Fig.12.Efficiency difference distribution function of the BBV network with every new node connected to the previous 12 nodes.

圖13 新增節(jié)點(diǎn)與之前13個(gè)節(jié)點(diǎn)相連的BBV網(wǎng)絡(luò)的效率差值分布函數(shù)Fig.13.Efficiency difference distribution function of the BBV network with every new node connected to the previous 13 nodes.

圖14 新增節(jié)點(diǎn)與之前14個(gè)節(jié)點(diǎn)相連的BBV網(wǎng)絡(luò)的效率差值分布函數(shù)Fig.14.Efficiency difference distribution function of the BBV network with every new node connected to the previous 14 nodes.

圖15 新增節(jié)點(diǎn)與之前15個(gè)節(jié)點(diǎn)相連的BBV網(wǎng)絡(luò)的效率差值分布函數(shù)Fig.15.Efficiency difference distribution function of the BBV network with every new node connected to the previous 15 nodes.

其中n為節(jié)點(diǎn)總數(shù),rij為節(jié)點(diǎn)vi到vj的最短路徑.通過從這些網(wǎng)絡(luò)中刪除最重要的節(jié)點(diǎn),分析網(wǎng)絡(luò)效率下降比例.以從網(wǎng)絡(luò)中刪除破壞測(cè)試方法得出的最重要節(jié)點(diǎn)后網(wǎng)絡(luò)效率下降比例為該網(wǎng)絡(luò)的基準(zhǔn)值,用從對(duì)應(yīng)網(wǎng)絡(luò)中刪除其他方法得出的最重要節(jié)點(diǎn)后網(wǎng)絡(luò)效率下降比例減去該網(wǎng)絡(luò)基準(zhǔn)值得出差值,如果該差值為正,則表示其他方法得出的重要節(jié)點(diǎn)優(yōu)于破壞測(cè)試方法.針對(duì)每類BBV網(wǎng)絡(luò)的50個(gè)具體網(wǎng)絡(luò),計(jì)算出每種方法下網(wǎng)絡(luò)效率下降比例與對(duì)應(yīng)基準(zhǔn)值的50個(gè)差值,利用核密度估計(jì)方法估計(jì)這些差值的概率分布函數(shù),進(jìn)而分析對(duì)比破壞測(cè)試方法與其他四種方法的優(yōu)劣.圖9—圖15分別展示了每類BBV網(wǎng)絡(luò)中其他四種方法得到的差值概率分布函數(shù).如果圖中差值為0對(duì)應(yīng)的概率大于0.5,其表示差值小于0的可能性更大,也就是說刪除其他方法得出的最重要節(jié)點(diǎn)時(shí)造成的效率下降值低于刪除破壞測(cè)試方法得出的最重要節(jié)點(diǎn)時(shí)造成的效率下降值的可能性更大,即破壞測(cè)試方法依概率優(yōu)于對(duì)應(yīng)的其他方法.從圖9、圖12、圖13和圖15可以看出,破壞測(cè)試方法優(yōu)于其他四種方法.從圖10和圖11可以看出,破壞測(cè)試方法沒有互信息方法好,與度中心性方法和PageRank方法相當(dāng),比介數(shù)中心性方法好.從圖14可以看出,破壞測(cè)試方法、度中心性方法和PageRank方法相當(dāng),破壞測(cè)試方法要優(yōu)于互信息方法和介數(shù)中心性方法.綜合以上BBV網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果,可以得出破壞測(cè)試方法具有統(tǒng)計(jì)學(xué)意義上的最優(yōu)性,刪除其計(jì)算得出的重要節(jié)點(diǎn)導(dǎo)致網(wǎng)絡(luò)效率下降幅度最大.

在異質(zhì)網(wǎng)絡(luò)破壞測(cè)試方法有效性驗(yàn)證上,本文選擇在4.1節(jié)中建立的異質(zhì)DWS網(wǎng)絡(luò)模型上進(jìn)行實(shí)驗(yàn).通過破壞測(cè)試方法得出的節(jié)點(diǎn)重要性排序如圖16所示,可以看出度高并且級(jí)別高的節(jié)點(diǎn)是比較重要的節(jié)點(diǎn),這與異質(zhì)網(wǎng)絡(luò)上的擾動(dòng)測(cè)試方法得出的結(jié)論相反.圖16中顯示節(jié)點(diǎn)v1比節(jié)點(diǎn)v20重要,并且在實(shí)驗(yàn)建立的DWS網(wǎng)絡(luò)中,節(jié)點(diǎn)v1和節(jié)點(diǎn)v20的度相同.如果提高節(jié)點(diǎn)v20的穩(wěn)定性,設(shè)置其自身動(dòng)力學(xué)模型的可調(diào)參數(shù)為再次進(jìn)行破壞測(cè)試,可以發(fā)現(xiàn)節(jié)點(diǎn)v20比節(jié)點(diǎn)v1重要,具體如圖17所示.由此可見,利用異質(zhì)網(wǎng)絡(luò)破壞測(cè)試方法進(jìn)行節(jié)點(diǎn)重要性評(píng)估,節(jié)點(diǎn)度越大,節(jié)點(diǎn)越重要,同時(shí)在控制度不變的情況下,節(jié)點(diǎn)自身動(dòng)力學(xué)模型越穩(wěn)定,節(jié)點(diǎn)越重要.該結(jié)論與實(shí)際相符,因?yàn)槠茐亩却蟮狞c(diǎn)影響范圍大,所以重要.同時(shí)由于穩(wěn)定性好的點(diǎn)可以更好地促進(jìn)網(wǎng)絡(luò)穩(wěn)定和保持網(wǎng)絡(luò)處于平衡狀態(tài),所以節(jié)點(diǎn)的重要程度與節(jié)點(diǎn)自身動(dòng)力學(xué)模型的穩(wěn)定性正相關(guān).

圖16 破壞測(cè)試條件下的DWS網(wǎng)絡(luò)節(jié)點(diǎn)的重要性排序Fig.16.Rank of important nodes in DWS under destructive test.

圖17 破壞測(cè)試條件下調(diào)整后的DWS網(wǎng)絡(luò)節(jié)點(diǎn)的重要性排序Fig.17.Rank of important nodes in adjusted DWS under destructive test.

5 結(jié) 論

分析復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn)可以幫助我們有針對(duì)性地設(shè)計(jì)防護(hù)策略或者有效控制網(wǎng)絡(luò)上危害的蔓延.現(xiàn)有的復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要性評(píng)估方法中,從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)出發(fā),建立網(wǎng)絡(luò)局部與全局以及節(jié)點(diǎn)位置相關(guān)的評(píng)價(jià)指標(biāo)進(jìn)行節(jié)點(diǎn)重要性評(píng)估的研究比較成熟,但是基于復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)估方法較少,已有的方法多是針對(duì)給定并且滿足特定條件的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型展開的.對(duì)于無向加權(quán)網(wǎng)絡(luò),本文提出了建立其對(duì)應(yīng)動(dòng)力學(xué)模型的方法,并從理論上證明了建立的動(dòng)力學(xué)模型是大范圍一致漸進(jìn)穩(wěn)定的.基于動(dòng)力學(xué)模型,本文進(jìn)一步提出了兩種節(jié)點(diǎn)重要性評(píng)估方法,并揭示了現(xiàn)有的基于拓?fù)浣Y(jié)構(gòu)的和基于動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)估方法結(jié)論的差異源于節(jié)點(diǎn)功能是否被破壞.擾動(dòng)測(cè)試方法是在不破壞節(jié)點(diǎn)功能的情況下,分析對(duì)哪些節(jié)點(diǎn)施加干擾對(duì)網(wǎng)絡(luò)整體平衡狀態(tài)影響最大,從而確定重要節(jié)點(diǎn).實(shí)驗(yàn)表明該方法所得結(jié)論與現(xiàn)有基于動(dòng)力學(xué)模型的節(jié)點(diǎn)重要性評(píng)估方法的結(jié)論一致程度較高,即重要節(jié)點(diǎn)傾向于避免高度節(jié)點(diǎn).破壞測(cè)試方法是節(jié)點(diǎn)受到破壞并且無法恢復(fù)正常時(shí),通過比較破壞節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)整體平衡狀態(tài)造成影響的不同來確定節(jié)點(diǎn)的重要性,實(shí)驗(yàn)表明該方法所得結(jié)論與基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的節(jié)點(diǎn)重要性評(píng)估方法的結(jié)論一致程度較高.特別是對(duì)BBV網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)重要性評(píng)估和以網(wǎng)絡(luò)效率為評(píng)估指標(biāo)時(shí),實(shí)驗(yàn)表明在統(tǒng)計(jì)意義上破壞測(cè)試方法得出的重要節(jié)點(diǎn)比度中心性方法、互信息方法、PageRank方法和介數(shù)中心性方法更為合理和穩(wěn)定.由于擾動(dòng)測(cè)試方法和破壞測(cè)試方法既包含了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息又包含了節(jié)點(diǎn)自身特性,所以本文提出的節(jié)點(diǎn)重要性評(píng)估方法能更加全面地反映不同節(jié)點(diǎn)重要性.同時(shí),本文建立了偏離均值和基于偏離均值的方差兩級(jí)評(píng)估標(biāo)準(zhǔn),對(duì)節(jié)點(diǎn)重要性評(píng)估更為細(xì)致,區(qū)分度好.此外,建立異質(zhì)的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型時(shí),節(jié)點(diǎn)自身動(dòng)力學(xué)模型的可調(diào)參數(shù)可以靈活設(shè)置,可以更好地面向?qū)嶋H問題建立動(dòng)力學(xué)模型和進(jìn)行節(jié)點(diǎn)重要性評(píng)估.

本文只針對(duì)單個(gè)節(jié)點(diǎn)的重要節(jié)點(diǎn)評(píng)估進(jìn)行了研究,進(jìn)一步可以將擾動(dòng)測(cè)試方法和破壞測(cè)試方法用于重要節(jié)點(diǎn)集合的評(píng)估.由于是連續(xù)時(shí)間動(dòng)力學(xué)模型,除衡量測(cè)試開始至系統(tǒng)穩(wěn)定的時(shí)期內(nèi)的偏離均值和基于偏離均值的方差外,還可以分析自測(cè)試開始后每個(gè)時(shí)刻的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型狀態(tài)變化軌線,依據(jù)狀態(tài)變化軌線設(shè)置更合理的與時(shí)間相關(guān)的節(jié)點(diǎn)重要性評(píng)估指標(biāo).為了建立更合理的動(dòng)力學(xué)模型,可以進(jìn)一步結(jié)合信息在不同節(jié)點(diǎn)之間傳遞的延時(shí)效應(yīng),建立具有延時(shí)環(huán)節(jié)的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)模型.同時(shí),針對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)建立更為一般的非線性動(dòng)力學(xué)方程并基于其進(jìn)行節(jié)點(diǎn)重要性評(píng)估,具有重要研究?jī)r(jià)值.這將是我們下一步研究的方向.

參考文獻(xiàn)

[1]Zhao M,Zhou T,Wang B H,Wang W X 2005Phys.Rev.E72 057102

[2]Zemanová L,Zhou C,Kurths J 2006Physica D224 202

[3]Lü L Y,Chen D B,Ren X L,Zhang Q M,Zhang Y C,Zhou T 2016Phys.Rep.650 1

[4]Bonacich P 1972J.Math.Sociol.2 113

[5]Estrada E,Rodríguez-Velázquez J A 2005Phys.Rev.E71 056103

[6]Kitsak M,Gallos L K,Havlin S,Liljeros F,Muchnik L,Stanley H E,Makse H A 2010Nat.Phys.6 888

[7]Lü L Y,Zhou T,Zhang Q M,Stanley H E 2016Nat.Commun.7 10168

[8]Chen D B,Lü L Y,Shang M S,Zhang Y C,Zhou T 2012Physica A391 1777

[9]Ruan Y R,Lao S Y,Wang J D,Bai L,Chen L D 2017Acta Phys.Sin.66 038902(in Chinese)[阮逸潤(rùn),老松楊,王竣德,白亮,陳立棟2017物理學(xué)報(bào)66 038902]

[10]Freeman L C,Borgatti S P,White D R 1991Soc.Networks13 141

[11]Estrada E,Higham D J,Hatano N 2009Physica A388 764

[12]Li Q,Zhou T,Lü L Y,Chen D B 2014Physica A404 47

[13]Zhou Y B,Lei T,Zhou T 2011Europhys.Lett.94 48002

[14]Li P X,Ren Y Q,Xi Y M 2004Systems Eng.22 13(in Chinese)[李鵬翔,任玉晴,席酉民 2004系統(tǒng)工程 22 13]

[15]Gao C,Wei D J,Hu Y,Mahadevan S,Deng Y 2013Physica A392 5490

[16]Wang Y,Guo J L 2017Acta Phys.Sin.66 050201(in Chinese)[王雨,郭進(jìn)利 2017物理學(xué)報(bào) 66 050201]

[17]Lü L,Zhang Y C,Chi H Y,Zhou T 2011Plos One6 e21202

[18]Yan G,Zhou T,Wang J,Fu Z Q,Wang B 2005Chin.Phys.Lett.22 510

[19]Brummitt C D,D’Souza R M,Leicht E A 2012Proceedings of the National Academy of Sciences of the United States of America109 E680

[20]Du W J,Yu J L,An X L,Ma C X 2015Transport Research1 14(in Chinese)[杜文舉,俞建寧,安新磊,馬昌喜2015交通運(yùn)輸研究1 14]

[21]Liu Y Y,Slotine J J,Barabasi A L 2011Nature473 167

[22]Jia T,Barabási A L 2013Sci.Rep.3 2354

[23]Chen T P,Lu W L 2013Theory of Coordination in Complex Networks(Beijing:Higher Education Press)p14(in Chinese)[陳天平,盧文聯(lián)2013復(fù)雜網(wǎng)絡(luò)協(xié)調(diào)性理論(北京:高等教育出版社)第14頁]

[24]Wang E F,Shi S M 2005Advanced Algebra(3rd Ed.)(Beijing:Higher Education Press)p160(in Chinese)[王萼芳,石生明 2005高等代數(shù)第三版 (北京:高等教育出版社)第160頁]

[25]Zhong Q H 2004Modern Control Theory2004(Beijing:Higher Education Press)p142(in Chinese)[鐘秋海2004現(xiàn)代控制理論(北京:高等教育出版社)第142頁]

[26]Liang H L 2015Ph.D.Dissertation(Shanghai:Shanghai Jiao Tong University)(in Chinese)[梁海麗 2015博士學(xué)位論文(上海:上海交通大學(xué))]

[27]Wang B,Ma R N,Wang G,Chen B 2015J.Comput.Appl.35 1820(in Chinese)[王班,馬潤(rùn)年,王剛,陳波2015計(jì)算機(jī)應(yīng)用35 1820]

[28]Brin S,Page L 1998Computer Networks and ISDN Systems30 107

[29]Yao Z Q,Shang K K,Xu X K 2012J.Univ.Shanghai Sci.Technol.34 18(in Chinese)[姚尊強(qiáng),尚可可,許小可2012上海理工大學(xué)學(xué)報(bào)34 18]

[30]Dodds P S,Watts D J,Sabel C F 2003PNAS100 12516

[31]Yuan M 2014Acta Phys.Sin.63 220501(in Chinese)[袁銘2014物理學(xué)報(bào) 63 220501]

[32]Zachary W W 1977J.Anthropol.Res.33 452

[33]Pan Z F,Wang X F 2006Acta Phys.Sin.55 4058(in Chinese)[潘灶烽,汪小帆 2006物理學(xué)報(bào) 55 4058]

[34]Latora V,Marchiori M 2007New J.Phys.9 188