基于冗余度的復(fù)雜網(wǎng)絡(luò)抗毀性及節(jié)點(diǎn)重要度評(píng)估模型

王梓行，姜大立，漆 磊，陳 星,趙禹博

(1.陸軍勤務(wù)學(xué)院 a.軍事物流系；b.基礎(chǔ)部，重慶 401311；2.陸軍裝甲兵學(xué)院士官學(xué)院，長(zhǎng)春 130137)

0 引言

隨著復(fù)雜網(wǎng)絡(luò)研究的逐步深入及其研究方向的不斷拓展，復(fù)雜網(wǎng)絡(luò)理論已經(jīng)更加廣泛地應(yīng)用于當(dāng)今時(shí)代的各個(gè)領(lǐng)域之中。然而，任何領(lǐng)域的復(fù)雜網(wǎng)絡(luò)中均分布著不計(jì)其數(shù)的網(wǎng)絡(luò)節(jié)點(diǎn)，并且節(jié)點(diǎn)與節(jié)點(diǎn)之間可能又具有錯(cuò)綜復(fù)雜的連接關(guān)系，倘若某些“關(guān)鍵節(jié)點(diǎn)”遭受損壞或發(fā)生事故，便可能引起“級(jí)聯(lián)失效”的情況，使得網(wǎng)絡(luò)抗毀性驟降，最終導(dǎo)致網(wǎng)絡(luò)大規(guī)模失效乃至整個(gè)系統(tǒng)面臨癱瘓的狀態(tài)。因此，復(fù)雜網(wǎng)絡(luò)抗毀性的量化及節(jié)點(diǎn)重要度的評(píng)估長(zhǎng)期以來(lái)一直是此方向的研究熱點(diǎn)，它能對(duì)整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化、抗毀性的提高以及網(wǎng)絡(luò)中重要節(jié)點(diǎn)的獲取與防護(hù)提供有效參考和決策支持，對(duì)于保證電網(wǎng)、物流網(wǎng)、通信網(wǎng)等領(lǐng)域網(wǎng)絡(luò)的安全可靠和功能穩(wěn)定性有著重要而深遠(yuǎn)的現(xiàn)實(shí)意義。

在涉及復(fù)雜網(wǎng)絡(luò)抗毀性和節(jié)點(diǎn)重要度問(wèn)題的相關(guān)研究中，從模型構(gòu)建的角度上來(lái)看，現(xiàn)有文獻(xiàn)很少使用概率對(duì)網(wǎng)絡(luò)抗毀性進(jìn)行量化，故不利于各種抗毀性求解方法在求解效果和結(jié)果精度上的相互比較；另外，現(xiàn)有研究多以網(wǎng)絡(luò)中的局部屬性作為節(jié)點(diǎn)重要度的評(píng)價(jià)指標(biāo)，而通過(guò)網(wǎng)絡(luò)全局屬性進(jìn)行重要度評(píng)估的研究不多、成果偏少，且建立的模型大多復(fù)雜程度較高，故對(duì)于規(guī)模較大的復(fù)雜網(wǎng)絡(luò)適用性不強(qiáng)。吳俊等[1]針對(duì)網(wǎng)絡(luò)結(jié)構(gòu)屬性，利用網(wǎng)絡(luò)中所有回路數(shù)的加權(quán)和對(duì)任意兩點(diǎn)間可替代路徑的冗余程度進(jìn)行量化，而后借助特征譜理論對(duì)網(wǎng)絡(luò)的自然連通度進(jìn)行定義，并將其作為譜測(cè)度指標(biāo)對(duì)網(wǎng)絡(luò)抗毀性展開量化；田田等[2]以自然連通度為基礎(chǔ)構(gòu)建了針對(duì)網(wǎng)絡(luò)抗毀性的組合優(yōu)化模型，并利用改進(jìn)的搜索禁忌算法對(duì)抗毀性最優(yōu)的網(wǎng)絡(luò)的拓?fù)鋵傩哉归_分析研究；蔣豐景[3]根據(jù)度分布和網(wǎng)絡(luò)的局部連通性，建立了節(jié)點(diǎn)重要度量化評(píng)估模型，同時(shí)提出了一種以重要度熵為基礎(chǔ)的方法對(duì)網(wǎng)絡(luò)抗毀性展開度量，對(duì)于小規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)重要度和抗毀性的求解具有一定的可行性和有效性；王燦[4]根據(jù)復(fù)雜網(wǎng)絡(luò)理論中對(duì)熵的定義以及圖論中的中心介數(shù)理論，在無(wú)線傳輸領(lǐng)域建立了以介數(shù)熵為基礎(chǔ)的網(wǎng)絡(luò)抗毀性量化求解模型；姚杰[5]基于復(fù)雜網(wǎng)絡(luò)理論對(duì)網(wǎng)絡(luò)中連接度、中心介數(shù)、緊密性和特征向量等重要性評(píng)估指標(biāo)進(jìn)行分析研究，借助層次分析法建立了基于通信網(wǎng)的節(jié)點(diǎn)重要度量化評(píng)估模型。本文在已有成果文獻(xiàn)的基礎(chǔ)上，根據(jù)網(wǎng)絡(luò)中任意兩點(diǎn)間替代路徑的數(shù)量定義了復(fù)雜網(wǎng)絡(luò)的冗余度，同時(shí)基于此用網(wǎng)絡(luò)隨機(jī)失效后保持連通的概率對(duì)其抗毀性進(jìn)行量化，并利用冗余度在網(wǎng)絡(luò)中的全局屬性對(duì)節(jié)點(diǎn)重要度進(jìn)行評(píng)估，最終建立起基于冗余度的復(fù)雜網(wǎng)絡(luò)抗毀性及節(jié)點(diǎn)重要度評(píng)估模型，為大規(guī)模網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的防護(hù)以及復(fù)雜網(wǎng)絡(luò)抗毀性的優(yōu)化提高提供參考模型和決策依據(jù)。

在求解算法方面，現(xiàn)有研究大多難以解決求解精度與耗時(shí)長(zhǎng)度之間的矛盾：若以網(wǎng)絡(luò)局部屬性的相關(guān)算法對(duì)節(jié)點(diǎn)重要度進(jìn)行評(píng)估，則大都難以取得排序一致且精度較高的解；若以網(wǎng)絡(luò)全局屬性設(shè)計(jì)算法量化節(jié)點(diǎn)重要度，則大多會(huì)導(dǎo)致其時(shí)間復(fù)雜度較高，在評(píng)估復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度上缺乏一定的時(shí)效性。譚躍進(jìn)等[6]通過(guò)節(jié)點(diǎn)度和平均路徑長(zhǎng)度的結(jié)合，對(duì)網(wǎng)絡(luò)的局部和全局屬性進(jìn)行綜合性考慮，以凝聚度為基礎(chǔ)設(shè)計(jì)出了節(jié)點(diǎn)收縮法，從而量化評(píng)估復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要性，并獲得了理想的運(yùn)算效率；劉媛妮[7]基于中心介數(shù)理論和重要度熵設(shè)計(jì)出一種網(wǎng)絡(luò)抗毀性量化算法，并通過(guò)節(jié)點(diǎn)受損后網(wǎng)絡(luò)中抗毀性的變化程度來(lái)對(duì)節(jié)點(diǎn)的重要度進(jìn)行衡量；陳靜等[8]借助節(jié)點(diǎn)關(guān)鍵度理論及網(wǎng)絡(luò)節(jié)點(diǎn)接近度的概念設(shè)計(jì)出一種方法以評(píng)估各個(gè)節(jié)點(diǎn)的重要度，在對(duì)網(wǎng)絡(luò)的局部和全局屬性展開綜合考慮的前提下，提出了針對(duì)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性的量化評(píng)估手段，并且取得了可接受的時(shí)間復(fù)雜度；張喜平等[9]根據(jù)鄰居節(jié)點(diǎn)理論，以m階鄰居節(jié)點(diǎn)的重要度貢獻(xiàn)為基礎(chǔ)，提出一種精確性較高的方法對(duì)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性展開評(píng)估，同時(shí)顯著區(qū)分了復(fù)雜網(wǎng)絡(luò)中不同節(jié)點(diǎn)之間的差異程度；阮逸潤(rùn)等[10]從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)出發(fā)，基于網(wǎng)絡(luò)中節(jié)點(diǎn)的局部重合程度對(duì)節(jié)點(diǎn)相似性進(jìn)行定義，并由此設(shè)計(jì)出一種將鄰接拓?fù)渲睾隙群投确植枷嘟Y(jié)合的節(jié)點(diǎn)重要度評(píng)估方法；宋琛等[11]以隨機(jī)游走技術(shù)為基礎(chǔ)設(shè)計(jì)出一種優(yōu)化疊加算法的節(jié)點(diǎn)重要性量化評(píng)估手段，有效解決了當(dāng)前評(píng)估方法中普遍存在的重要度排序結(jié)果精確度不高的問(wèn)題。針對(duì)文獻(xiàn)分析，本文擬利用網(wǎng)絡(luò)冗余度的全局屬性，通過(guò)節(jié)點(diǎn)刪除的方法對(duì)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的重要度進(jìn)行評(píng)估，為有效處理求解精度與算法復(fù)雜度之間的矛盾提供參考。

1 模型的準(zhǔn)備

1.1 問(wèn)題提出

在當(dāng)今社會(huì)中復(fù)雜網(wǎng)絡(luò)幾乎隨處可見，其理論對(duì)于各個(gè)領(lǐng)域均有極其重要的運(yùn)用價(jià)值。然而，一旦網(wǎng)絡(luò)中部分關(guān)鍵節(jié)點(diǎn)受損或失效，輕則造成網(wǎng)絡(luò)連通性的下降，重則可能導(dǎo)致整個(gè)網(wǎng)絡(luò)陷入癱瘓的狀態(tài)。因此，對(duì)于復(fù)雜網(wǎng)絡(luò)抗毀性及其節(jié)點(diǎn)重要度的評(píng)估具有重要而深遠(yuǎn)的現(xiàn)實(shí)意義。

本文從拓?fù)浣Y(jié)構(gòu)的角度出發(fā)，將復(fù)雜網(wǎng)絡(luò)視為一個(gè)包含n個(gè)點(diǎn)、m條邊的無(wú)向無(wú)權(quán)圖G=(V,E)。其中，V={v1,v2,…，vn}為圖G的非空節(jié)點(diǎn)集，E={e1,e2,…，em}?V×V為圖G的非空邊集。則圖G可通過(guò)鄰接矩陣A(G)=(aij)n×n進(jìn)行簡(jiǎn)化表示，其中，vi與vj相連通則取aij=1，不連通則取aij=0，此外，該鄰接矩陣A(G)中的aii=0且aij=aji。要求根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其節(jié)點(diǎn)連接情況，建立一個(gè)普適性的數(shù)學(xué)模型，從而量化出復(fù)雜網(wǎng)絡(luò)的抗毀性，同時(shí)對(duì)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的重要度進(jìn)行評(píng)估。

1.2 模型假設(shè)

1)各個(gè)領(lǐng)域的網(wǎng)絡(luò)均存在復(fù)雜度上限，且復(fù)雜度最大的網(wǎng)絡(luò)是一個(gè)節(jié)點(diǎn)數(shù)確定的完全圖。

2)節(jié)點(diǎn)在網(wǎng)絡(luò)中有且僅有兩種狀態(tài)——失效和正常，且節(jié)點(diǎn)失效是相互獨(dú)立的。

3)節(jié)點(diǎn)失效后原來(lái)與其相連的邊也將失效。

4)將冗余度作為唯一的評(píng)價(jià)指標(biāo)對(duì)復(fù)雜網(wǎng)絡(luò)的抗毀性進(jìn)行研究，不考慮其它因素的影響。

1.3 符號(hào)說(shuō)明

對(duì)該模型所用到的符號(hào)進(jìn)行說(shuō)明(見表1)。

表1 符號(hào)類型及含義Tab.1 Symbol types and meanings

2 模型的構(gòu)建

2.1 復(fù)雜網(wǎng)絡(luò)冗余度

復(fù)雜網(wǎng)絡(luò)的抗毀性在狹義上可定義為：邊或點(diǎn)遭遇事故隨機(jī)失效以后網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)還能保持連通的概率[12]。因此，著眼于拓?fù)浣Y(jié)構(gòu)的角度展開分析，網(wǎng)絡(luò)抗毀性可以由任意兩節(jié)點(diǎn)間保持鄰接關(guān)系的通路數(shù)目來(lái)衡量。或者說(shuō)，復(fù)雜網(wǎng)絡(luò)抗毀性可以由網(wǎng)絡(luò)中任意節(jié)點(diǎn)間部分連通路徑失效后剩余的替代路徑數(shù)目進(jìn)行表征。然而，對(duì)于復(fù)雜網(wǎng)絡(luò)中任意節(jié)點(diǎn)間替代路徑數(shù)目的求解往往難以實(shí)現(xiàn)，一方面是網(wǎng)絡(luò)節(jié)點(diǎn)間的替代路徑數(shù)目統(tǒng)計(jì)難度較大，另一方面則是隨著網(wǎng)絡(luò)規(guī)模的逐步增大，對(duì)復(fù)雜網(wǎng)絡(luò)中替代路徑數(shù)目的求解可能會(huì)形成NP問(wèn)題[13]。故本文考慮使用復(fù)雜網(wǎng)絡(luò)中的所有閉合回路數(shù)來(lái)對(duì)任意節(jié)點(diǎn)間替代路徑數(shù)的累加和進(jìn)行簡(jiǎn)化表征[14]，可認(rèn)為網(wǎng)絡(luò)中的閉合回路數(shù)越多，網(wǎng)絡(luò)節(jié)點(diǎn)間的替代路徑數(shù)量就越多，其抗毀性也就越高。

網(wǎng)絡(luò)閉合回路數(shù)是圖論中網(wǎng)絡(luò)的基本屬性之一，可與網(wǎng)絡(luò)子圖一一對(duì)應(yīng)。在含有n個(gè)點(diǎn)，m條邊的無(wú)向無(wú)權(quán)圖G=(V,E)中，由于其鄰接矩陣A(G)=(aij)n×n是實(shí)對(duì)稱矩陣，故根據(jù)矩陣?yán)碚摽芍?，該鄰接矩陣A(G)有n個(gè)實(shí)特征值λi，其中，i=1,2,…,n。這里不妨假設(shè)λ1≥λ2≥…≥λn，因此，根據(jù)鄰接矩陣的特征值，可以得出網(wǎng)絡(luò)的譜密度ρ(λ)，即

(1)

式(1)中：δ(λ)為單位沖激函數(shù)，λ=0時(shí)δ(λ)=1，λ≠0時(shí)δ(λ)=0。

由此可知ρ(λ)是一種譜密度，因?yàn)闈M足

(2)

顯然，當(dāng)n→∞時(shí)，ρ(λ)逼近一個(gè)連續(xù)函數(shù)。進(jìn)一步，根據(jù)圖論和矩陣特征值理論，可以得出

(3)

(4)

式(4)表示網(wǎng)絡(luò)G中包含的所有有序閉合回路數(shù)可由網(wǎng)絡(luò)所有階次的鄰接矩陣的跡之和進(jìn)行度量。其中，tr((A)k)指k次鄰接矩陣的跡，λi指網(wǎng)絡(luò)G的鄰接矩陣A(G)的第i個(gè)特征值。

(5)

式(5)表示，根據(jù)泰勒公式，網(wǎng)絡(luò)中包含的所有無(wú)序閉合回路數(shù)可由網(wǎng)絡(luò)鄰接矩陣所有特征值的自然指數(shù)和進(jìn)行度量。此外，為實(shí)現(xiàn)數(shù)量級(jí)的統(tǒng)一同時(shí)保證L′處于收斂狀態(tài)，基于式(5)進(jìn)行處理，從而定義了復(fù)雜網(wǎng)絡(luò)冗余度

(6)

其中，λi為網(wǎng)絡(luò)G的鄰接矩陣A(G)的第i個(gè)特征值。

2.2 基于冗余度的復(fù)雜網(wǎng)絡(luò)抗毀性及節(jié)點(diǎn)重要度

在節(jié)點(diǎn)數(shù)目一定的情況下，基于增刪邊的網(wǎng)絡(luò)冗余度變化是嚴(yán)格單調(diào)的[16]。因此，網(wǎng)絡(luò)規(guī)模確定的無(wú)向圖中，完全圖的冗余度最大，網(wǎng)絡(luò)抗毀性最優(yōu)。此外，將式(6)通過(guò)Matlab2012b進(jìn)行測(cè)試后，發(fā)現(xiàn)完全圖基于節(jié)點(diǎn)數(shù)目的網(wǎng)絡(luò)冗余度亦是單調(diào)的(見圖1)。

圖1 完全圖冗余度隨網(wǎng)絡(luò)規(guī)模擴(kuò)大的變化情況示意Fig.1 The change of complete graph redundancy as the network scale expands

然而，在實(shí)際情況下，任何領(lǐng)域的網(wǎng)絡(luò)構(gòu)建都會(huì)受到一定成本的約束，因此導(dǎo)致了各個(gè)領(lǐng)域的網(wǎng)絡(luò)都會(huì)有網(wǎng)絡(luò)復(fù)雜度的限制[17]。故根據(jù)不同領(lǐng)域的網(wǎng)絡(luò)性質(zhì)及約束成本，可確定其所能構(gòu)建完全圖網(wǎng)絡(luò)的最大規(guī)模，即完全圖的最大節(jié)點(diǎn)數(shù)——在對(duì)模型進(jìn)行仿真求解時(shí)輸入其最大節(jié)點(diǎn)數(shù)，進(jìn)而可界定出該領(lǐng)域的網(wǎng)絡(luò)冗余度上限值。

(7)

式(7)表示網(wǎng)絡(luò)冗余度的上限值，其中，Nm指規(guī)模最大的完全圖網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，即此領(lǐng)域中所能構(gòu)建完全圖網(wǎng)絡(luò)的最大規(guī)模。

綜上，根據(jù)復(fù)雜網(wǎng)絡(luò)抗毀性的定義，基于冗余度的性質(zhì)利用網(wǎng)絡(luò)隨機(jī)失效后保持連通的概率對(duì)其抗毀性進(jìn)行量化

(8)

其中，R為任一領(lǐng)域的復(fù)雜網(wǎng)絡(luò)冗余度。

以上述模型為理論基礎(chǔ)，基于網(wǎng)絡(luò)冗余度的全局屬性，通過(guò)節(jié)點(diǎn)刪除的方法對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的重要度進(jìn)行評(píng)估。

當(dāng)M=3，N=5時(shí)，文獻(xiàn)[9]和文獻(xiàn)[13]的自由度為16，本文算法的自由度為25.為了驗(yàn)證三種算法的檢測(cè)能力，設(shè)置仿真條件：信噪比為10dB，快拍數(shù)K=500，信號(hào)源數(shù)D=13，來(lái)波方向均勻分布在-60°～60°范圍內(nèi)，三種算法的歸一化DOA檢測(cè)空間譜如圖 5所示.為了驗(yàn)證算法的陣列自由度，同時(shí)仿真了信源數(shù)增加到20時(shí)本文算法的歸一化DOA檢測(cè)空間譜，仿真結(jié)果如圖 6所示.

(9)

式(9)表示網(wǎng)絡(luò)G中節(jié)點(diǎn)vdel的重要度，可用網(wǎng)絡(luò)G的初始冗余度與刪除節(jié)點(diǎn)vdel后新網(wǎng)絡(luò)G′的冗余度之差再與初始冗余度相除進(jìn)行表示。其中，P0為網(wǎng)絡(luò)G的初始抗毀性，Pdel為刪除節(jié)點(diǎn)vdel后新網(wǎng)絡(luò)G′的抗毀性，R0為網(wǎng)絡(luò)G的初始冗余度，Rdel為刪除節(jié)點(diǎn)vdel后新網(wǎng)絡(luò)G′的冗余度。

3 模型的求解

3.1 求解思路

首先，將待求網(wǎng)絡(luò)表示成鄰接矩陣的形式代入模型，并根據(jù)網(wǎng)絡(luò)所屬的具體領(lǐng)域明確其完全圖的最大節(jié)點(diǎn)數(shù)；其次，分別求解出原網(wǎng)絡(luò)和最大完全圖網(wǎng)絡(luò)鄰接矩陣的全部特征值，同時(shí)根據(jù)復(fù)雜網(wǎng)絡(luò)冗余度的定義計(jì)算出網(wǎng)絡(luò)的初始冗余度和冗余度上限值；然后基于冗余度用網(wǎng)絡(luò)隨機(jī)失效后保持連通的概率對(duì)其抗毀性進(jìn)行量化并輸出；最后利用冗余度的全局屬性，通過(guò)網(wǎng)絡(luò)初始冗余度與刪除節(jié)點(diǎn)后新網(wǎng)絡(luò)冗余度之差與初始冗余度的比值對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的重要度進(jìn)行評(píng)估。模型求解思路示意如圖2所示。

圖2 模型求解思路示意Fig.2 Model solution steps

3.2 算法流程及其復(fù)雜性分析

步驟1 輸入待求網(wǎng)絡(luò)的鄰接矩陣A(G)，以及網(wǎng)絡(luò)所屬領(lǐng)域完全圖的最大節(jié)點(diǎn)數(shù)Nm；

步驟2 計(jì)算網(wǎng)絡(luò)初始冗余度R0和最大冗余度Rm；

步驟3 計(jì)算并輸出網(wǎng)絡(luò)抗毀性P；

步驟4 在原網(wǎng)絡(luò)中刪除節(jié)點(diǎn)vdel，并計(jì)算新網(wǎng)絡(luò)的冗余度Rdel；

步驟5 計(jì)算并輸出節(jié)點(diǎn)重要度Idel；

步驟6 重復(fù)Step4至Step5，直至窮盡網(wǎng)絡(luò)的全部節(jié)點(diǎn)。

表2 網(wǎng)絡(luò)抗毀性指標(biāo)的計(jì)算復(fù)雜度對(duì)比Tab.2 Comparison of computational complexity about network invulnerability indicators

由于網(wǎng)絡(luò)冗余度可直接通過(guò)其鄰接矩陣的特征譜直接導(dǎo)出，數(shù)學(xué)形式簡(jiǎn)潔且物理意義明確，具有良好的計(jì)算效果；另外，網(wǎng)絡(luò)冗余度能夠表征網(wǎng)絡(luò)中任意節(jié)點(diǎn)間部分連通路徑失效后剩余的替代路徑數(shù)目，在結(jié)合節(jié)點(diǎn)刪除法后能更精確地刻畫出復(fù)雜網(wǎng)絡(luò)抗毀性的細(xì)微變化，故此模型算法能有效處理求解精度與算法復(fù)雜度之間的矛盾。

4 仿真算例

4.1 問(wèn)題描述

目前，復(fù)雜網(wǎng)絡(luò)正越來(lái)越廣泛地運(yùn)用于社會(huì)的各個(gè)領(lǐng)域，其指標(biāo)的研究對(duì)于各領(lǐng)域的發(fā)展也具有越來(lái)越深遠(yuǎn)的現(xiàn)實(shí)意義和重大的應(yīng)用價(jià)值?，F(xiàn)針對(duì)爵士音樂(lè)家合作網(wǎng)絡(luò)(Jazz)、線蟲新陳代謝網(wǎng)絡(luò)(Metabolic)兩個(gè)不同類型和規(guī)模的真實(shí)復(fù)雜網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)分析處理[18]，要求分別對(duì)各自的網(wǎng)絡(luò)抗毀性以及節(jié)點(diǎn)重要度進(jìn)行量化求解，同時(shí)分別得出各自網(wǎng)絡(luò)中重要度排名前十的節(jié)點(diǎn)序列。

4.2 問(wèn)題求解

首先，根據(jù)Jazz和Metabolic兩個(gè)真實(shí)網(wǎng)絡(luò)的數(shù)據(jù)集進(jìn)行數(shù)據(jù)處理分析，分別將其轉(zhuǎn)化為對(duì)應(yīng)的鄰接矩陣；其次，通過(guò)實(shí)際調(diào)研和專家評(píng)價(jià)的方式對(duì)這兩個(gè)復(fù)雜網(wǎng)絡(luò)所處領(lǐng)域的完全圖最大節(jié)點(diǎn)數(shù)進(jìn)行界定——分別為200和500；而后分別將各自網(wǎng)絡(luò)的鄰接矩陣及其完全圖最大節(jié)點(diǎn)數(shù)代入基于冗余度的復(fù)雜網(wǎng)絡(luò)抗毀性及節(jié)點(diǎn)重要度評(píng)估模型，根據(jù)上述算法步驟，借助Matlab2012b進(jìn)行仿真分析，最終得到各自網(wǎng)絡(luò)的抗毀性及其節(jié)點(diǎn)重要度排序(如表3、4所示)。

表3 Jazz、Metabolic網(wǎng)絡(luò)的抗毀性對(duì)比Tab.3 Comparison of invulnerability in Jazz and Metabolic networks

4.3 結(jié)果分析

由表3可以看出，在各領(lǐng)域網(wǎng)絡(luò)最大復(fù)雜度確定的情況下，Jazz網(wǎng)絡(luò)的抗毀性較好。因此，對(duì)于一定約束成本限制下高抗毀性網(wǎng)絡(luò)的構(gòu)造問(wèn)題，Jazz網(wǎng)絡(luò)能夠作為一種較好的參考模板供研究者進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化，進(jìn)而得到抗毀性最優(yōu)的復(fù)雜網(wǎng)絡(luò)。

為驗(yàn)證本文方法能對(duì)節(jié)點(diǎn)重要度評(píng)估中求解精度與耗時(shí)長(zhǎng)度之間的矛盾進(jìn)行有效解決，參考相關(guān)文獻(xiàn)[19-22]，在Matlab語(yǔ)言環(huán)境下分別利用本文方法、基于最短路的接近度方法、基于信息的中心化方法以及節(jié)點(diǎn)收縮方法對(duì)Jazz和Metabolic網(wǎng)絡(luò)的節(jié)點(diǎn)重要度進(jìn)行評(píng)估，同時(shí)利用基于生物學(xué)的經(jīng)典病毒傳播模型(SI模型)針對(duì)兩個(gè)網(wǎng)絡(luò)分別進(jìn)行節(jié)點(diǎn)實(shí)際傳播效果仿真，得出各種方法的節(jié)點(diǎn)重要度評(píng)估結(jié)果及其節(jié)點(diǎn)實(shí)際傳播能力，從而對(duì)不同方法的有效性進(jìn)行判斷，兩個(gè)網(wǎng)絡(luò)中不同方法評(píng)估結(jié)果與節(jié)點(diǎn)實(shí)際傳播效果關(guān)系如圖3所示。

表4 Jazz、Metabolic網(wǎng)絡(luò)的節(jié)點(diǎn)重要度排序Tab.4 Node importance ranking in Jazz and Metabolic networks

圖3 不同方法評(píng)估結(jié)果與節(jié)點(diǎn)實(shí)際傳播效果關(guān)系Fig.3 Relationship between evaluation results of different methods and actual propagation effect of nodes

為了對(duì)各種評(píng)估方法的有效性進(jìn)行量化和對(duì)比分析，借助Kendall系數(shù)(τ)對(duì)不同方法評(píng)估結(jié)果與節(jié)點(diǎn)實(shí)際傳播能力值之間的相關(guān)程度進(jìn)行度量，得到不同方法評(píng)估結(jié)果與節(jié)點(diǎn)實(shí)際傳播效果的Kendall系數(shù)如表5所示。此外，為驗(yàn)證方法的時(shí)效性，本文將此方法在不同規(guī)模的ER網(wǎng)絡(luò)中進(jìn)行模擬仿真，得到其運(yùn)行時(shí)間隨節(jié)點(diǎn)數(shù)目上升的變化情況如圖4所示。

表5 不同方法評(píng)估結(jié)果與節(jié)點(diǎn)實(shí)際傳播效果的Kendall系數(shù)Tab.5 Kendall coefficients of evaluation results of different methods and actual propagation effect of nodes

圖4 本方法在ER網(wǎng)絡(luò)中運(yùn)行時(shí)間隨節(jié)點(diǎn)數(shù)目上升的變化情況Fig.4 Running time for the ER network vs number of nodes

在圖3中可以直觀地看出，本文方法相較于其它重要度評(píng)估方法而言，無(wú)論針對(duì)Jazz網(wǎng)絡(luò)還是Metabolic網(wǎng)絡(luò)均更具有效性。根據(jù)圖3中的b、c和f、g可以看出，基于最短路的接近度方法、基于信息的中心化方法均存在相似節(jié)點(diǎn)間實(shí)際傳播能力值差異偏大的現(xiàn)象，故其在各自網(wǎng)絡(luò)中所對(duì)應(yīng)的散點(diǎn)圖皆不隨評(píng)估結(jié)果單調(diào)遞增且最終呈現(xiàn)出發(fā)散的趨勢(shì)；根據(jù)圖3中的d和h可以看出，節(jié)點(diǎn)收縮方法針對(duì)Jazz網(wǎng)絡(luò)的有效性和可靠性不高，因此其散點(diǎn)圖d中點(diǎn)分布較為分散且無(wú)法形成線性的趨勢(shì)，而針對(duì)Metabolic網(wǎng)絡(luò)而言，節(jié)點(diǎn)收縮方法無(wú)法對(duì)節(jié)點(diǎn)重要度進(jìn)行細(xì)粒度區(qū)分，故其散點(diǎn)圖h中相同橫坐標(biāo)值對(duì)應(yīng)的實(shí)際傳播能力值不唯一；而根據(jù)圖3中的a和e則能看出，在不同類型的網(wǎng)絡(luò)中，本文方法所對(duì)應(yīng)的散點(diǎn)圖隨評(píng)估結(jié)果近似呈線性和單調(diào)遞增的趨勢(shì)且最終收斂于實(shí)際傳播能力的飽和值，故在節(jié)點(diǎn)重要度的有效評(píng)估上較其它方法具有一定的先進(jìn)性。

表5表示在兩個(gè)網(wǎng)絡(luò)中各種方法評(píng)估結(jié)果與節(jié)點(diǎn)實(shí)際傳播效果之間的相關(guān)性，其中，R、Cc、Cv、Nc、SI分別指本文基于冗余度的方法、基于最短路的接近度方法、基于信息的中心化方法、節(jié)點(diǎn)收縮方法、基于生物學(xué)的經(jīng)典病毒傳播模型。根據(jù)表5可以看出，對(duì)于不同類型的復(fù)雜網(wǎng)絡(luò)而言，本文方法和基于最短路的接近度方法、基于信息的中心化方法以及節(jié)點(diǎn)收縮方法3種計(jì)算精度較高的全局性算法相比，與節(jié)點(diǎn)實(shí)際傳播能力值之間的一致程度最高，故說(shuō)明本文方法在網(wǎng)絡(luò)的節(jié)點(diǎn)重要度評(píng)估方面具有一定優(yōu)越性，能夠作為一種新的精度較高的重要度評(píng)估手段為網(wǎng)絡(luò)中重要節(jié)點(diǎn)的獲取與防護(hù)提供參考。

由圖4可以看出，隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的上升算法運(yùn)行時(shí)間將不可避免地處于持續(xù)上升的狀態(tài)，但在相應(yīng)領(lǐng)域網(wǎng)絡(luò)最大節(jié)點(diǎn)數(shù)的限制范圍內(nèi)此運(yùn)行時(shí)間仍是可接受的[23]，因此，在同一類型不同規(guī)模的復(fù)雜網(wǎng)絡(luò)中，本文方法仍能保持一定的可行性和時(shí)效性。故本文模型算法對(duì)于各種類型的較大規(guī)模網(wǎng)絡(luò)中節(jié)點(diǎn)重要度的評(píng)估具備必要的有效性和可行性。

5 結(jié)語(yǔ)

本文從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的角度出發(fā)，針對(duì)復(fù)雜網(wǎng)絡(luò)抗毀性及節(jié)點(diǎn)重要度評(píng)估問(wèn)題進(jìn)行了綜合性研究。模型方面，定義了復(fù)雜網(wǎng)絡(luò)的冗余度，同時(shí)基于此用網(wǎng)絡(luò)隨機(jī)失效后保持連通的概率對(duì)其抗毀性進(jìn)行量化，并利用冗余度的網(wǎng)絡(luò)全局性對(duì)節(jié)點(diǎn)重要度進(jìn)行評(píng)估，最終建立起基于冗余度的復(fù)雜網(wǎng)絡(luò)抗毀性及節(jié)點(diǎn)重要度評(píng)估模型，為復(fù)雜網(wǎng)絡(luò)抗毀性的提高以及重要節(jié)點(diǎn)的防護(hù)提供參考模型和決策依據(jù)。算法方面，利用網(wǎng)絡(luò)冗余度的全局屬性，通過(guò)節(jié)點(diǎn)刪除的方法對(duì)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的重要度進(jìn)行評(píng)估，從而為解決求解精度與算法復(fù)雜度之間的矛盾提供參考。算例方面，利用Jazz和Metabolic兩個(gè)真實(shí)網(wǎng)絡(luò)進(jìn)行仿真求解，結(jié)果表明該模型算法能為一定約束成本限制下高抗毀性網(wǎng)絡(luò)的構(gòu)造問(wèn)題提供解決方案，同時(shí)對(duì)于各種類型的較大規(guī)模網(wǎng)絡(luò)中節(jié)點(diǎn)重要度的評(píng)估具有一定的有效性和優(yōu)越性。不足方面，在網(wǎng)絡(luò)抗毀性度量中對(duì)完全圖最大節(jié)點(diǎn)數(shù)的界定上缺乏必要的客觀性和理論性，下一步將重點(diǎn)針對(duì)不同領(lǐng)域中受成本約束下完全圖網(wǎng)絡(luò)規(guī)模上限的量化求解問(wèn)題進(jìn)行定量化分析和模型化研究。