付 凱，夏靖波，趙小歡

(1.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安710077； 2. 95246部隊(duì)，南寧530003； 3.廈門大學(xué) 嘉庚學(xué)院，福建 漳州363105； 4. 95340部隊(duì)，廣西 百色 533616)

動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估方法

付 凱1,2，夏靖波3，趙小歡4

(1.空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安710077； 2. 95246部隊(duì)，南寧530003； 3.廈門大學(xué) 嘉庚學(xué)院，福建 漳州363105； 4. 95340部隊(duì)，廣西 百色 533616)

為挖掘復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)及提高網(wǎng)絡(luò)魯棒性，針對(duì)有/無線多網(wǎng)融合的層級(jí)網(wǎng)絡(luò)，提出了動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)模型及其節(jié)點(diǎn)重要度評(píng)估方法.結(jié)合動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)的特點(diǎn)，定義了邊連通概率、路徑連通概率、網(wǎng)絡(luò)連通概率、融合節(jié)點(diǎn)比例、融合節(jié)點(diǎn)分布和融合路徑比例等與網(wǎng)絡(luò)動(dòng)態(tài)性和融合性相關(guān)的參數(shù).在單層復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估指標(biāo)的基礎(chǔ)上，設(shè)計(jì)了融合網(wǎng)絡(luò)節(jié)點(diǎn)度中心性、節(jié)點(diǎn)介數(shù)中心性和節(jié)點(diǎn)融合中心性指標(biāo).其中，融合節(jié)點(diǎn)的節(jié)點(diǎn)融合中心性表示融合節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)融合的貢獻(xiàn)程度，非融合節(jié)點(diǎn)的節(jié)點(diǎn)融合中心性表示非融合節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)融合的輔助作用程度，主要體現(xiàn)在作為融合節(jié)點(diǎn)之間的中繼節(jié)點(diǎn).最后，綜合考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、動(dòng)態(tài)融合特性等因素進(jìn)行節(jié)點(diǎn)重要度評(píng)估.以改進(jìn)的動(dòng)態(tài)交織風(fēng)箏網(wǎng)絡(luò)為例進(jìn)行仿真分析，結(jié)果表明該方法能夠比較全面地刻畫節(jié)點(diǎn)在動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)中的重要性.利用NS2搭建由光通信網(wǎng)和衛(wèi)星通信網(wǎng)融合構(gòu)成的仿真實(shí)驗(yàn)網(wǎng)絡(luò)，進(jìn)一步驗(yàn)證了在仿真網(wǎng)絡(luò)環(huán)境中本方法的有效性.

復(fù)雜網(wǎng)絡(luò)；動(dòng)態(tài)融合；節(jié)點(diǎn)重要度；度中心性；介數(shù)中心性；融合中心性

復(fù)雜網(wǎng)絡(luò)小世界效應(yīng)[1]和無標(biāo)度特性[2]的發(fā)現(xiàn)，掀起了國(guó)內(nèi)外研究復(fù)雜網(wǎng)絡(luò)的熱潮.隨著網(wǎng)絡(luò)科學(xué)[3-4]的蓬勃發(fā)展，節(jié)點(diǎn)重要度評(píng)估進(jìn)一步受到研究人員的關(guān)注，尋找復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)成為網(wǎng)絡(luò)科學(xué)的重要研究?jī)?nèi)容.目前，節(jié)點(diǎn)重要度評(píng)估方法主要包括基于網(wǎng)絡(luò)結(jié)構(gòu)的方法和基于傳播動(dòng)力學(xué)的方法[5].度中心性、介數(shù)中心性[6]、特征向量中心性[7]等是典型的基于網(wǎng)絡(luò)結(jié)構(gòu)的評(píng)估指標(biāo)，其依據(jù)是網(wǎng)絡(luò)局部或全局屬性信息.基于傳播動(dòng)力學(xué)的方法通過計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)的影響范圍來衡量其重要度，如社會(huì)網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的挖掘[8-9].上述評(píng)估指標(biāo)主要針對(duì)單層復(fù)雜網(wǎng)絡(luò)，隨著研究的深入和應(yīng)用的拓展，多種層級(jí)復(fù)雜網(wǎng)絡(luò)模型[10]被相繼提出.相互依存網(wǎng)絡(luò)[11]描述了具有相互影響和依賴關(guān)系的網(wǎng)絡(luò)模型，對(duì)于預(yù)防和控制復(fù)雜系統(tǒng)中的相繼故障具有重要意義，如電力-計(jì)算機(jī)網(wǎng)等.陳宏斌等[12]提出了二元隨機(jī)網(wǎng)的概念，它是一種特殊的二元網(wǎng)，不考慮同類節(jié)點(diǎn)之間的相互作用，如圖書借閱網(wǎng)絡(luò)等.邵峰晶等[13]提出多子網(wǎng)復(fù)合網(wǎng)絡(luò)模型，通過網(wǎng)絡(luò)加載和拆分等網(wǎng)絡(luò)運(yùn)算進(jìn)行網(wǎng)絡(luò)的復(fù)合與分解，實(shí)現(xiàn)復(fù)雜網(wǎng)絡(luò)中同一子網(wǎng)元素間、不同子網(wǎng)元素間以及不同子網(wǎng)之間的相互關(guān)系等形式描述.超網(wǎng)絡(luò)[14]是一種“高于而又超于現(xiàn)存網(wǎng)絡(luò)”的網(wǎng)絡(luò)，用以描述規(guī)模巨大、連接復(fù)雜、具有嵌套網(wǎng)絡(luò)的大型復(fù)雜網(wǎng)絡(luò)，如供應(yīng)鏈網(wǎng)絡(luò)等.以上層級(jí)復(fù)雜網(wǎng)絡(luò)側(cè)重不同子網(wǎng)之間的相互關(guān)系，而對(duì)于網(wǎng)絡(luò)模型中的節(jié)點(diǎn)重要性未做深入研究.沈迪等[15]提出一種交織型層級(jí)復(fù)雜網(wǎng)，描述由兩個(gè)具有部分相同節(jié)點(diǎn)、連接邊屬性近似的子網(wǎng)構(gòu)成的層級(jí)復(fù)雜網(wǎng)絡(luò)，并且定義了相關(guān)測(cè)度用于衡量子網(wǎng)之間的密切程度及節(jié)點(diǎn)中心性，但只適用于靜態(tài)網(wǎng)絡(luò).而節(jié)點(diǎn)重要度評(píng)估問題已逐漸向動(dòng)態(tài)變化的時(shí)變網(wǎng)絡(luò)延伸，在拓?fù)浣Y(jié)構(gòu)變化的網(wǎng)絡(luò)中發(fā)現(xiàn)關(guān)鍵節(jié)點(diǎn)更具有挑戰(zhàn)性[16]. Basaras等[17]在介數(shù)和K-SHELL基礎(chǔ)上提出了動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法，基于局部信息從而降低計(jì)算開銷，更加適合動(dòng)態(tài)網(wǎng)絡(luò)中應(yīng)用. Masaki[18]以動(dòng)態(tài)變化的社會(huì)網(wǎng)絡(luò)為背景，提出了加權(quán)動(dòng)態(tài)復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)重要度評(píng)估方法.

隨著對(duì)網(wǎng)絡(luò)應(yīng)用的需求不斷增強(qiáng)，多網(wǎng)系融合、有/無線并用成為未來網(wǎng)絡(luò)的發(fā)展趨勢(shì).例如，手機(jī)、平板電腦等移動(dòng)網(wǎng)絡(luò)終端通過無線路由器實(shí)現(xiàn)對(duì)互聯(lián)網(wǎng)的接入，就構(gòu)成了有線的寬帶互聯(lián)網(wǎng)與無線的手機(jī)通信網(wǎng)之間的融合互聯(lián)，而且網(wǎng)絡(luò)帶寬、信號(hào)強(qiáng)度等使得有線和無線信道的通信質(zhì)量存在差異.為了在這種融合網(wǎng)絡(luò)中發(fā)現(xiàn)關(guān)鍵節(jié)點(diǎn)、優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)等，需要構(gòu)建新的網(wǎng)絡(luò)模型研究節(jié)點(diǎn)重要度評(píng)估問題.本文在文獻(xiàn)[15]的基礎(chǔ)上提出動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)(dynamic convergence complex networks，DCCN)模型，定義了與動(dòng)態(tài)性和融合性相關(guān)的網(wǎng)絡(luò)參數(shù)，結(jié)合網(wǎng)絡(luò)動(dòng)態(tài)融合特性改進(jìn)了節(jié)點(diǎn)度中心性和介數(shù)中心性指標(biāo)，并提出了節(jié)點(diǎn)融合中心性以反映各類節(jié)點(diǎn)對(duì)促進(jìn)網(wǎng)絡(luò)融合的貢獻(xiàn)程度，在此基礎(chǔ)上進(jìn)行動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估，最后通過仿真分析驗(yàn)證了方法的有效性.與現(xiàn)有模型相比，本文模型結(jié)合當(dāng)前有/無線網(wǎng)絡(luò)融合發(fā)展的需求，在融合網(wǎng)絡(luò)的基礎(chǔ)上又考慮了網(wǎng)絡(luò)動(dòng)態(tài)特性，并結(jié)合網(wǎng)絡(luò)動(dòng)態(tài)融合特性設(shè)計(jì)或改進(jìn)節(jié)點(diǎn)中心性指標(biāo)，能夠比較全面地刻畫節(jié)點(diǎn)在動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)中的重要性.

1 動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)模型

1.1 理論基礎(chǔ)

設(shè)圖Ga=Va,Ea是一個(gè)無環(huán)無向無權(quán)的單層復(fù)雜網(wǎng)絡(luò)，Va={v1,v2,…,vn}表示網(wǎng)絡(luò)a的節(jié)點(diǎn)集合，節(jié)點(diǎn)數(shù)量為Va=n，Ea={e1,e2,…,em}=Va×Va為網(wǎng)絡(luò)a的邊集合，邊的數(shù)量為Ea=m.A=Aijn×n為網(wǎng)絡(luò)a的鄰接矩陣，取值為0或1，表示節(jié)點(diǎn)之間是否存在連接邊.在圖Ga中任意兩個(gè)節(jié)點(diǎn)之間最長(zhǎng)的路徑稱為圖Ga的直徑，記為Dnd.

在單層復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)vi的度中心性定義為

式中:gi為節(jié)點(diǎn)vi的度，n為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù).

節(jié)點(diǎn)vi的介數(shù)中心性定義為

(1)

式中:Nsp(s,t)為節(jié)點(diǎn)vs和vt之間的最短路徑數(shù)量，Nsp(s,i,t)為節(jié)點(diǎn)vs和vt之間經(jīng)過節(jié)點(diǎn)vi的最短路徑數(shù)量.

1.2 模型概述

定義1動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò).由兩種以上單層復(fù)雜網(wǎng)絡(luò)融合而成，且其中至少有一種為動(dòng)態(tài)網(wǎng)絡(luò)的層級(jí)網(wǎng)絡(luò)稱為動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò).動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)中的“動(dòng)態(tài)”是指網(wǎng)絡(luò)中的邊以一定概率進(jìn)行連通(主要指無線傳輸手段等間歇連接)，而節(jié)點(diǎn)數(shù)量保持不變.網(wǎng)絡(luò)動(dòng)態(tài)性對(duì)介數(shù)等與路徑相關(guān)的參數(shù)影響較大，而對(duì)度等基于網(wǎng)絡(luò)局部屬性的參數(shù)影響較小.動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)中的“融合”是指多個(gè)網(wǎng)絡(luò)之間存在部分節(jié)點(diǎn)復(fù)用，節(jié)點(diǎn)之間可能存在兩種以上屬性的邊.為方便研究，本文僅考慮由兩種單層復(fù)雜網(wǎng)絡(luò)組成的動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)，且其中一種為動(dòng)態(tài)網(wǎng)絡(luò).

1.3 參數(shù)定義

動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)最重要的特性是動(dòng)態(tài)和融合，因此本文主要從動(dòng)態(tài)和融合兩方面設(shè)計(jì)網(wǎng)絡(luò)參數(shù).其中，網(wǎng)絡(luò)連通參數(shù)主要包括邊連通概率、路徑連通概率和網(wǎng)絡(luò)連通概率，用以描述網(wǎng)絡(luò)的連通狀況；網(wǎng)絡(luò)融合參數(shù)主要包括融合節(jié)點(diǎn)比例、融合節(jié)點(diǎn)分布和融合路徑比例，用以描述網(wǎng)絡(luò)的融合程度.

1.3.1 邊連通概率

在動(dòng)態(tài)網(wǎng)絡(luò)中，如果節(jié)點(diǎn)vi和vj之間存在連接邊，則Pij表示該邊的連通概率，并假定非動(dòng)態(tài)網(wǎng)絡(luò)中邊的連通概率為1.令P=PijN×N為融合網(wǎng)絡(luò)c的連通性矩陣，規(guī)定節(jié)點(diǎn)之間無連接邊時(shí)取值為0，節(jié)點(diǎn)之間有1條邊時(shí)為該邊的連通概率，節(jié)點(diǎn)之間有2條邊時(shí)取2條邊的連通概率的最大值.

1.3.2 路徑連通概率

設(shè)路徑vi-vm-vn-…-vz-vj，則Qij(k)=Pim×Pmn×…×Pzj表示該路徑的連通概率，為該路徑上所有邊的連通概率之積.值得注意的是，Qij(k)=Pim×Pmn×…×Pzj表示特定的一條路徑(vi-vm-vn-…-vz-vj，其路徑編號(hào)為k)的連通概率，而不是指節(jié)點(diǎn)vi和vj之間的路徑連通概率，因?yàn)楣?jié)點(diǎn)vi和vj可能存在多條路徑(路徑編號(hào)k取不同的值)，而每一條路徑都對(duì)應(yīng)一個(gè)路徑連通概率.

1.3.3 網(wǎng)絡(luò)連通概率

網(wǎng)絡(luò)連通概率定義為

反映整個(gè)網(wǎng)絡(luò)的平均連通狀況.

1.3.4 融合節(jié)點(diǎn)比例

融合節(jié)點(diǎn)比例定義為

Rcnp=M/N，

表示網(wǎng)絡(luò)節(jié)點(diǎn)集中融合節(jié)點(diǎn)所占的比例，從融合節(jié)點(diǎn)數(shù)量的角度反映網(wǎng)絡(luò)融合程度，融合節(jié)點(diǎn)越多則越能促進(jìn)網(wǎng)絡(luò)的融合.

1.3.5 融合節(jié)點(diǎn)分布

融合節(jié)點(diǎn)比例在一定程度上反映了網(wǎng)絡(luò)的融合程度，但還存在片面性.如果融合節(jié)點(diǎn)比較密集地分布在局部區(qū)域，那么與融合節(jié)點(diǎn)分散分布的情形相比，其對(duì)促進(jìn)整個(gè)網(wǎng)絡(luò)融合的作用會(huì)減弱.因此，定義融合節(jié)點(diǎn)分布為

Rcnd=Davg/Dnd，

表示網(wǎng)絡(luò)中融合節(jié)點(diǎn)的緊密程度，從融合節(jié)點(diǎn)位置的角度反映網(wǎng)絡(luò)融合程度，融合節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置越分散則越能促進(jìn)網(wǎng)絡(luò)的融合.其中，Davg為融合節(jié)點(diǎn)之間的平均距離，Dnd為融合網(wǎng)絡(luò)的直徑.

1.3.6 融合路徑比例

融合路徑比例定義為

Rcpp=Ncp/Nsp，

表示最短路徑中融合路徑所占的比例，從消息傳播的角度反映網(wǎng)絡(luò)融合程度，融合路徑越多則越能促進(jìn)網(wǎng)絡(luò)的融合.其中，Nsp為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的最短路徑的數(shù)量，Ncp為這些最短路徑中融合路徑的數(shù)量.融合路徑是指包含兩種邊的路徑，僅包含融合節(jié)點(diǎn)但只有一種邊的路徑不是融合路徑.如圖1所示，對(duì)于路徑1-2-3-4，圖1(a)、(b)為融合路徑，而圖1(c)不是融合路徑.

圖1 融合路徑示例

2 節(jié)點(diǎn)重要度評(píng)估方法

動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)重要度評(píng)估主要是在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，考慮動(dòng)態(tài)及融合特性的影響.度中心性和介數(shù)中心性是節(jié)點(diǎn)重要度評(píng)估中最常用的指標(biāo)，分別基于網(wǎng)絡(luò)局部屬性和全局屬性反映單層復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性.但對(duì)于動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)由于網(wǎng)絡(luò)融合而具有新的變化，因此本文結(jié)合其特性進(jìn)行重新定義.此外，提出節(jié)點(diǎn)融合中心性指標(biāo)，從節(jié)點(diǎn)促進(jìn)網(wǎng)絡(luò)融合的角度反映其重要性.

定義2融合網(wǎng)絡(luò)節(jié)點(diǎn)度中心性.

融合網(wǎng)絡(luò)中節(jié)點(diǎn)vi的度中心性定義為

(2)

定義3融合網(wǎng)絡(luò)節(jié)點(diǎn)介數(shù)中心性.

融合網(wǎng)絡(luò)中節(jié)點(diǎn)vi的介數(shù)中心性定義為

(3)

定義4融合網(wǎng)絡(luò)節(jié)點(diǎn)融合中心性.

融合網(wǎng)絡(luò)中節(jié)點(diǎn)vi的融合中心性定義為

對(duì)于融合節(jié)點(diǎn)，其融合中心性表示融合節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)融合的貢獻(xiàn)程度.一旦網(wǎng)絡(luò)拓?fù)鋮?shù)確定，所有融合節(jié)點(diǎn)的融合中心性是一個(gè)與其位置特性無關(guān)的固定值，從宏觀上反映網(wǎng)絡(luò)中所有融合節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)融合的貢獻(xiàn)程度.融合節(jié)點(diǎn)比例越低，融合路徑比例越低，融合節(jié)點(diǎn)分布越密集，則網(wǎng)絡(luò)的融合程度越低.而在網(wǎng)絡(luò)融合程度低的情形下，融合節(jié)點(diǎn)發(fā)揮的作用就越大，從而融合節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)融合的貢獻(xiàn)程度就越高.另外，加入?yún)?shù)Rncp考慮網(wǎng)絡(luò)動(dòng)態(tài)性對(duì)融合路徑的影響，使指標(biāo)的計(jì)算更加客觀.

對(duì)于非融合節(jié)點(diǎn)，其融合中心性表示非融合節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)融合的輔助作用程度，主要體現(xiàn)在作為融合節(jié)點(diǎn)之間的中繼節(jié)點(diǎn).其中，Nacn為節(jié)點(diǎn)vi的鄰居融合節(jié)點(diǎn)數(shù)量，ci為節(jié)點(diǎn)vi的融合聚類系數(shù)，反映其鄰居融合節(jié)點(diǎn)之間的連通程度，定義為

式中，fi為節(jié)點(diǎn)vi與其任意兩個(gè)鄰居融合節(jié)點(diǎn)之間所形成的三角形的個(gè)數(shù).若gi=1或Nacn=0，則令ci=+.

由于非融合節(jié)點(diǎn)的融合中心性主要體現(xiàn)在連通那些原本相互之間連通程度較弱的融合節(jié)點(diǎn)上，因此節(jié)點(diǎn)vi的鄰居融合節(jié)點(diǎn)的比例越高，且它們之間的連通程度越弱，則非融合節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)融合的輔助作用程度越高.如圖2所示，圖2(a)、(b)、(c)中節(jié)點(diǎn)1的融合中心性分別為0.40、0.60、0.36.圖2(b)比圖2(a)的值高是因?yàn)槿诤瞎?jié)點(diǎn)比例增加，圖2(c)比圖2(b)的值低是因?yàn)槿诤暇垲愊禂?shù)提高，節(jié)點(diǎn)1在連通融合節(jié)點(diǎn)3、4、5的作用上減弱了，其融合中心性也要降低.

圖2 非融合節(jié)點(diǎn)的融合中心性示例

定義5融合網(wǎng)絡(luò)節(jié)點(diǎn)重要度.

根據(jù)定義2～定義4，綜合考慮局部位置信息、全局位置信息、網(wǎng)絡(luò)融合特性3個(gè)方面，定義融合網(wǎng)絡(luò)的節(jié)點(diǎn)重要度為

Ii=α×Di+β×Bi+γ×Ci.

式中，α、β、γ∈(0,1)，且α+β+γ=1，通過3個(gè)參數(shù)的設(shè)置可以調(diào)節(jié)各中心性在最終節(jié)點(diǎn)重要度評(píng)估中的權(quán)重.一般來說，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)節(jié)點(diǎn)重要度的影響是主要的，因此參數(shù)α和β應(yīng)設(shè)置較大一些.融合中心性是在動(dòng)態(tài)融合網(wǎng)絡(luò)模型中對(duì)節(jié)點(diǎn)重要度評(píng)估的一個(gè)改進(jìn)和補(bǔ)充，因此參數(shù)γ應(yīng)設(shè)置小一些.

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

3.1 典型算例

為驗(yàn)證本文節(jié)點(diǎn)重要度評(píng)估方法的有效性，以文獻(xiàn)[15]中的交織風(fēng)箏網(wǎng)絡(luò)為基礎(chǔ)網(wǎng)絡(luò)，并加入連邊的動(dòng)態(tài)特性以構(gòu)成動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)(如圖3所示).其中，單層網(wǎng)絡(luò)a包含10個(gè)節(jié)點(diǎn)、18條邊；單層網(wǎng)絡(luò)b為動(dòng)態(tài)網(wǎng)絡(luò)，包含8個(gè)節(jié)點(diǎn)、13條邊，邊上的數(shù)值代表邊的連通概率；融合網(wǎng)絡(luò)c為網(wǎng)絡(luò)a和b融合構(gòu)成的網(wǎng)絡(luò)，包含13個(gè)節(jié)點(diǎn)、31條邊，其中5個(gè)融合節(jié)點(diǎn)分別由網(wǎng)絡(luò)a和b中具有相同編號(hào)的節(jié)點(diǎn)融合形成.

實(shí)驗(yàn)中設(shè)置參數(shù)α=0.4，β=0.4，γ=0.2，通過MATLAB 2010a進(jìn)行仿真實(shí)驗(yàn)，分別計(jì)算單層網(wǎng)絡(luò)a和b中各節(jié)點(diǎn)的度中心性和介數(shù)中心性，以及網(wǎng)絡(luò)融合后各節(jié)點(diǎn)在融合網(wǎng)絡(luò)中的中心性指標(biāo)，仿真結(jié)果見表1～3.

圖3 動(dòng)態(tài)交織風(fēng)箏網(wǎng)絡(luò)

節(jié)點(diǎn)編號(hào)12345678910111213網(wǎng)絡(luò)a0．1110．2220．3330．5560．5560．3330．6670．3330．4440．444———網(wǎng)絡(luò)b0．428—0．714——0．5710．2860．571——0．4290．4290．286網(wǎng)絡(luò)c(文獻(xiàn)[15])0．6740．1671．5860．4160．4161．4451．3491．4450．3330．3330．2310．2310．167網(wǎng)絡(luò)c(本文)0．4440．1671．0670．4160．4160．8750．6670．8750．3330．3330．2500．2500．167

表2 介數(shù)中心性

表3 融合中心性和節(jié)點(diǎn)重要度

由表1可以看出，融合節(jié)點(diǎn)1、3、6、7、8的度中心性較高，一是網(wǎng)絡(luò)融合后這些節(jié)點(diǎn)的度有所增加，二是式(2)使融合節(jié)點(diǎn)的度中心性得到加強(qiáng)，而非融合節(jié)點(diǎn)由于融合網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的增加而使其度中心性降低，說明本文計(jì)算節(jié)點(diǎn)度中心性考慮了網(wǎng)絡(luò)融合的影響，這與文獻(xiàn)[15]是類似的.節(jié)點(diǎn)3在融合網(wǎng)絡(luò)中具有最高的度值并且得到加強(qiáng)，因而其度中心性排名最高.

由表2可以看出，本文計(jì)算的所有節(jié)點(diǎn)的介數(shù)中心性都不高，雖然網(wǎng)絡(luò)融合產(chǎn)生了更多的節(jié)點(diǎn)對(duì)和最短路徑，但式(3)考慮融合路徑和網(wǎng)絡(luò)動(dòng)態(tài)性后使計(jì)算結(jié)果較小.與文獻(xiàn)[15]相比，雖然本文計(jì)算節(jié)點(diǎn)介數(shù)中心性的條件比較嚴(yán)格，但能夠在動(dòng)態(tài)融合的網(wǎng)絡(luò)環(huán)境下真實(shí)反映信息傳播對(duì)介數(shù)的貢獻(xiàn).節(jié)點(diǎn)3在各單層網(wǎng)絡(luò)中就具有最高的介數(shù)中心性，網(wǎng)絡(luò)融合后仍是許多融合最短路徑所經(jīng)過的節(jié)點(diǎn)，因此其介數(shù)中心性排名最高.節(jié)點(diǎn)6和8在單層網(wǎng)絡(luò)中的介數(shù)中心性排名比較低，但網(wǎng)絡(luò)融合后在融合最短路徑上的貢獻(xiàn)度較大，因此介數(shù)中心性排名比較靠前.同時(shí)，節(jié)點(diǎn)8比節(jié)點(diǎn)6的值稍高，是因?yàn)榫W(wǎng)絡(luò)b左半部分的邊連通概率比右半部分的高，這點(diǎn)在其他對(duì)稱的節(jié)點(diǎn)對(duì)(如節(jié)點(diǎn)4、5、9和10、11和12)之間也有所體現(xiàn)，從而說明本文的指標(biāo)能夠反映網(wǎng)絡(luò)連通性的影響.節(jié)點(diǎn)1的介數(shù)中心性不再是單層網(wǎng)絡(luò)中的0，主要是網(wǎng)絡(luò)融合后該節(jié)點(diǎn)在融合最短路徑上有所貢獻(xiàn).節(jié)點(diǎn)2的介數(shù)中心性由網(wǎng)絡(luò)a中的0.222變?yōu)?，是由于節(jié)點(diǎn)1和3之間的連邊使節(jié)點(diǎn)2的兩條鄰邊成為了冗余路徑.

如表3所示，融合中心性方面，融合節(jié)點(diǎn)的值為0.429，是融合節(jié)點(diǎn)比例、融合路徑比例和融合節(jié)點(diǎn)分布等3個(gè)網(wǎng)絡(luò)融合參數(shù)共同決定的，反映了融合節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)融合的貢獻(xiàn)程度.非融合節(jié)點(diǎn)2、11、12、13的融合中心性較高，說明它們?cè)谳o助網(wǎng)絡(luò)融合方面起到了較大作用，從網(wǎng)絡(luò)拓?fù)渲幸部梢钥闯鏊鼈兌际沁B接融合節(jié)點(diǎn)的樞紐，在融合程度不高的網(wǎng)絡(luò)中它們的重要性更是不能忽視.節(jié)點(diǎn)重要度方面，本文綜合考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和動(dòng)態(tài)融合特性等因素，對(duì)節(jié)點(diǎn)重要度的評(píng)估是一個(gè)綜合評(píng)價(jià)指標(biāo).5個(gè)融合節(jié)點(diǎn)的重要度位居前列，這也與指標(biāo)設(shè)計(jì)的基本思想是一致的.對(duì)稱節(jié)點(diǎn)對(duì)的重要度差異主要來自介數(shù)中心性的計(jì)算，最終反映了網(wǎng)絡(luò)動(dòng)態(tài)性對(duì)節(jié)點(diǎn)重要度的影響.非融合節(jié)點(diǎn)13的排名緊跟融合節(jié)點(diǎn)之后，主要在于其融合中心性的作用，體現(xiàn)了對(duì)非融合節(jié)點(diǎn)重要度的加強(qiáng)，使節(jié)點(diǎn)重要度評(píng)估更加全面、客觀.

在節(jié)點(diǎn)重要度評(píng)估中，節(jié)點(diǎn)度中心性和融合中心性主要考慮網(wǎng)絡(luò)融合性的影響，節(jié)點(diǎn)介數(shù)中心性主要考慮網(wǎng)絡(luò)動(dòng)態(tài)性的影響，并通過α、β、γ這3個(gè)參數(shù)的設(shè)置進(jìn)行調(diào)節(jié).由于節(jié)點(diǎn)度中心性和介數(shù)中心性是以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)，而網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是節(jié)點(diǎn)重要度的主要影響因素，因此本文給參數(shù)γ一個(gè)較小的固定值，并考察參數(shù)α和β的不同變化對(duì)節(jié)點(diǎn)重要度的影響，仿真結(jié)果如圖4所示.可以看出，隨著α的增大，網(wǎng)絡(luò)融合性的影響增強(qiáng)，融合節(jié)點(diǎn)的重要度有顯著的提高.隨著β的增大，網(wǎng)絡(luò)動(dòng)態(tài)性的影響增強(qiáng)，各節(jié)點(diǎn)的重要度均有所降低，尤其對(duì)節(jié)點(diǎn)9～12等介數(shù)中心性較小的節(jié)點(diǎn)影響較大，β=0.2時(shí)其重要度均排在節(jié)點(diǎn)13之前，而β=0.8時(shí)均排在節(jié)點(diǎn)13之后.

圖4 不同參數(shù)設(shè)置下的節(jié)點(diǎn)重要度

3.2 仿真網(wǎng)絡(luò)

為進(jìn)一步驗(yàn)證本文方法的適用性，利用NS2搭建仿真網(wǎng)絡(luò)，仿真場(chǎng)景及其對(duì)應(yīng)的網(wǎng)絡(luò)拓?fù)淙鐖D5、6所示.該仿真網(wǎng)絡(luò)由光通信網(wǎng)和衛(wèi)星通信網(wǎng)融合構(gòu)成，是典型的有線與無線混合組網(wǎng)的情景.網(wǎng)絡(luò)中共有15個(gè)節(jié)點(diǎn)，其中有線節(jié)點(diǎn)7個(gè)(W1～W7)，無線節(jié)點(diǎn)5個(gè)(M1～M4，B1)，融合節(jié)點(diǎn)3個(gè)(B2～B4).網(wǎng)絡(luò)中共18條鏈路，其中有線鏈路11條，無線鏈路7條.另外，仿真網(wǎng)絡(luò)中僅反映無線節(jié)點(diǎn)之間的連通關(guān)系(即兩個(gè)無線節(jié)點(diǎn)之間是否存在無線鏈路)，而不考慮其運(yùn)動(dòng)情況.

圖5 仿真場(chǎng)景

圖6 網(wǎng)絡(luò)拓?fù)?/p>

鏈路連通率反映了鏈路兩端點(diǎn)之間成功發(fā)送或接收數(shù)據(jù)的情況，因此本文采用鏈路連通率計(jì)算無線鏈路的邊連通概率.設(shè)置背景流量模擬網(wǎng)絡(luò)中的數(shù)據(jù)傳輸情況，通過流量發(fā)生器的源/目的節(jié)點(diǎn)設(shè)置使數(shù)據(jù)流覆蓋所有鏈路.仿真時(shí)間共100 s，以1 s為時(shí)間間隔測(cè)量無線鏈路的連通率，并取仿真時(shí)間內(nèi)測(cè)量所得的鏈路連通率的平均值作為該無線鏈路的邊連通概率，計(jì)算結(jié)果見表4.設(shè)置參數(shù)α=0.4，β=0.4，γ=0.2，計(jì)算節(jié)點(diǎn)的度中心性、介數(shù)中心性、融合中心性和節(jié)點(diǎn)重要度，見表5.

表4 邊連通概率

表5 中心性指標(biāo)及節(jié)點(diǎn)重要度

由表5可以看出，B2～B4等3個(gè)融合節(jié)點(diǎn)的度中心性和介數(shù)中心性相對(duì)其他非融合節(jié)點(diǎn)較高，反映了在動(dòng)態(tài)融合網(wǎng)絡(luò)環(huán)境中融合節(jié)點(diǎn)在拓?fù)浣Y(jié)構(gòu)上的重要性，而對(duì)于W1、W6、W7、M4等處于網(wǎng)絡(luò)邊緣的節(jié)點(diǎn)，其度中心性和介數(shù)中心性均較低.3個(gè)融合節(jié)點(diǎn)的融合中心性為0.491，而M1～M3等3個(gè)非融合節(jié)點(diǎn)的融合中心性較高，反映出它們對(duì)網(wǎng)絡(luò)融合的輔助作用程度較大.綜合3個(gè)中心性指標(biāo)計(jì)算得出，3個(gè)融合節(jié)點(diǎn)的重要度較高，M3節(jié)點(diǎn)由于其融合中心性高而使其重要度也較高，W1、W6、W7、M4等節(jié)點(diǎn)由于各中心性指標(biāo)均較低而使其重要度較低，其他節(jié)點(diǎn)的重要度處于中間的位置.通過上述分析，利用本文方法基本能夠合理地反映不同節(jié)點(diǎn)在動(dòng)態(tài)融合網(wǎng)絡(luò)中的重要程度，進(jìn)一步驗(yàn)證了在仿真網(wǎng)絡(luò)環(huán)境中本文方法的有效性.

4 結(jié) 論

1)針對(duì)有/無線多網(wǎng)融合的層級(jí)網(wǎng)絡(luò)，本文綜合考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、動(dòng)態(tài)融合特性等因素，提出了動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)模型及其節(jié)點(diǎn)重要度評(píng)估方法.以改進(jìn)的動(dòng)態(tài)交織風(fēng)箏網(wǎng)絡(luò)和NS2搭建的仿真實(shí)驗(yàn)網(wǎng)絡(luò)為例進(jìn)行仿真分析，結(jié)果表明，該方法能夠比較全面地反映動(dòng)態(tài)融合復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要度.

2)本文定義的動(dòng)態(tài)網(wǎng)絡(luò)僅限于邊的連通性變化，未考慮節(jié)點(diǎn)數(shù)量的增減[19]，下一步可采用大規(guī)模有/無線融合通信網(wǎng)等真實(shí)網(wǎng)絡(luò)進(jìn)行驗(yàn)證.

3)文中節(jié)點(diǎn)重要度的計(jì)算采用各中心性指標(biāo)線性加權(quán)得出，參數(shù)設(shè)置比較簡(jiǎn)單，未來可考慮采用多屬性決策[20]等方法作進(jìn)一步研究.

[1] WATTS D J, STROGATZ S H. Collective dynamics of small-world networks[J]. Nature, 1998,393(6684): 440-442. DOI: 10.1038/30918.

[2] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439):509-512. DOI: 10.1126/science.286.5439.509.

[3] 紐曼. 網(wǎng)絡(luò)科學(xué)引論[M]. 郭世澤, 陳哲, 譯. 北京: 電子工業(yè)出版社, 2014: 106.

NEWMAN M E J. Networks: an introduction[M]. Guo S Z, Chen Z. Beijing: Publishng House of Electronics Industry, 2014: 106.

[4] 周濤, 張子柯, 陳關(guān)榮, 等. 復(fù)雜網(wǎng)絡(luò)研究的機(jī)遇與挑戰(zhàn)[J]. 電子科技大學(xué)學(xué)報(bào), 2014,43(1):1-5.DOI: 10.3969/j.issn.1001-0548.2014.01.001.

ZHOU Tao, ZHANG Zike, CHEN Guanrong, et al. The opportunities and challenges of complex networks research[J]. Journal of University of Electronic Science and Technology of China, 2014, 43(1):1-5. DOI: 10.3969/j.issn.1001-0548.2014.01.001.

[5] 劉建國(guó), 任卓明, 郭強(qiáng), 等. 復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序的研究進(jìn)展[J]. 物理學(xué)報(bào), 2013, 62(17):178901. DOI:10.7498/aps.62.178901.

LIU Jianguo, REN Zhuoming, GUO Qiang, et al. Node importance ranking of complex networks[J]. Acta Physica Sinica, 2013, 62(17):178901. DOI:10.7498/aps.62.178901.

[6] KOURTELLIS N, ALAHAKOON T, SIMHA R, et al. Identifying high betweenness centrality nodes in large social networks[J]. Social Network Analysis and Mining, 2013, 3(4):899-914. DOI: 10.1007/s13278-012-0076-6.

[8] SAITO K, KIMURA M, OHARA K, et al. Efficient discovery of influential nodes for SIS models in social networks[J]. Knowledge and Information Systems, 2012, 30(3): 613-635. DOI: 10.1007/s10115-011-0396-2.

[9] ZHOU Jingyu, ZHANG Yunlong, CHENG Jia. Preference-based mining of top-K influential nodes in social network[J]. Future Generation Computer Systems, 2014, 31:40-47. DOI: 10.1016/j.future.2012.06.011.

[10]張欣. 多層復(fù)雜網(wǎng)絡(luò)理論研究進(jìn)展：概念、理論和數(shù)據(jù)[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2015, 12(2):103-107. DOI: 10.13306/j.1672-3813.2015.02.016.

ZHANG Xin. Multilayer networks science: concepts, theories and data[J]. Complex Systems and Complexity Science, 2015, 12(2):103-107. DOI: 10.13306/j.1672-3813.2015.02.016.

[11]BULDYREV S V, PARSHANI R, PAUL G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010(464):1025-1028.DOI: 10.1038/nature08932.

[12]陳宏斌, 樊瑛, 方錦清, 等. 二元隨機(jī)網(wǎng)[J]. 物理學(xué)報(bào), 2009, 58(3):1383-1390.

CHEN Hongbin, FAN Ying, FANG Jinqing, et al. Bielemental random networks[J]. Acta Physica Sinica, 2009, 58(3):1383-1390.

[13]邵峰晶, 孫仁誠(chéng), 李淑靜, 等. 多子網(wǎng)復(fù)合復(fù)雜網(wǎng)絡(luò)及其運(yùn)算研究[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2012, 9(4):20-25.

SHAO Fengjing, SUN Rencheng, LI Shujing, et al. Research of multi-subnet composited complex network and its operation[J]. Complex Systems and Complexity Science, 2012, 9(4):20-25.

[14]郭進(jìn)利, 祝昕昀. 超網(wǎng)絡(luò)中標(biāo)度律的涌現(xiàn)[J]. 物理學(xué)報(bào), 2014, 63(9):090207. DOI:10.7498/aps.63.090207.

GUO Jinli, ZHU Xinyun. Emergence of scaling in hypernetworks[J]. Acta Physica Sinica, 2014, 63(9):090207. DOI:10.7498/aps.63.090207.

[15]沈迪, 李建華, 張強(qiáng), 等. 交織型層級(jí)復(fù)雜網(wǎng)[J]. 物理學(xué)報(bào), 2014, 63(19):190201. DOI:10.7498/aps.63.190201.

SHEN Di, LI Jianhua, ZHANG Qiang, et al. Interlacing layered complex networks[J]. Acta Physica Sinica, 2014, 63(19):190201. DOI:10.7498/aps.63.190201.

[16]HOLME P, SARAMAKI J. Temporal networks[J]. Physics Reports, 2012,519(3):97-125. DOI:10.1016/j.physrep.2012.03.001.

[17]BASARAS P, KATSAROS D, TASSIULAS L. Detecting influential spreaders in complex, dynamic networks[J]. Computer, 2013,46(4):24-29. DOI: 10.1109/MC.2013.75.

[18]MASAKI O. A method for extracting influential nodes while considering the development of social networks[C]// Proceedings of the 2012 Second International Conference on Cloud and Green Computing. Xiangtan, China: IEEE, 2012: 456-459. DOI: 10.1109/CGC.2012.77.

[19]ZHOU Jian, PAN Jiaxin, ZHOU Yanran. Node importance evaluation based on network heterogeneity[C]// Proceedings of the 2010 International Conference on Communications and Mobile Computing. Shenzhen, China: IEEE, 2010:188-194. DOI: 10.1109/CMC.2010.112.

[20]于會(huì), 劉尊, 李勇軍. 基于多屬性決策的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性綜合評(píng)價(jià)方法[J]. 物理學(xué)報(bào), 2013, 62(2): 020204. DOI:10.7498/aps.62.020204.

YU Hui, LIU Zun, LI Yongjun. Key nodes in complex networks identified by multi-attribute decision-making method[J]. Acta Physica Sinica, 2013, 62(2): 020204. DOI:10.7498/aps.62.020204.

Nodeimportanceevaluationindynamicconvergencecomplexnetworks

FU Kai1,2， XIA Jingbo3， ZHAO Xiaohuan4

(1.Information and Navigation College, Air Force Engineering University, Xi’an 710077, China; 2.Unit 95246, Nanning 530003, China; 3.Tan Kah Kee College, Xiamen University, Zhangzhou 363105, Fujian, China; 4.Unit 95340, Baise 533616, Guangxi, China)

To seek key nodes and improve network robustness, the dynamic convergence complex network model and its node importance evaluation method are proposed for wired and wireless integrating layered networks. Considering characteristic of dynamic convergence complex networks, parameters including edge connection probability, path connection probability, network connection probability, convergence node proportion, convergence node distribution and convergence path proportion are designed. Based on node importance evaluation indexes in single-layer complex networks, the node degree centrality, node betweenness centrality and node convergence centrality in dynamic convergence complex networks are presented. Node convergence centrality of convergence nodes indicates their contribution to network convergence, and that of non-convergence nodes indicates their auxiliary effect to network convergence, especially they are used as relay nodes among convergence nodes. At last, node importance evaluation is implemented considering network topology structure and its dynamic convergence characteristic. Typical example results of improved dynamic convergence kite networks show that the proposed method can comprehensively depict the node importance in dynamic convergence complex networks. Simulation network composed of fiber communication network and satellite communication network is designed by NS2, further indicating the effectiveness of the proposed method.

complex networks; dynamic convergence; node importance; degree centrality; betweenness centrality; convergence centrality

10.11918/j.issn.0367-6234.201607012

TP393

A

0367-6234(2017)10-0112-08

2016-07-05

航空科學(xué)基金(20141996018)；陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目(2012JZ8005)

付 凱(1987—)，男，博士研究生；

夏靖波(1963—)，男，教授，博士生導(dǎo)師

付 凱，fukaia3@163.com

(編輯張 紅)