劉 崢,郭舒婷,周綺鳳,李 濤

(1.南京郵電大學(xué)計(jì)算機(jī)學(xué)院,江蘇 南京 210023;2.江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 210023;3.廈門(mén)大學(xué)航天航空學(xué)院,福建 廈門(mén) 361005)

目前,現(xiàn)代大規(guī)模復(fù)雜網(wǎng)絡(luò)基礎(chǔ)設(shè)施的日常運(yùn)維往往依賴于集中式網(wǎng)絡(luò)監(jiān)控平臺(tái)和人工干預(yù)來(lái)保證網(wǎng)絡(luò)服務(wù)的可靠性[1-2].重要網(wǎng)元的監(jiān)視和管理對(duì)保障網(wǎng)絡(luò)服務(wù)的可靠性至關(guān)重要.網(wǎng)元的重要性往往由網(wǎng)絡(luò)管理員根據(jù)經(jīng)驗(yàn)來(lái)判斷,然而在網(wǎng)絡(luò)基礎(chǔ)設(shè)施規(guī)模日益增大和網(wǎng)絡(luò)管理人力資源有限的背景下,對(duì)于承載重要業(yè)務(wù)的網(wǎng)元相對(duì)較易確定,而對(duì)于處于網(wǎng)絡(luò)基礎(chǔ)設(shè)施拓?fù)浣Y(jié)構(gòu)中的重要節(jié)點(diǎn)的判斷卻很難由人工判定,常常出現(xiàn)錯(cuò)誤及遺漏.

網(wǎng)絡(luò)基礎(chǔ)設(shè)施中面向業(yè)務(wù)的網(wǎng)元子圖是指網(wǎng)絡(luò)基礎(chǔ)設(shè)施中承載具體業(yè)務(wù)的重要網(wǎng)元的拓?fù)渥訄D,也包括其他非重要網(wǎng)元.通過(guò)確定面向業(yè)務(wù)的網(wǎng)元子圖,可以滿足大規(guī)模網(wǎng)絡(luò)基礎(chǔ)設(shè)施中運(yùn)維需求,僅需投入較少人力對(duì)這些拓?fù)渥訄D中的網(wǎng)元進(jìn)行重點(diǎn)監(jiān)控,就可以提高故障分析的效率,節(jié)省網(wǎng)絡(luò)基礎(chǔ)設(shè)施運(yùn)維的成本.目前在網(wǎng)絡(luò)基礎(chǔ)設(shè)施運(yùn)維中并沒(méi)有成熟的網(wǎng)元子圖的確定方法,傳統(tǒng)的方法是從發(fā)生故障的網(wǎng)元出發(fā),將其鄰域網(wǎng)元所組成的子圖作為網(wǎng)元子圖.

在社交網(wǎng)絡(luò)研究領(lǐng)域,已經(jīng)有一些學(xué)者對(duì)節(jié)點(diǎn)的影響力進(jìn)行了研究,并將高影響力的節(jié)點(diǎn)作為重要節(jié)點(diǎn).Kempe等[3]研究了影響最大化問(wèn)題,集中介紹了描述節(jié)點(diǎn)激活行為的模型.Leskovec等[4]提出一種高性價(jià)比的懶惰前向(cost-effective lazy forward,CELF)貪心算法的優(yōu)化策略,運(yùn)用獨(dú)立級(jí)聯(lián)型的次模特性(sub-modularity),大大降低了選擇最具影響力節(jié)點(diǎn)的工作次數(shù).此外,Lei等[5]提出了一個(gè)能夠在市場(chǎng)病毒式營(yíng)銷中學(xué)習(xí)到傳播概率的方法.Farajtabar等[6]通過(guò)對(duì)社會(huì)活動(dòng)進(jìn)行建模,構(gòu)建了一個(gè)凸優(yōu)化框架確定激勵(lì)用戶刺激社交活動(dòng)所需的活動(dòng)水平.但這些社交網(wǎng)絡(luò)中的影響力評(píng)估算法著重關(guān)注社交網(wǎng)絡(luò)中信息的傳播模型,而不是故障傳播模型,并不適用于評(píng)估網(wǎng)絡(luò)技術(shù)設(shè)施中網(wǎng)元的影響力.在圖數(shù)據(jù)挖掘的研究領(lǐng)域中,已經(jīng)有一些學(xué)者提出了一些節(jié)點(diǎn)之間關(guān)系的度量方法.Jeh等[7]提出了一種通過(guò)節(jié)點(diǎn)鄰域的相似性來(lái)度量節(jié)點(diǎn)之間的相似度的方法,稱為SimRank,表征從兩個(gè)節(jié)點(diǎn)出發(fā)的隨機(jī)游走的期望相遇距離.Palmer等[8]定義了一個(gè)距離函數(shù)來(lái)衡量?jī)蓚€(gè)屬性數(shù)據(jù)集之間的相似度,用圖模型來(lái)表示屬性值,兩個(gè)屬性值之間的距離定義為重啟隨機(jī)游走的逃逸概率.但這些重要性的度量方法都沒(méi)有考慮到網(wǎng)絡(luò)基礎(chǔ)設(shè)施中網(wǎng)元重要性的特點(diǎn),沒(méi)有將重要節(jié)點(diǎn)的鄰域節(jié)點(diǎn)進(jìn)行深入分析.此外,由于拓?fù)浣Y(jié)構(gòu)和承載業(yè)務(wù)兩者的異構(gòu)性,也不能直接利用上述方法度量網(wǎng)元的重要性.另一方面重要網(wǎng)元子圖的確定與社交網(wǎng)絡(luò)研究領(lǐng)域中的社區(qū)發(fā)現(xiàn)有一定相似.目前,對(duì)圖上的社區(qū)發(fā)現(xiàn)算法主要包括:基于譜分析的聚類算法[9],基于圖劃分的聚類算法[10],基于層次的聚類算法[11]以及基于密度的聚類算法[12].Liu等[13]搜索網(wǎng)絡(luò)中的極大團(tuán),并依據(jù)其連接情況合并極大團(tuán)來(lái)獲得網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu).Pons等[14]提出利用長(zhǎng)度為l的隨機(jī)游走來(lái)度量圖上兩個(gè)節(jié)點(diǎn)的相似度用于社區(qū)發(fā)現(xiàn).Tong等[15]也提出了利用重啟隨機(jī)游走在圖數(shù)據(jù)上發(fā)現(xiàn)中心子圖.但社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)偏重于尋找社交網(wǎng)絡(luò)中的相似節(jié)點(diǎn)的集合,而不是根據(jù)節(jié)點(diǎn)的影響力來(lái)判斷節(jié)點(diǎn)的影響范圍.

為了同時(shí)考慮網(wǎng)元連接關(guān)系的重要性和承載業(yè)務(wù)的重要性,本研究將業(yè)務(wù)轉(zhuǎn)換為圖模型上的點(diǎn),利用鄰域影響度來(lái)衡量網(wǎng)元之間(圖上節(jié)點(diǎn)之間)的連接關(guān)系,并由此評(píng)估節(jié)點(diǎn)的重要性.識(shí)別重要節(jié)點(diǎn)后,根據(jù)其重要性衡量標(biāo)準(zhǔn),將確定網(wǎng)元子圖的問(wèn)題變成一個(gè)在圖上對(duì)節(jié)點(diǎn)進(jìn)行分組的問(wèn)題.為此,本文中提出了一個(gè)3步的框架來(lái)識(shí)別重要網(wǎng)元子圖:

1) 評(píng)估網(wǎng)元節(jié)點(diǎn)的重要性,尋找重要的網(wǎng)元節(jié)點(diǎn);

2) 從每個(gè)重要網(wǎng)元節(jié)點(diǎn)出發(fā),根據(jù)節(jié)點(diǎn)之間的相關(guān)性,生成網(wǎng)元重要子圖;

3) 融合網(wǎng)元重要子圖,形成網(wǎng)元重要子圖集合.

1 評(píng)估網(wǎng)元節(jié)點(diǎn)的重要性

為了同時(shí)考慮網(wǎng)元連接關(guān)系的重要性和承載業(yè)務(wù)的重要性,首先需要弄清重要網(wǎng)元的特征.從大規(guī)模復(fù)雜網(wǎng)絡(luò)運(yùn)維實(shí)際出發(fā),網(wǎng)元的重要性主要體現(xiàn)在以下兩方面:1) 重要網(wǎng)元與其他網(wǎng)元的直接連接或間接連接的關(guān)系較密切,體現(xiàn)在重要網(wǎng)元與其他網(wǎng)元之間的連通路徑較多,一旦重要網(wǎng)元發(fā)生故障,可能會(huì)影響其他網(wǎng)元之間的通信或服務(wù)交互.2) 重要網(wǎng)元所承載的業(yè)務(wù)的數(shù)量較多,級(jí)別也較高.一旦重要網(wǎng)元發(fā)生故障,會(huì)影響到承載同樣業(yè)務(wù)的其他網(wǎng)元服務(wù)的穩(wěn)定性.

根據(jù)重要網(wǎng)元的特征，本研究將業(yè)務(wù)轉(zhuǎn)換為圖模型上的節(jié)點(diǎn),再利用鄰域影響度捕捉節(jié)點(diǎn)的連接關(guān)系,進(jìn)而將連接關(guān)系的重要性和承載業(yè)務(wù)的重要性統(tǒng)一起來(lái).本文中的網(wǎng)絡(luò)基礎(chǔ)設(shè)施用圖模型G=〈V，E〉表示,其中V是所有網(wǎng)元節(jié)點(diǎn)vi所組成的集合,E表示網(wǎng)元之間連接關(guān)系的集合,即圖上兩個(gè)節(jié)點(diǎn)之間的邊ei的集合.

對(duì)于用圖模型G表示的網(wǎng)絡(luò)基礎(chǔ)設(shè)施,令A(yù)表示有權(quán)重圖的鄰接矩陣.A(i,j)表示邊eij=(vi,vj)上的權(quán)重.基于隨機(jī)游走的概念,在圖G上的影響力擴(kuò)散是指從某一節(jié)點(diǎn)v0出發(fā),并按一定概率在圖上沿節(jié)點(diǎn)和邊隨機(jī)移動(dòng).假設(shè)目前第vs步的隨機(jī)游走在節(jié)點(diǎn)s+1上,則第s+1步將以概率Pst移動(dòng)到vs的某一相鄰節(jié)點(diǎn)vt上,即vt∈N(vs),其中N(vs)表示節(jié)點(diǎn)vs在圖G上的所有相鄰節(jié)點(diǎn)的集合,其轉(zhuǎn)移概率Pst=A(s,t)/∑vk∈N(vs)A(s,k),所經(jīng)過(guò)的節(jié)點(diǎn)路徑組成一個(gè)馬爾科夫鏈.令D表示一個(gè)對(duì)角矩陣,其中對(duì)角線上某個(gè)值d(s)=∑vk∈N(vs)A(s,k),則對(duì)應(yīng)的馬爾科夫鏈的轉(zhuǎn)移概率矩陣P的矩陣表示為P=D-1A.從節(jié)點(diǎn)vj到節(jié)點(diǎn)vk的長(zhǎng)度為l的概率Qjk可以通過(guò)轉(zhuǎn)移矩陣P經(jīng)過(guò)l次乘積后相應(yīng)位置上的對(duì)應(yīng)元素來(lái)表示,故Q=(Qjk)=Pl.

當(dāng)G為非二項(xiàng)圖時(shí),由于馬爾科夫鏈的無(wú)記憶性,從任何節(jié)點(diǎn)出發(fā),經(jīng)過(guò)無(wú)限步的影響度最后落在同一個(gè)節(jié)點(diǎn)vk的概率只和最終節(jié)點(diǎn)的度的大小有關(guān).可以通過(guò)返回概率c,將影響度傾向于在出發(fā)節(jié)點(diǎn)的周?chē)木植康倪B接關(guān)系,同時(shí)只考慮長(zhǎng)度為l的隨機(jī)游走,即鄰域影響度所能達(dá)到的節(jié)點(diǎn)與出發(fā)的節(jié)點(diǎn)的最短路徑長(zhǎng)度不超過(guò)l.值得注意的是,本文中提出的算法可以根據(jù)不同需要自由地增大l以擴(kuò)大鄰域的范圍.

定義1鄰域影響度:若隨機(jī)游走的長(zhǎng)度為l,則節(jié)點(diǎn)vj到節(jié)點(diǎn)vk的鄰域影響度(影響力)為

其中,0

由此可知鄰域影響度的矩陣可表示為:

(1)

根據(jù)鄰域影響度(影響力)矩陣,重要網(wǎng)元節(jié)點(diǎn)的重要性可定義為

S(vj)=∑vk∈VΠjk,

(2)

其中,重要性分值S(vj)表示節(jié)點(diǎn)vj的影響力.是根據(jù)重要節(jié)點(diǎn)對(duì)其他節(jié)點(diǎn)的影響力,即鄰域影響度長(zhǎng)度的總和來(lái)決定.

式(2)定義網(wǎng)絡(luò)基礎(chǔ)設(shè)施圖模型G上的重要性,為了同時(shí)考慮承載業(yè)務(wù)的重要性,本文中提出將業(yè)務(wù)也轉(zhuǎn)換為圖模型上的點(diǎn),如圖1所示.假設(shè)網(wǎng)絡(luò)基礎(chǔ)設(shè)施中的業(yè)務(wù)有{w1,w2,w3,…}.每種業(yè)務(wù)wj在圖上都映射相應(yīng)的節(jié)點(diǎn)wj.如果某網(wǎng)元承載某業(yè)務(wù),則在圖上增加連接網(wǎng)元對(duì)應(yīng)節(jié)點(diǎn)vi到業(yè)務(wù)對(duì)于節(jié)點(diǎn)wj的一條邊e(vi,wj).這樣生成的包括業(yè)務(wù)信息的圖模型用G′表示.在圖G′上利用鄰域影響度來(lái)統(tǒng)一衡量節(jié)點(diǎn)的重要性,可同時(shí)衡量連接關(guān)系的重要性和關(guān)于業(yè)務(wù)的重要性.對(duì)于業(yè)務(wù)的級(jí)別,可以通過(guò)給邊e(vi,wj)賦予相應(yīng)的權(quán)重,為簡(jiǎn)化描述,本文中假設(shè)所有業(yè)務(wù)級(jí)別都一樣,即相應(yīng)的邊的權(quán)重為1.下文中將不區(qū)分G′和G,兩者都表示包括業(yè)務(wù)信息的圖模型.

圖1 業(yè)務(wù)轉(zhuǎn)化為圖上的節(jié)點(diǎn)Fig.1 Service vertices in the graph

網(wǎng)元節(jié)點(diǎn)重要性評(píng)估算法步驟為:

1) 計(jì)算轉(zhuǎn)移概率矩陣P.將業(yè)務(wù)轉(zhuǎn)化為圖上業(yè)務(wù)節(jié)點(diǎn),利用圖上網(wǎng)元節(jié)點(diǎn)的鄰接關(guān)系和網(wǎng)元承載業(yè)務(wù)情況得到鄰接矩陣A,根據(jù)P=D-1A計(jì)算轉(zhuǎn)移概率矩陣P.

2) 計(jì)算影響力距離矩陣Π.設(shè)置合適的隨機(jī)游走長(zhǎng)度l和隨機(jī)游走的重啟概率c,根據(jù)式(1) 計(jì)算Π.

3) 根據(jù)式(2) 計(jì)算網(wǎng)元節(jié)點(diǎn)的重要性分值.

4) 生成重要網(wǎng)元節(jié)點(diǎn)列表.重要性分值大于ξ的網(wǎng)元節(jié)點(diǎn)稱為重要節(jié)點(diǎn),其中ξ表示重要網(wǎng)元節(jié)點(diǎn)重要性的閾值.圖2所示的是基于本文中實(shí)驗(yàn)部分?jǐn)?shù)據(jù)集的網(wǎng)絡(luò)基礎(chǔ)設(shè)施圖G上的網(wǎng)元重要性的分布情況.通過(guò)對(duì)網(wǎng)元節(jié)點(diǎn)影響力的曲線擬合,可見(jiàn)網(wǎng)元節(jié)點(diǎn)影響力分布曲線與冪律分布函數(shù)y=1.72x-0.06-1的曲線基本吻合,遵循冪律(power law)分布,因此確定重要節(jié)點(diǎn)的重要性的閾值ξ并不是絕對(duì)的,而是相對(duì)的.在下文3.2節(jié)對(duì)ξ的取值進(jìn)行了討論.

圖2 網(wǎng)元節(jié)點(diǎn)影響力分布曲線Fig.2 The curve of vertex influence distribution

由于評(píng)估節(jié)點(diǎn)重要性需要對(duì)兩個(gè)矩陣進(jìn)行乘積,所以整體的時(shí)間復(fù)雜度是O(ln3),其中n是圖中的網(wǎng)元個(gè)數(shù).在實(shí)際應(yīng)用中,可以利用快速稀疏矩陣乘法來(lái)代替通常的矩陣相乘算法以加快計(jì)算速度.

2 生成重要網(wǎng)元子圖

重要網(wǎng)元子圖應(yīng)包括重要網(wǎng)元節(jié)點(diǎn)和與重要網(wǎng)元節(jié)點(diǎn)相似度較大的節(jié)點(diǎn),即被重要節(jié)點(diǎn)影響大的節(jié)點(diǎn),有如下幾個(gè)特點(diǎn):1) 重要網(wǎng)元子圖應(yīng)該是一個(gè)連通圖;2) 重要網(wǎng)元子圖應(yīng)該包括重要節(jié)點(diǎn);3) 重要網(wǎng)元子圖應(yīng)該包括被重要節(jié)點(diǎn)影響的節(jié)點(diǎn).

本文中提出了一個(gè)類似高維空間中密度聚類思想的擴(kuò)展策略,從重要網(wǎng)元節(jié)點(diǎn)擴(kuò)展出網(wǎng)元子圖.生成重要網(wǎng)元子圖的算法步驟如下:

1) 從重要網(wǎng)元節(jié)點(diǎn)列表中選擇當(dāng)前重要性分值最大的網(wǎng)元vj,初始化子圖gs為空,并將該網(wǎng)元插入到空節(jié)點(diǎn)圖中,從重要網(wǎng)元節(jié)點(diǎn)列表中刪除vj,標(biāo)記vj為已訪問(wèn)節(jié)點(diǎn),設(shè)置子圖擴(kuò)展的停止條件閾值ε,計(jì)算公式為:

ε=max(Π(j,∶))×rlb，

其中rlb的取值為冪律分布曲線的拐點(diǎn)位置.

2) 初始化最大堆H,將所有未被訪問(wèn)過(guò)的重要網(wǎng)元vj的相鄰節(jié)點(diǎn)vm和影響力值Πjm插入到最大堆H中.

3) 從最大堆H的堆頂獲取當(dāng)前影響力最大值節(jié)點(diǎn)vk和其影響力值,若該影響力值大于閾值ε,將所有未被訪問(wèn)過(guò)的vk的相鄰節(jié)點(diǎn)vm和影響力值Πkm插入到最大堆H中,同時(shí)將vk加入到圖gs中,標(biāo)記vk為已訪問(wèn),如果節(jié)點(diǎn)vk是重要網(wǎng)元,更新閾值ε,更新公式為:

ε=max(Π(k,∶))×rlb.

重復(fù)步驟3),若該影響力值小于閾值ε,則將當(dāng)前生成的子圖gs加入到重要網(wǎng)元子圖集合Gs中;若重要網(wǎng)元節(jié)點(diǎn)列表不為空,返回步驟1);否則進(jìn)行步驟4).

4) 融合重要網(wǎng)元子圖.遍歷重要網(wǎng)元子圖集合Gs,若兩個(gè)重要網(wǎng)元子圖存在節(jié)點(diǎn)在原圖上是直接相連的,將兩個(gè)網(wǎng)元子圖合并成一個(gè)網(wǎng)元子圖.

生成重要網(wǎng)元子圖的算法從重要網(wǎng)元節(jié)點(diǎn)出發(fā),通過(guò)擴(kuò)展重要網(wǎng)元來(lái)生成重要網(wǎng)元子圖.步驟2)和3)使用最大堆來(lái)維持影響力大的節(jié)點(diǎn),每次從最大堆H中取出第一個(gè)節(jié)點(diǎn)加入到當(dāng)前的重要網(wǎng)元子圖gs中.檢查是否結(jié)束當(dāng)前重要網(wǎng)元子圖gs的擴(kuò)展的判斷條件是當(dāng)前網(wǎng)元子圖gs中的所有節(jié)點(diǎn)對(duì)待擴(kuò)展節(jié)點(diǎn)的影響力是否小于閾值ε.閾值ε為最后加入到網(wǎng)元子圖的重要節(jié)點(diǎn)對(duì)圖上其他節(jié)點(diǎn)的影響力的最大值的rlb倍.由于影響力距離遵循冪律分布,rlb的取值為冪律分布曲線的拐點(diǎn)位置,在本文中根據(jù)實(shí)驗(yàn)中的具體冪律分布情況,rlb的值為0.2.在步驟4)中,對(duì)于生成的重要網(wǎng)元子圖集合,如果兩個(gè)重要網(wǎng)元子圖存在節(jié)點(diǎn)在原圖上是直接相連的,那么這兩個(gè)網(wǎng)元子圖將被合并成一個(gè)網(wǎng)元子圖.

3 實(shí)驗(yàn)結(jié)果與分析

本文中實(shí)驗(yàn)所使用的運(yùn)行環(huán)境為OS X 10.10.5,CPU為Intel i5 1.6 GHz,內(nèi)存為4 GB,算法的實(shí)現(xiàn)基于Python語(yǔ)言.在所有實(shí)驗(yàn)中,使用的隨機(jī)游走的返回概率為0.15.

3.1 數(shù)據(jù)集

本研究在數(shù)據(jù)集SNAP1N、SNAP1U、SNAP2N、SNAP2U上進(jìn)行實(shí)驗(yàn).這4個(gè)數(shù)據(jù)集由數(shù)據(jù)集SNAP1和SNAP2生成，數(shù)據(jù)集SNAP1和SNAP2均來(lái)源于俄勒岡大學(xué)路由查看計(jì)劃,來(lái)自Stanford大學(xué)的SNAP項(xiàng)目(https:∥snap.stanford.edu/data/).兩個(gè)數(shù)據(jù)集的基本特征如表1所示.

表1 數(shù)據(jù)集特征

數(shù)據(jù)集中每個(gè)節(jié)點(diǎn)代表一個(gè)自治系統(tǒng)(如路由),自治系統(tǒng)之間的通信遵循邊界網(wǎng)關(guān)協(xié)議,基于邊界網(wǎng)關(guān)協(xié)議的日志消息可以構(gòu)建自治系統(tǒng)之間的通信網(wǎng)絡(luò)拓?fù)鋱D.由于SNAP1和SNAP2中并沒(méi)有網(wǎng)元所承載的業(yè)務(wù)信息,本研究中在其上疊加了合成的業(yè)務(wù)數(shù)據(jù).假設(shè)有100種不同的業(yè)務(wù),對(duì)于每個(gè)節(jié)點(diǎn),允許其承載10個(gè)不同的業(yè)務(wù),承載的業(yè)務(wù)的數(shù)量有均勻分布和正態(tài)分布兩種情況.隨機(jī)地從100種業(yè)務(wù)中選擇某節(jié)點(diǎn)所承載的具體業(yè)務(wù).通過(guò)對(duì)SNAP1和SNAP2疊加兩種不同的業(yè)務(wù)分布,共生成4個(gè)不同的數(shù)據(jù)集供實(shí)驗(yàn)中使用,后文用SNAP1U、SNAP1N、SNAP2U、SNAP2N表示.其中,SNAP1U表示在SNAP1上疊加均勻分布的業(yè)務(wù)數(shù)量,SNAP1N表示在SNAP1上疊加正態(tài)分布的業(yè)務(wù)數(shù)量.SNAP2的表示與之類似.

3.2 有效性

首先介紹如何衡量重要網(wǎng)元子圖的質(zhì)量.對(duì)于確定的某重要網(wǎng)元子圖Gs,可以利用式(3)來(lái)衡量重要網(wǎng)元子圖的質(zhì)量：

(3)

其中Π是影響力矩陣.∑vj,vk∈V(Gs),score(vj)≥ξΠjk表示重要網(wǎng)元子圖內(nèi)節(jié)點(diǎn)之間的影響力,∑vj∈V(Gs),vk∈V(G),score(vj)≥ξΠjk衡量了重要網(wǎng)元子圖內(nèi)的重要節(jié)點(diǎn)到子圖內(nèi)其他節(jié)點(diǎn)的影響力,Rcoverage值越高,說(shuō)明重要網(wǎng)元子圖內(nèi)捕捉到大部分重要節(jié)點(diǎn)的影響力越大.

圖3顯示了在數(shù)據(jù)集SNAP1U和SNAP1N上，對(duì)于不同的ξ找到的前10個(gè)重要網(wǎng)元子圖的Rcoverage的算術(shù)平均值.對(duì)于每個(gè)ξ,變化鄰域影響度的長(zhǎng)度為2～6.當(dāng)隨機(jī)游走的長(zhǎng)度為2時(shí),Rcoverage的算術(shù)平均值在兩個(gè)數(shù)據(jù)集上都只有0.3左右,這是因?yàn)殚L(zhǎng)度為2的隨機(jī)游走在圖上所能訪問(wèn)范圍過(guò)小,不足以捕捉重要節(jié)點(diǎn)的影響力.當(dāng)隨機(jī)游走的長(zhǎng)度超過(guò)3時(shí),發(fā)現(xiàn)兩個(gè)數(shù)據(jù)集上的Rcoverage的算術(shù)平均值都超過(guò)70%,例如對(duì)于長(zhǎng)度為5,ξ為85%時(shí),重要網(wǎng)元子圖內(nèi)的重要節(jié)點(diǎn)的影響力超過(guò)85%都在子圖內(nèi)部.

圖3 數(shù)據(jù)集SNAP1U和SNAP1N的RcoverageFig.3 Rcoverage of dataset SNAP1U and SNAP1N

圖中數(shù)值表示網(wǎng)元的編號(hào),下同.圖4 數(shù)據(jù)集SNAP1U和SNAP1N的重要網(wǎng)元子圖示例Fig.4 An element subgraph of dataset SNAP1U and SNAP1N

圖4展示了分別在數(shù)據(jù)集SNAP1U和SNAP1N上找到的重要網(wǎng)元子圖,其中隨機(jī)游走的長(zhǎng)度為4,ξ為85%，灰色節(jié)點(diǎn)表示重要網(wǎng)元子圖中的重要節(jié)點(diǎn).可見(jiàn),找到的重要網(wǎng)元子圖里包括相當(dāng)部分的重要節(jié)點(diǎn),也包括與重要節(jié)點(diǎn)相連的非重要節(jié)點(diǎn).尋找網(wǎng)元子圖的傳統(tǒng)方法是從同一時(shí)間窗口內(nèi)的每個(gè)故障網(wǎng)元出發(fā),以每個(gè)故障網(wǎng)元為中心,尋找與其路徑距離小于h的網(wǎng)元節(jié)點(diǎn).將故障網(wǎng)元以及這些故障網(wǎng)元的鄰接網(wǎng)元節(jié)點(diǎn)所構(gòu)成的子圖作為此故障網(wǎng)元的鄰域子圖，即為重要網(wǎng)元子圖.同一時(shí)間窗口內(nèi)的故障網(wǎng)元鄰域子圖如有重合,即包含相同節(jié)點(diǎn),則把重合的鄰域子圖合并.圖5展示了在數(shù)據(jù)集SNAP1U和SNAP1N上利用傳統(tǒng)的方法找到的與圖4對(duì)應(yīng)的網(wǎng)元子圖,即包括發(fā)生故障網(wǎng)元的鄰域子圖,其中鄰域子圖中的節(jié)點(diǎn)到發(fā)生故障節(jié)點(diǎn)的路徑長(zhǎng)度為2.可見(jiàn),傳統(tǒng)方法找到的網(wǎng)元子圖包括的節(jié)點(diǎn)遠(yuǎn)遠(yuǎn)多于本文中所找到的重要網(wǎng)元子圖中的節(jié)點(diǎn),會(huì)極大地增加運(yùn)維人員的負(fù)擔(dān).

3.3 運(yùn)行時(shí)間

圖5 數(shù)據(jù)集SNAP1U和SNAP1N的傳統(tǒng)網(wǎng)元子圖示例Fig.5 An element subgraph of dataset SNAP1U and SNAP1N

圖6 數(shù)據(jù)集的運(yùn)行時(shí)間Fig.6 The running time on datasets

本研究在4個(gè)數(shù)據(jù)集上都進(jìn)行了運(yùn)行時(shí)間的實(shí)驗(yàn),其中隨機(jī)游走的長(zhǎng)度為4和6,ξ為85%.圖6顯示了在SNAP1U、SNAP1N、SNAP2U、SNAP2N的運(yùn)行時(shí)間,包括長(zhǎng)度為4和6的隨機(jī)游走.運(yùn)行時(shí)間分兩部分,分別對(duì)應(yīng)評(píng)估網(wǎng)元節(jié)點(diǎn)的重要性和生成重要網(wǎng)元子圖.其中,SNAP1U和SNAP1N的實(shí)驗(yàn)結(jié)果對(duì)應(yīng)左邊的坐標(biāo)縱軸,SNAP2U和SNAP2N的實(shí)驗(yàn)結(jié)果對(duì)應(yīng)右邊的坐標(biāo)縱軸.由于評(píng)估網(wǎng)元重要性算法的時(shí)間復(fù)雜度為O(ln3),所以評(píng)估網(wǎng)元節(jié)點(diǎn)重要性所需的時(shí)間隨l的增加而增加.生成重要網(wǎng)元子圖算法是一個(gè)啟發(fā)式的算法,其時(shí)間復(fù)雜度與重要節(jié)點(diǎn)的個(gè)數(shù)以及重要節(jié)點(diǎn)的影響范圍有關(guān),但l的變化會(huì)影響重要節(jié)點(diǎn)的個(gè)數(shù),所以生成重要網(wǎng)元算法的時(shí)間也會(huì)隨l的變化而變化.由于生成重要網(wǎng)元子圖中要頻繁更新最大堆中所對(duì)應(yīng)的影響力值,其時(shí)間復(fù)雜度為O(logm),其中m是最大堆里的元素個(gè)數(shù),所以擴(kuò)展生成重要網(wǎng)元子圖的時(shí)間相對(duì)較長(zhǎng).

為了衡量算法的時(shí)間復(fù)雜度,本研究中分別選取不同節(jié)點(diǎn)數(shù),在數(shù)據(jù)集SNAP2N上進(jìn)行實(shí)驗(yàn).圖7顯示了在不同大小的圖上算法的運(yùn)行時(shí)間,其中隨機(jī)游走的長(zhǎng)度為4,ξ為85%.可見(jiàn),隨著節(jié)點(diǎn)數(shù)量的增加,計(jì)算網(wǎng)元重要性算法和生成重要網(wǎng)元子圖算法的運(yùn)行時(shí)間符合上面的復(fù)雜度分析,整體上呈多項(xiàng)式時(shí)間增長(zhǎng).當(dāng)節(jié)點(diǎn)數(shù)為2 000時(shí)，生成重要網(wǎng)元子圖步驟的變化也反映了啟發(fā)式算法的啟發(fā)策略對(duì)整體運(yùn)行時(shí)間的影響.

4 結(jié) 論

快速而準(zhǔn)確地確定重要網(wǎng)元子圖可以用于提高網(wǎng)絡(luò)基礎(chǔ)設(shè)施的運(yùn)維效率,降低運(yùn)維成本.本研究的主要貢獻(xiàn):1) 針對(duì)在大規(guī)模網(wǎng)絡(luò)基礎(chǔ)設(shè)施中確定面向業(yè)務(wù)的重要網(wǎng)元子圖的問(wèn)題,提出利用鄰域影響度來(lái)統(tǒng)一衡量網(wǎng)元在連接和業(yè)務(wù)兩方面的重要性;2) 給出了確定重要網(wǎng)元子圖的算法,利用類似密度聚類的思想,通過(guò)擴(kuò)展重要網(wǎng)元生成重要網(wǎng)元子圖;3) 在真實(shí)的網(wǎng)絡(luò)基礎(chǔ)設(shè)施數(shù)據(jù)集上,通過(guò)疊加合成的業(yè)務(wù)承載數(shù)據(jù)進(jìn)行了廣泛的實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果驗(yàn)證了提出的方法可以高效地找到高質(zhì)量的重要網(wǎng)元子圖,并將其用于網(wǎng)絡(luò)基礎(chǔ)設(shè)施的運(yùn)維.未來(lái)可能的研究方向包括利用其他影響力模型來(lái)構(gòu)建重要網(wǎng)元子圖,以及在動(dòng)態(tài)網(wǎng)絡(luò)基礎(chǔ)設(shè)施中如何維護(hù)所發(fā)現(xiàn)的重要網(wǎng)元子圖等.