朱 江,包崇明,王崇云,周麗華,孔 兵

(云南大學(xué) a.信息學(xué)院; b.軟件學(xué)院; c.生態(tài)學(xué)與環(huán)境學(xué)院,昆明 650091)

0 概述

近年來,網(wǎng)絡(luò)與人們生產(chǎn)生活的關(guān)系日益密切,網(wǎng)絡(luò)數(shù)量、規(guī)模及數(shù)據(jù)量均呈現(xiàn)出多元化、復(fù)雜化、海量化的發(fā)展趨勢。在此背景下,如何快速掌握網(wǎng)絡(luò)關(guān)鍵節(jié)點、獲取有效信息等成為進(jìn)一步提高生產(chǎn)生活效率和質(zhì)量的關(guān)鍵,例如關(guān)鍵節(jié)點對網(wǎng)絡(luò)輿情的控制、社交網(wǎng)絡(luò)影響力的分析、網(wǎng)絡(luò)安全薄弱點的發(fā)現(xiàn)、信息的快速傳播等有重要意義。

結(jié)構(gòu)洞的概念由BURT于2009年提出[1],其對個體在群體之中的關(guān)鍵位置進(jìn)行深入解釋和分析,認(rèn)為社會結(jié)構(gòu)中處在關(guān)鍵位置的個體將能夠獲得更多的競爭優(yōu)勢等,但真實網(wǎng)絡(luò)遠(yuǎn)比示例網(wǎng)絡(luò)要復(fù)雜得多,隨著研究的深入,對結(jié)構(gòu)洞的理解也不再局限于社區(qū)間信息流動的關(guān)鍵節(jié)點。

結(jié)構(gòu)洞發(fā)現(xiàn)算法不斷被提出,例如基于社區(qū)發(fā)現(xiàn)的算法[2-3],該類算法需要預(yù)先對社區(qū)進(jìn)行發(fā)現(xiàn)和檢測,在計算過程和周期上會變得復(fù)雜和冗長,同時結(jié)構(gòu)洞的質(zhì)量取決于社區(qū)發(fā)現(xiàn)的質(zhì)量;基于中心性算法和關(guān)鍵性排序算法的優(yōu)化算法[4](個性化PageRank[5]、中介中心性(Betweenness Centrality,BC)[6-7]、接近中心性(Closeness Centrality,CC)[8-9]等),該類算法能夠較快收斂,但精準(zhǔn)性相對較弱;此外,還有利用機(jī)器學(xué)習(xí)整合多項數(shù)據(jù)從而對關(guān)鍵節(jié)點排序的算法[10-11]。

本文主要從網(wǎng)絡(luò)結(jié)構(gòu)方面著手,提出基于最短路徑增量與中介中心性過濾的結(jié)構(gòu)洞發(fā)現(xiàn)算法(SNV-BC)。SNV算法通過最短路徑增量、連通分量個數(shù)(Number of Connected Components,NCC)、節(jié)點方差(VAR)等數(shù)據(jù)可精準(zhǔn)地區(qū)分節(jié)點的屬性差異,大幅提升算法結(jié)果的準(zhǔn)確性,但節(jié)點屬性的精準(zhǔn)計算導(dǎo)致了較高的時間成本。由于BC算法與SNV算法在變化趨勢上有著較高的一致性和相似度,BC算法計算的是某節(jié)點上所通過的最短路徑條數(shù),與最短路徑增量具有內(nèi)在一致性,且BC算法時間復(fù)雜度極低,因此本文利用BC算法進(jìn)行節(jié)點過濾,并通過SNV算法進(jìn)行結(jié)構(gòu)洞發(fā)現(xiàn)。

1 理論基礎(chǔ)

1.1 網(wǎng)絡(luò)模型定義

節(jié)點v的最短路徑和c(v)表示以該節(jié)點v為起點,到其他所有節(jié)點的最短路徑長度之和[12]。

(1)

圖G的最短路徑和c(G)表示圖G中所有節(jié)點的最短路徑長度之和[12]。

(2)

定義1(圖最短路徑增量) 圖中的任何節(jié)點都可能在一些節(jié)點對間的最短路徑上,因此如果移除這樣的節(jié)點,可能導(dǎo)致該節(jié)點對間的最短路徑增大甚至不可達(dá)(即無窮大)。如果越多的最短路徑通過這個節(jié)點,那么移除該節(jié)點后,各節(jié)點的最短路徑和勢必會增大,圖的最短路徑也將增加。因此,可以通過圖最短路徑增量(Shortest Path Increment of Graph,SPIG)來體現(xiàn)節(jié)點的重要性。

設(shè)G(Vv)表示從圖G中移除節(jié)點v并將其縮寫為Gv,那么SPIG可以表示為:

SPIG(vi)=c(Gvi)-(c(G)-c(vi))?

SPIG(vi)=c(Gvi)+c(vi)-c(G)

(3)

對于給定的網(wǎng)絡(luò)G,c(G)是一個常數(shù)。該常數(shù)對兩個節(jié)點之間的SPIG值的比較沒有影響。因此,使用SPIG′代替SPIG進(jìn)行比較,提高計算效率。

SPIG′(vi)=c(Gvi)+c(vi)?

SPIG′(vi)=c(Gvi)+c(vi)

(4)

定義2(連通分量個數(shù)) 連通分量個數(shù)是節(jié)點的屬性之一,表示移除節(jié)點后圖中連通分量的數(shù)量。通常給定的網(wǎng)絡(luò)圖G是一個連通圖,也就意味著NCC(G)=1。然而,移除圖G中的節(jié)點v可能會形成多個獨立的子連通分量。如圖1所示,NCC(Gv)=3,縮寫為NCC(v)=3,NCC(u)=3,NCC(w)=1。

圖1 NCC和節(jié)點方差的定義

定義3(節(jié)點方差) 節(jié)點方差也是節(jié)點的屬性之一。在移除節(jié)點v后,如果形成多個子連通分量,則VAR(v)等于各個子連通分量中節(jié)點數(shù)量的方差;否則VAR(v)為0。如圖1所示,VAR(v)=VAR[|C1|,|C2|,|C3|]=VAR[4,3,4]=0.222,VAR(w)=VAR[|C1|]=VAR[1]=0。

定義4(結(jié)構(gòu)洞屬性) 結(jié)構(gòu)洞屬性(SH)用于描述節(jié)點作為結(jié)構(gòu)洞的可能性大小。SH值越大,其作為結(jié)構(gòu)洞的可能性就越大。

1.2 問題描述與定義

給定網(wǎng)絡(luò)G=(V,E),結(jié)構(gòu)洞發(fā)現(xiàn)就是找到節(jié)點集合Vs(Vs?V),使得從圖G中移除集合Vs中的節(jié)點能夠?qū)е伦訄DGVs的最短路徑增量最大化。換言之,若移除節(jié)點v后SPIG值越大,則說明節(jié)點v的結(jié)構(gòu)洞屬性就越強。

目前,在社交網(wǎng)絡(luò)的研究中對于結(jié)構(gòu)洞還沒有明確的定義,但主要有兩個研究方向:一個是重疊社區(qū)部分節(jié)點[2,13-14];另一個是網(wǎng)絡(luò)中信息擴(kuò)散的關(guān)鍵節(jié)點[4,15],本文研究更傾向于后者。盡管存在兩個研究方向,但相同的是均認(rèn)為結(jié)構(gòu)洞是一種橋節(jié)點。一方面是橋接不同社區(qū),另一方面是信息傳播的關(guān)鍵橋梁。如圖2所示,3個虛線區(qū)域分別表示3個社區(qū),灰色節(jié)點直接制約著社區(qū)之間以及整個網(wǎng)絡(luò)的信息流動,因此其被視為具有結(jié)構(gòu)洞屬性。

圖2 結(jié)構(gòu)洞示意圖

定義5(結(jié)構(gòu)洞) 在網(wǎng)絡(luò)中,橋接不存在直接連接或直連程度較弱的多個社區(qū)(或節(jié)點群)的中介節(jié)點,刪除此類橋節(jié)點將導(dǎo)致信息擴(kuò)散成本和時間的增加,甚至信息的不可達(dá)。本文將制約網(wǎng)絡(luò)信息流動的一系列橋節(jié)點稱為結(jié)構(gòu)洞。

屬性1給定節(jié)點v和u,節(jié)點v橋接多個社區(qū),而節(jié)點u僅在社區(qū)內(nèi)連接,根據(jù)社區(qū)的特性[16],社區(qū)內(nèi)部連通性通常強于社區(qū)間的連通性,因此去除節(jié)點v對于信息擴(kuò)散的影響顯然要大于去除節(jié)點u的影響,v的結(jié)構(gòu)洞屬性值也將高于u。

屬性2給定節(jié)點v和u,節(jié)點v橋接多個社區(qū),節(jié)點u僅橋接少數(shù)幾個社區(qū)。去除節(jié)點v對于信息擴(kuò)散的影響顯然要大于去除節(jié)點u的影響,因此v的結(jié)構(gòu)洞屬性值也將高于u。

屬性3給定節(jié)點v和u,節(jié)點v橋接兩個較大的社區(qū),節(jié)點u橋接兩個較小的社區(qū)或一大一小的社區(qū)。對于整個網(wǎng)絡(luò)的信息擴(kuò)散而言,移除節(jié)點v比移除u的影響更大,因此節(jié)點v具有比u更高的結(jié)構(gòu)洞屬性值。

屬性4在上述3個定義中,如果移除節(jié)點后能夠形成更多的社區(qū),則說明該節(jié)點可以將信息傳播到更多的社區(qū),因此更關(guān)鍵。其次是社區(qū)中節(jié)點的數(shù)量,節(jié)點的數(shù)量越多,信息擴(kuò)散的范圍就越大。因此,一個節(jié)點只具有屬性2的影響力通常強于只具有屬性3的影響力,并強于只具有屬性1的影響力。

根據(jù)定義1,SPIG的計算依賴于連通圖。如果一個節(jié)點被移除,可以將整個圖分割成多個子連通分量,并且不同連通分量的節(jié)點間將是不可達(dá)的,因此無法計算得到SPIG值,從而不能獲得更有效的SH值。目前,有一部分算法是通過使用極大值來代替無窮遠(yuǎn)來解決該問題[4]。但如果在圖中有更多的節(jié)點,或者在刪除節(jié)點之后產(chǎn)生更多的子連通分量,則極值會被多次迭代計算,這將嚴(yán)重影響計算復(fù)雜度和時間復(fù)雜度,并且值過大會將一些有用的信息覆蓋。因此,本文提出一種基于SPIG、NCC和VAR的結(jié)構(gòu)洞發(fā)現(xiàn)算法。

2 SNV-BC結(jié)構(gòu)洞發(fā)現(xiàn)算法

2.1 算法原理

本文提出的SNV-BC算法是通過遍歷刪除每個節(jié)點,從而計算每個節(jié)點的SPIG、NCC、VAR值,然后分別對這3類值進(jìn)行歸一化并將其合并得到各節(jié)點的SH屬性值,最終根據(jù)該值進(jìn)行排序得到Top-k結(jié)構(gòu)洞。但在刪除節(jié)點后如果形成多個連通分量,SPIG值將無法計算,于是通過NCC和VAR來補充數(shù)據(jù)。本文選擇NCC是因為SNV-BC算法不依賴于社區(qū)發(fā)現(xiàn),所以使用連通分量個數(shù)來代替可能的社區(qū)數(shù)量。換言之,將移除節(jié)點后形成的這些連通分量視為相應(yīng)數(shù)量的獨立社區(qū),根據(jù)屬性2可以得出,如果NCC值越大,那么該節(jié)點的SH屬性也就越高。

如果一個節(jié)點連接著一個葉子節(jié)點(度等于1的節(jié)點),那么根據(jù)上文的思路和定義,移除該節(jié)點后這個葉節(jié)點也是一個單獨的連通分量,同樣會被視為一個可能的社區(qū)。如圖1所示,節(jié)點u和葉節(jié)點p的關(guān)系就屬于此情況。這顯然是不可行的,將會影響與其他NCC值相同節(jié)點的比較,因此提出一個簡單的圖優(yōu)化處理辦法,其將圖中的葉節(jié)點全部提前去除。

對于將其分別刪除后所形成連通分量數(shù)量相等的兩個節(jié)點,則通過其離心程度來確定其SH屬性高低。離心程度通常由eccentricity值來衡量[17],但由于小世界模型的原因[18-19],eccentricity值的區(qū)分度非常低,本文提出使用各連通分量中節(jié)點數(shù)的方差來代替,方差越大說明該節(jié)點的離心程度越大,在網(wǎng)絡(luò)中意味著節(jié)點更靠近網(wǎng)絡(luò)的邊緣;反之,節(jié)點的方差越小越靠近網(wǎng)絡(luò)中心,在其他條件相同的情況下,顯然靠近網(wǎng)絡(luò)中心的節(jié)點SH屬性值應(yīng)該高于邊緣節(jié)點。該性質(zhì)其實就是屬性3的體現(xiàn)。如圖1所示,分別移除節(jié)點u和v,有NCC(u)=NCC(v)=3。對應(yīng)各連通分量中的節(jié)點數(shù),移除節(jié)點u為(4,3,4),移除節(jié)點v為(2,1,8),進(jìn)而VAR(u)=0.222,VAR(v)=9.556,VAR(u) < VAR(v),即節(jié)點u的SH屬性值要強于節(jié)點v?？梢钥闯?節(jié)點u的位置相對于v要更靠近網(wǎng)絡(luò)中心,因此對于信息擴(kuò)散影響和關(guān)鍵性而言,節(jié)點u要大于節(jié)點v。

在得到這3項重要數(shù)據(jù)后,為便于綜合比較需要將其歸并。歸并前需要進(jìn)行歸一化處理,NCC和SPIG都是正相關(guān),而VAR是負(fù)相關(guān),因此VAR的歸一化需要先取其倒數(shù),分別用NCCnorm、VARnorm、SPIGnorm表示其歸一化后的數(shù)據(jù):

(5)

(6)

(7)

按照式(8)進(jìn)行合并:

SH(v)=α·NCCnorm(v)+β·(SPIGnorm(v)+

VARnorm(v))

(8)

在式(8)中,SPIGnorm和VARnorm值有且只能存在其中一個,VARnorm是在SPIGnorm無法計算時作為補充,因此將SPIGnorm和VARnorm作為整體統(tǒng)一調(diào)整,α、β作為NCCnorm、VARnorm、SPIGnorm的調(diào)整參數(shù)(0<α<1,0<β<1),其目的是為了控制各成分在最終結(jié)果中的比重。

為確定具體參數(shù),本文分別選取(0.2,0.8),(0.4,0.6),(0.5,0.5),(0.6,0.4),(0.8,0.2)5組取值方案進(jìn)行實驗驗證。通過最終結(jié)果對比發(fā)現(xiàn),α、β取值對于最終排序結(jié)果的影響較小,僅對數(shù)據(jù)差異性存在一定影響。針對本文所用的數(shù)據(jù)集,α、β分別取0.6、0.4時其區(qū)分性較好。對于其他網(wǎng)絡(luò)數(shù)據(jù)集,網(wǎng)絡(luò)中的弱聯(lián)系越多,不可達(dá)情況較高時,α應(yīng)適當(dāng)增大;反之,網(wǎng)絡(luò)的連通性越強且越趨向于強聯(lián)通時,β應(yīng)適當(dāng)增大。

2.2 基于BC算法的過濾原理

由于SNV算法是基于最短路徑增量來確定節(jié)點的結(jié)構(gòu)洞屬性強弱,而最短路徑的計算又依賴于對整個數(shù)據(jù)集節(jié)點的遍歷,同時由于增量是刪除不同節(jié)點后不同的差值,因此需要的迭代計算量隨著數(shù)據(jù)集規(guī)模的增大呈現(xiàn)出指數(shù)級的增加。因此,嘗試提前對數(shù)據(jù)集中的節(jié)點進(jìn)行過濾和篩選處理,從而降低計算量,提高算法效率。根據(jù)已有研究和實驗,發(fā)現(xiàn)SNV算法的準(zhǔn)確性相較于BC算法要高很多,但在多數(shù)情況下,兩算法的變化趨勢較為相似和一致。究其原因,SNV算法主要考慮節(jié)點刪除后最短路徑的增量,BC算法主要關(guān)注節(jié)點上最短路徑經(jīng)過的次數(shù)。最短路徑經(jīng)過的次數(shù)越多,在刪除該節(jié)點后,最短路徑增量必然也就更大。因此,從內(nèi)在屬性上有著較高的關(guān)聯(lián)性,同時BC算法具有較高的計算效率,利用BC算法進(jìn)行過濾處理具有理論可能性。需要強調(diào)的是,過濾是對下一個需要處理節(jié)點的挑選過程,即不再計算被過濾掉的節(jié)點的最短路徑增量,數(shù)據(jù)集和圖結(jié)構(gòu)仍然保持完整,對于被選擇節(jié)點最短路徑增量的計算沒有影響。

Top-k節(jié)點的發(fā)現(xiàn)算法中節(jié)點的排序結(jié)果尤為重要和關(guān)鍵。節(jié)點排序越靠前代表其作用和價值也越高,同時隨著節(jié)點排序位置的增加節(jié)點價值也隨之降低,并且在多數(shù)情況和環(huán)境下,并不是按線性趨勢降低,而是幾何級的快速降低。針對本文實驗所用數(shù)據(jù)集大小和需求,將過濾閾值設(shè)定為2.5%(即只對前2.5%節(jié)點進(jìn)行計算比較),同時最低不低于50個節(jié)點。該閾值可根據(jù)不同的需求進(jìn)行調(diào)整。

2.3 算法偽代碼

算法1SNV-BC結(jié)構(gòu)洞發(fā)現(xiàn)算法

輸入無向圖G=(V,E)

輸出該無向圖中每個節(jié)點的SH屬性值

1.Get Vpassby invoking Procedure 3;

/*通過調(diào)用程序3獲取被過濾的節(jié)點集合*/

2.Let n=|V|n=|V|;

3.For i ← 1 to n do:

4.If vinot in Vpassthen:

/* 只計算未被過濾的節(jié)點*/

5.Calculate SPIG,VAR and NCC of viby invoking Procedure 1;

/*通過調(diào)用程序1計算SPIG、VAR、NCC */

6.Else

7.SH(vi) ← 0;

8.End if

9.End for

10.For i ← 0 to n do:

/*歸一化各節(jié)點SPIG,VAR,NCC并求得SH值*/

11.get NCCnorm[vi]NCCnorm[vi]←(NCC(vi)-NCCmin)/(NCCmax-NCCmin) by formula(5);

12.get SPIGnorm[vi] by formula(6);

13.get VARnorm[vi]VARnorm[vi]←(1/VAR(v)-(1/VAR)min)/(1/VAR)max-(1/VAR)min) by formula(7);

14.get SH[vi] by formula(8);

15.End for

16.sort SH

17.Return set SH

程序1計算節(jié)點SPIG,VAR,NCC值的偽代碼

輸入無向圖G=(V,E)中的節(jié)點v

輸出由該節(jié)點的NCC,VAR,SPIG組成的字典值vertex_info

1.Let the dictionary data vertex_info ← ?

2.G.remove (v);/*將節(jié)點v從圖G中移除*/

3.NCC ← nx.number_connected_components (G);

/*計算連通分量個數(shù)*/

4.If NCC==1 then:

5.SPIG′ ← c(Gv) + c(v);

/*通過調(diào)用程序2計算相應(yīng)的c(x)*/

6.VAR ← 0;

7.Else if NCC > 1 then:

8.SPIG’ ← 0;

9.For i←1 to NCC do:

10.NVCC[i]← the number of vertices in each connected component;

/*統(tǒng)計各子連通分量節(jié)點數(shù)*/

11.VAR ← calculate the variance of NVCC;

/*計算各子連通分量節(jié)點數(shù)的方差*/

12.Add NCC,VAR and SPIG to vertex_info

13.Return the dictionary vertex_info

程序2計算最短路徑c(x)的偽代碼

輸入無向圖G=(V,E)、節(jié)點對(v,u)、節(jié)點v

輸出圖的最短路徑和c(G)、節(jié)點v和u之間的最短路徑c(v,u)、節(jié)點v的最短路徑和c(v)

1.Def BCSP (i,j):

/*通過鄰接表計算節(jié)點對之間的最短路徑 */

2.SP ← shortest_path (i,j);

3.Return SP

4.Def VSP (v):

/*通過調(diào)用BCSP計算單源節(jié)點的最短路徑和 */

5.For i←1 to |V| do:

6.SP ← SP + BCSP (v,i);

7.End for

8.Return SP

9.Def NSP (G):

/*通過調(diào)用VSP計算圖的最短路徑和 */

10.For i←1 to |V| do:

11.SP ← SP + VSP (i);

12.End for

13.Return SP

14.If input is a vertices pair (v,u) then:

/*根據(jù)輸入類型進(jìn)行對應(yīng)計算 */

15.SP ← BCSP (v,u);

16.Elseif input is a vertex v then:

17.SP ← VSP (v);

18.Elseif input is a network G then:

19.SP ← NSP (G);

20.End if

21.Return SP

程序3中介中心性算法過濾篩選的偽代碼

輸入無向圖G=(V,E)

輸出優(yōu)化后被過濾的節(jié)點集合Vpass

1.Let n=|V|;

2.k=0.025*n;

/*通過閾值確定選取節(jié)點數(shù)*/

3.If k<50:

/*將節(jié)點數(shù)最低值設(shè)為50*/

4.k=50;

5.End if

6.Get BC_value=betweenness_centrality(G);

7.sort BC_value;

8.For i ←k to n do:

/*將閾值以后的節(jié)點加入到Vpass中*/

9.Add vertex vito set Vpass

10.End for

11.Return set Vpass

2.4 算法時間復(fù)雜度

單源節(jié)點的最短距離之和c(v)的時間復(fù)雜度為O(n),圖的最短距離之和c(G)的時間復(fù)雜度為n×O(c(v))=n×O(n)=O(n2),因此程序1的時間復(fù)雜度為O(n2)+O(n)=O(n2)。整個算法通過過濾篩選,運行時僅需遍歷篩選出的50個節(jié)點,需要調(diào)用50次程序1,因此算法的時間復(fù)雜度為50×O(n2)=O(n2),相較于未過濾篩選前的時間復(fù)雜度n×O(n2)=O(n3)有顯著的提升和改善。

圖3為BC算法過濾前后運行耗時情況對比。可以看出,經(jīng)過優(yōu)化過濾后,算法耗時減少,同時算法過濾性能較好。

圖3 BC算法過濾前后運行時間對比

3 實驗結(jié)果與分析

3.1 實驗環(huán)境設(shè)定

如表1所示,選取了5個不同類型和規(guī)格的網(wǎng)絡(luò),包括真實數(shù)據(jù)網(wǎng)絡(luò)和人工合成網(wǎng)絡(luò),其中Coauthor網(wǎng)絡(luò)較小。本文預(yù)先對結(jié)構(gòu)洞的節(jié)點進(jìn)行人工標(biāo)注,然后利用NDCG[20]評估方法對各算法的排序結(jié)果進(jìn)行打分,從而評估算法的有效性。人工合成網(wǎng)絡(luò)使用LFR[21]發(fā)生器進(jìn)行生成。合成網(wǎng)絡(luò)規(guī)模較大,無法人工標(biāo)注結(jié)構(gòu)洞,也難以進(jìn)行直觀的觀察和比較,因此通過SIR[22]模型進(jìn)行評價和比較。

表1 網(wǎng)絡(luò)數(shù)據(jù)集

NDCG是常用的排序結(jié)果評價算法。當(dāng)通過算法得出相應(yīng)的排序結(jié)果后,可以通過NDCG來計算該排序結(jié)果相對于標(biāo)準(zhǔn)結(jié)果的準(zhǔn)確度。NDCG@n表示取前n位排序結(jié)果進(jìn)行準(zhǔn)確度計算。

SIR是經(jīng)典的傳染病模型,其中,S(Susceptible)表示易感者,I(Infective)表示感染者,R(Recovered)表示免疫者。易感者與感染者接觸后以一定概率α變?yōu)楦腥菊?感染者每周期以一定概率β被治愈,并產(chǎn)生免疫力,變?yōu)槊庖哒?。后被引入到信息傳播研究中。在實驗?將不同算法得到的有序關(guān)鍵節(jié)點作為初始感染節(jié)點,運用SIR模型在相應(yīng)網(wǎng)絡(luò)上進(jìn)行感染實驗,比較網(wǎng)絡(luò)中的感染范圍和感染時間,從而比較和說明算法的優(yōu)劣。感染范圍越大,達(dá)到最大感染范圍所需時間越短,說明擴(kuò)散效率越高,節(jié)點關(guān)鍵性也越高。

LFR算法由LANCICHINETTI等人于2008年提出[21]。通過該算法能夠生成一種標(biāo)準(zhǔn)測試網(wǎng)絡(luò)?，F(xiàn)實網(wǎng)絡(luò)數(shù)據(jù)集中的節(jié)點度服從冪律分布,利用該算法生成的網(wǎng)絡(luò)同樣服從冪律分布規(guī)律和特點,因此利用LFR生成的網(wǎng)絡(luò)結(jié)構(gòu)來模擬真實網(wǎng)絡(luò)進(jìn)行實驗。

為評估本文算法,選取了個性化的PageRank算法PersonalRank以及其他基于最短路徑的經(jīng)典算法進(jìn)行比較:

1)PersonalRank算法[23](為與PageRank區(qū)分,記為PPR):其與目前使用較為廣泛的個性化PageRank算法最大的差異在于隨機(jī)游走過程中節(jié)點的初始訪問概率,PageRank始終以1/N概率運行(N為節(jié)點總數(shù))[5],PPR則是根據(jù)設(shè)定選擇相應(yīng)的根節(jié)點開始游走(本文中該算法的根節(jié)點選取為網(wǎng)絡(luò)的中心節(jié)點,即離心率最小的節(jié)點)。最終通過多輪迭代計算賦予每個節(jié)點相應(yīng)的得分,迭代中隨機(jī)跳轉(zhuǎn)的參數(shù)為0.85,直到得分收斂穩(wěn)定為止。最終選擇Top-k個PPR分值較高的節(jié)點。

2)BC算法[6-7]:一個節(jié)點擔(dān)任圖中任意兩個節(jié)點之間SP的橋梁次數(shù)或比例。最終選擇Top-k個中心性排序較高的節(jié)點。

3)CC算法[8]:一個節(jié)點到其他節(jié)點的最短路徑的平均長度。平均路徑越小,中心性越高。最終選擇Top-k個中心性排序較高的節(jié)點。

4)Harmonic接近中心性算法(Harmonic Closeness Centrality,HCC)[9]:其是接近中心性算法的優(yōu)化算法之一。最終選擇Top-k個中心性排序較高的節(jié)點。

所有實驗均在英特爾(R)酷睿TMI7-6700 3.4 GHz CPU,16 GB RAM,Windows 10企業(yè)的操作系統(tǒng)上進(jìn)行,代碼運行平臺是Anaconda的Python 2.7。

3.2 算法有效性分析

本文首先對過濾有效性進(jìn)行實驗分析,分別利用SNV-BC和SNV算法對表1中的各數(shù)據(jù)集進(jìn)行計算,得到兩個不同的節(jié)點序列rank_SNV-BC和rank_SNV。其中rank_SNV作為對應(yīng)基準(zhǔn),再根據(jù)NDCG@n(rank_SNV-BC,rank_SNV)進(jìn)一步計算得到rank_SNV-BC的NDCG評分,從而判斷排序的相似情況。

如圖4所示,5組評分分別對應(yīng)表1中各數(shù)據(jù)集,每組中的5項數(shù)據(jù)分別代表Top-10、Top-20、Top-30、Top-40、Top-50節(jié)點序列的NDCG(rank_SNV-BC,rank_SNV)評分,滿分為1,表示過濾前后的節(jié)點排序完全相同。從評分情況來看,Coauthor網(wǎng)絡(luò)數(shù)據(jù)集的各項均為滿分1。LFR-500、LFR-1000、LFR-1500、LFR-2000數(shù)據(jù)集在過濾前后不同的排序段均保持較高的NDCG評分,說明過濾前后節(jié)點序列能夠高度吻合,從而進(jìn)一步說明SNV-BC的過濾算法是有效和可行的。

圖4 BC算法過濾前后節(jié)點序列的NDCG評分

如圖5所示,Coauthor網(wǎng)絡(luò)是從C-DBLP科研合作網(wǎng)中提取的一個連通子集[10]。為顯示數(shù)據(jù)對比情況,用不同的顏色深度和直徑大小表示節(jié)點的SH值大小。

圖5 Coauthor網(wǎng)絡(luò)

從圖5可以看出,SH值與節(jié)點結(jié)構(gòu)關(guān)鍵性的吻合度較高。下文分別采用NDCG@2、NDCG@4、NDCG@6、NDCG@8進(jìn)一步進(jìn)行評價。在評價前,需要對網(wǎng)絡(luò)關(guān)鍵節(jié)點進(jìn)行實際標(biāo)注,標(biāo)注的依據(jù)為網(wǎng)絡(luò)中節(jié)點所對應(yīng)作者的真實影響力大小。各算法計算得到的Top-8節(jié)點以及人工標(biāo)記排序的Top-8節(jié)點如表2所示,括號中的排序評分用于NDCG計算。

表2 Top-8節(jié)點編號(評分)

圖6是Coauthor網(wǎng)絡(luò)的各算法排序的NDCG,分別給出各算法在不同NDCG@n下NDCG評分對比。從圖6可以看出,本文提出的SNV-BC算法在該網(wǎng)絡(luò)中效果明顯優(yōu)于PPR、CC、HCC,僅在部分情況下略低于BC,其主要原因為SNV-BC對于節(jié)點4的排序較為靠前,這是由該網(wǎng)絡(luò)的結(jié)構(gòu)特殊性以及該算法對于子連通分量的過濾較為簡單所造成。在移除節(jié)點4后,形成{1,2,3},{5,6},{8,9,12,11,13,10,…}3個子連通分量,明顯要多于移除節(jié)點26,36,10的子連通分量的數(shù)量。因此,本文提出的算法對節(jié)點4的排序較為靠前。對此進(jìn)行優(yōu)化和完善也是后續(xù)工作的方向之一,例如加強對子連通分量的過濾。盡管部分情況下效果略低于BC,這主要是網(wǎng)絡(luò)規(guī)模較小、結(jié)構(gòu)較特殊的原因?qū)е?但整體性能表現(xiàn)較好,說明SNV-BC算法是有效可行的。

圖6 Coauthor網(wǎng)絡(luò)NDCG@n評分對比

3.3 人工合成網(wǎng)絡(luò)上的效果分析

本節(jié)首先利用LFR生成多個規(guī)模較大的實驗網(wǎng)絡(luò),然后在不同LFR網(wǎng)絡(luò)上利用SIR模型進(jìn)一步對算法效果進(jìn)行分析。為生成符合要求特性的網(wǎng)絡(luò),需要對LFR參數(shù)進(jìn)行相應(yīng)配置[24],其中,k=6表示平均節(jié)點度,max-k=20表示最大節(jié)點度,u=0.1表示混合參數(shù),min-c=15表示社區(qū)最小節(jié)點數(shù),max-c=100表示社區(qū)最大節(jié)點數(shù)。

各算法分別計算求得相應(yīng)的Top-k節(jié)點序列,選取序列中的前n個節(jié)點作為SIR模型中的初始傳染源進(jìn)行擴(kuò)散實驗,統(tǒng)一設(shè)定SIR模型感染率α為0.8,治愈率β為0.5。由于是概率實驗,因此為避免誤差影響,每一種情況下都進(jìn)行50次計算并將其平均值作為最終結(jié)果。

圖7(a)、圖8(a)、圖9(a)、圖10(a)分別是LFR-500、LFR-1000、LFR-1500、LFR-2000網(wǎng)絡(luò)數(shù)據(jù)集上各算法結(jié)果的感染率對比?？梢钥闯?隨著初始感染節(jié)點數(shù)量的增加,本文提出SNV-BC算法的感染率均呈現(xiàn)出穩(wěn)定的增長趨勢。在LFR-500、LFR-1000和LFR-1500網(wǎng)絡(luò)上多數(shù)情況下要明顯優(yōu)于其他算法。在LFR-2000網(wǎng)絡(luò)中,部分區(qū)間其他算法的感染率高于SNV-BC算法,但是波動較大,而SNV-BC算法仍然保持較為穩(wěn)定的增長趨勢。

需要注意的是,盡管整體呈現(xiàn)出增長的趨勢,但各網(wǎng)絡(luò)數(shù)據(jù)集中的算法均不同程度的存在部分區(qū)間的最大感染率反而隨著初始感染節(jié)點的增加而降低的情況,如圖8(a)中SNV算法的初始傳播源節(jié)點數(shù)為15～20,圖9(a)中PageRank算法的初始傳播源節(jié)點數(shù)為3～6。這是由網(wǎng)絡(luò)結(jié)構(gòu)和SIR模型中免疫節(jié)點的免疫隔離共同作用的結(jié)果。免疫感染率降低程度越大,說明隔離程度也越明顯,從一定程度上反映了節(jié)點的關(guān)鍵性越強。在社交網(wǎng)絡(luò)分析研究中,可以理解為人們對于同一信息的興趣(或者信息的傳播擴(kuò)散能力),隨著該信息被接收次數(shù)的增加會快速降低甚至忽略。如果關(guān)鍵節(jié)點免疫越早,其隔離作用也就生效的越早,其對于整個網(wǎng)絡(luò)的信息擴(kuò)散隔離效果就越明顯。

從一定程度上來看,各算法感染率的區(qū)分度還不是很明顯。因此,本文通過比較達(dá)到最大感染率所需的時間來進(jìn)一步說明本文提出算法的優(yōu)勢。圖7(b)、圖8(b)、圖9(b)、圖10(b)分別是LFR-500、LFR-1000、LFR-1500、LFR-2000網(wǎng)絡(luò)數(shù)據(jù)集上各算法達(dá)到最大感染率所需時間的對比。可以看出,本文提出的SNV-BC算法達(dá)到最大感染率所需時間較短,并且隨著初始節(jié)點數(shù)量的增多,均提早多個周期達(dá)到最大感染率,進(jìn)而表明所得到的Top-k節(jié)點關(guān)鍵性更強,充分體現(xiàn)了算法的有效性。從最大感染率和達(dá)到最大感染率所需時間曲線圖中也可以看出,SNV算法和SNV-BC算法變化趨勢基本保持一致,進(jìn)一步證明BC算法過濾的有效性和可行性。

圖7 LFR-500網(wǎng)絡(luò)中6種算法效果對比

圖8 LFR-1000網(wǎng)絡(luò)中6種算法效果對比

圖9 LFR-1500網(wǎng)絡(luò)中6種算法效果對比

圖10 LFR-2000網(wǎng)絡(luò)中6種算法效果對比

4 結(jié)束語

本文分析并研究了復(fù)雜網(wǎng)絡(luò)上Top-k結(jié)構(gòu)洞的問題,提出基于最短路徑增量與中介中心性過濾的結(jié)構(gòu)洞發(fā)現(xiàn)算法SNV-BC,利用NDCG評估方法和SIR模型在多個網(wǎng)絡(luò)上對SNV-BC算法進(jìn)行評估。實驗結(jié)果表明,該算法可以更準(zhǔn)確地找到結(jié)構(gòu)洞,同時利用中介中心性算法提前完成過濾篩選,有效控制和降低算法的時間復(fù)雜度。后續(xù)將對節(jié)點過濾算法進(jìn)行優(yōu)化,進(jìn)一步提高結(jié)構(gòu)洞發(fā)現(xiàn)算法效率。