基于圖結構特征分析的Top-k結構洞發現算法

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

(云南大學 a.信息學院; b.軟件學院; c.生態學與環境學院,昆明 650091)

0 概述

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

結構洞的概念由BURT于2009年提出[1],其對個體在群體之中的關鍵位置進行深入解釋和分析,認為社會結構中處在關鍵位置的個體將能夠獲得更多的競爭優勢等,但真實網絡遠比示例網絡要復雜得多,隨著研究的深入,對結構洞的理解也不再局限于社區間信息流動的關鍵節點。

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

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

1 理論基礎

1.1 網絡模型定義

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

(1)

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

(2)

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

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

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

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

(3)

對于給定的網絡G,c(G)是一個常數。該常數對兩個節點之間的SPIG值的比較沒有影響。因此,使用SPIG′代替SPIG進行比較,提高計算效率。

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

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

(4)

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

圖1 NCC和節點方差的定義

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

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

1.2 問題描述與定義

給定網絡G=(V,E),結構洞發現就是找到節點集合Vs(Vs?V),使得從圖G中移除集合Vs中的節點能夠導致子圖GVs的最短路徑增量最大化。換言之,若移除節點v后SPIG值越大,則說明節點v的結構洞屬性就越強。

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

圖2 結構洞示意圖

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

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

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

屬性3給定節點v和u,節點v橋接兩個較大的社區,節點u橋接兩個較小的社區或一大一小的社區。對于整個網絡的信息擴散而言,移除節點v比移除u的影響更大,因此節點v具有比u更高的結構洞屬性值。

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

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

2 SNV-BC結構洞發現算法

2.1 算法原理

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

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

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

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

(5)

(6)

(7)

按照式(8)進行合并:

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

VARnorm(v))

(8)

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

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

2.2 基于BC算法的過濾原理

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

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

2.3 算法偽代碼

算法1SNV-BC結構洞發現算法

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

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

1.Get Vpassby invoking Procedure 3;

/*通過調用程序3獲取被過濾的節點集合*/

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

3.For i ← 1 to n do:

4.If vinot in Vpassthen:

/* 只計算未被過濾的節點*/

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

/*通過調用程序1計算SPIG、VAR、NCC */

6.Else

7.SH(vi) ← 0;

8.End if

9.End for

10.For i ← 0 to n do:

/*歸一化各節點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計算節點SPIG,VAR,NCC值的偽代碼

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

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

1.Let the dictionary data vertex_info ← ?

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

3.NCC ← nx.number_connected_components (G);

/*計算連通分量個數*/

4.If NCC==1 then:

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

/*通過調用程序2計算相應的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;

/*統計各子連通分量節點數*/

11.VAR ← calculate the variance of NVCC;

/*計算各子連通分量節點數的方差*/

12.Add NCC,VAR and SPIG to vertex_info

13.Return the dictionary vertex_info

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

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

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

1.Def BCSP (i,j):

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

2.SP ← shortest_path (i,j);

3.Return SP

4.Def VSP (v):

/*通過調用BCSP計算單源節點的最短路徑和 */

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

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

7.End for

8.Return SP

9.Def NSP (G):

/*通過調用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:

/*根據輸入類型進行對應計算 */

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)

輸出優化后被過濾的節點集合Vpass

1.Let n=|V|;

2.k=0.025*n;

/*通過閾值確定選取節點數*/

3.If k<50:

/*將節點數最低值設為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:

/*將閾值以后的節點加入到Vpass中*/

9.Add vertex vito set Vpass

10.End for

11.Return set Vpass

2.4 算法時間復雜度

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

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

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

3 實驗結果與分析

3.1 實驗環境設定

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

表1 網絡數據集

NDCG是常用的排序結果評價算法。當通過算法得出相應的排序結果后,可以通過NDCG來計算該排序結果相對于標準結果的準確度。NDCG@n表示取前n位排序結果進行準確度計算。

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

LFR算法由LANCICHINETTI等人于2008年提出[21]。通過該算法能夠生成一種標準測試網絡。現實網絡數據集中的節點度服從冪律分布,利用該算法生成的網絡同樣服從冪律分布規律和特點,因此利用LFR生成的網絡結構來模擬真實網絡進行實驗。

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

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

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

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

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

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

3.2 算法有效性分析

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

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

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

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

圖5 Coauthor網絡

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

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

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

圖6 Coauthor網絡NDCG@n評分對比

3.3 人工合成網絡上的效果分析

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

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

圖7(a)、圖8(a)、圖9(a)、圖10(a)分別是LFR-500、LFR-1000、LFR-1500、LFR-2000網絡數據集上各算法結果的感染率對比。可以看出,隨著初始感染節點數量的增加,本文提出SNV-BC算法的感染率均呈現出穩定的增長趨勢。在LFR-500、LFR-1000和LFR-1500網絡上多數情況下要明顯優于其他算法。在LFR-2000網絡中,部分區間其他算法的感染率高于SNV-BC算法,但是波動較大,而SNV-BC算法仍然保持較為穩定的增長趨勢。

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

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

圖7 LFR-500網絡中6種算法效果對比

圖8 LFR-1000網絡中6種算法效果對比

圖9 LFR-1500網絡中6種算法效果對比

圖10 LFR-2000網絡中6種算法效果對比

4 結束語

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