鄧 佩,何嘉林,朱力強
(西華師范大學(xué) 計算機(jī)學(xué)院,四川 南充 637009)
在現(xiàn)實世界中,人們往往將許多復(fù)雜系統(tǒng)抽象成復(fù)雜網(wǎng)絡(luò)來進(jìn)行研究,其中每個節(jié)點可以表示復(fù)雜系統(tǒng)中的一個元素,而每條邊可以表示復(fù)雜系統(tǒng)中兩個元素之間的相互作用。如在生物網(wǎng)絡(luò)中,節(jié)點表示基因,而連邊則表示基因之間的交互關(guān)系;在社交網(wǎng)絡(luò)中,節(jié)點表示用戶,而連邊則表示用戶之間的朋友或親人關(guān)系;在合作網(wǎng)絡(luò)中,節(jié)點表示作者,而連邊則表示作者之間的合作關(guān)系。近年來,復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點識別研究在許多領(lǐng)域都具有廣泛的應(yīng)用,如電氣科學(xué)[1]、交通運輸[2]、物聯(lián)網(wǎng)[3]、生物醫(yī)學(xué)[4]和軟件安全等[5]。如在營銷行業(yè)中,應(yīng)該重點關(guān)注客戶網(wǎng)絡(luò)中最具影響力的少數(shù)顧客,因為這些顧客會對他們的親人或者朋友產(chǎn)生直接影響[6];在疾病傳播的過程中,只需要對網(wǎng)絡(luò)中的重要病人進(jìn)行隔離并治療,就可以有效地控制疾病的傳播[7];對許多重要軟件系統(tǒng)來說,為保證它們在意外情況下的安全,只需要保護(hù)重要程度很高的函數(shù)就可以保證整個系統(tǒng)的正常運行[8]。
過去幾十年,許多識別單個關(guān)鍵節(jié)點的方法被提出,它們基本上遵從以下三個思路:從節(jié)點的局部環(huán)境考慮,從節(jié)點所處的位置考慮和從節(jié)點對網(wǎng)絡(luò)功能的影響考慮。對第一種思路來說,節(jié)點的局部環(huán)境通常包括鄰居節(jié)點和聚類系數(shù)等。ClusterRank 指標(biāo)同時考慮節(jié)點的度和聚類系數(shù)[9]。度中心性僅僅考慮節(jié)點的一階鄰居的數(shù)量,而半局部中心性則考慮了節(jié)點的四層鄰居的信息[10]。除了考慮鄰居節(jié)點的數(shù)量之外,一些挖掘算法還從鄰居節(jié)點的重要性進(jìn)行了探索,這些算法主是指基于特征向量的系列算法[11-13]。另外,Katz 中心性[14]、接近中心性[15]和信息指標(biāo)[16]從節(jié)點與網(wǎng)絡(luò)的其他節(jié)點的聯(lián)系強弱角度來評估節(jié)點的重要性。第二種思路分為兩種:節(jié)點在路徑中的位置和節(jié)點在網(wǎng)絡(luò)中的位置。前者主要包括介數(shù)中心性[17-19]、圖中心性[20]以及其他基于路徑的算法[21],而k-core 分解法則是后者的典型代表[22]。第三種思路主要考察將節(jié)點移除之后的網(wǎng)絡(luò)結(jié)構(gòu)和功能的變化,例如,殘余接近中心性和節(jié)點刪除的最短距離法主要關(guān)注網(wǎng)絡(luò)中的平均最短距離的變化[23],生成樹法主要關(guān)注節(jié)點刪除后的網(wǎng)絡(luò)生成樹的變化[24],節(jié)點收縮法關(guān)注節(jié)點刪除后的網(wǎng)絡(luò)凝聚度的變化[25]。
然而,在實際應(yīng)用中,往往需要識別一組關(guān)鍵節(jié)點。以上這些指標(biāo)通常選擇前top-k 個節(jié)點作為一組關(guān)鍵節(jié)點。然而,這種策略只考慮了單個關(guān)鍵節(jié)點的重要性,而忽略了關(guān)鍵節(jié)點之間的分布,從而導(dǎo)致前top-k 個節(jié)點往往集中在少數(shù)區(qū)域[26]。為解決這個問題,本論文提出了一種啟發(fā)式的識別一組關(guān)鍵節(jié)點算法——連邊折扣打分法(Adjacent Discount Score,ADScore),以下簡稱ADScore。該算法通過懲罰每個關(guān)鍵節(jié)點的一階鄰居節(jié)點和二階鄰居節(jié)點的打分能力,從而挑選一組足夠分散的關(guān)鍵節(jié)點。在真實網(wǎng)絡(luò)與人工網(wǎng)絡(luò)上的實驗表明,本文提出的算法在SIR 模型上的性能始終優(yōu)于其他四個基準(zhǔn)算法,并且我們算法的性能具有更好的穩(wěn)定性。
許多傳統(tǒng)的關(guān)鍵節(jié)點識別算法在選擇一組關(guān)鍵節(jié)點時,往往只考慮單個關(guān)鍵節(jié)點在網(wǎng)絡(luò)中的重要性,而忽略了一組關(guān)鍵節(jié)點之間的分布。因此選擇的一組關(guān)鍵節(jié)點往往過于集中在網(wǎng)絡(luò)的少數(shù)區(qū)域,從而導(dǎo)致信息無法傳播開來。為解決這個問題,不僅要考慮關(guān)鍵節(jié)點在網(wǎng)絡(luò)中的重要性,同時還要考慮關(guān)鍵節(jié)點在網(wǎng)絡(luò)中的均衡分布,盡可能使選擇的一組關(guān)鍵節(jié)點分散開來。基于這樣的思路,認(rèn)為一個節(jié)點v的重要性取決于它所有的一階鄰居節(jié)點u對它的打分,而一個鄰居節(jié)點u的打分能力又取決于它是否與一個關(guān)鍵節(jié)點相鄰。如果一個節(jié)點v還未被選為關(guān)鍵節(jié)點,而節(jié)點v中的大部分鄰居節(jié)點u都與關(guān)鍵節(jié)點相鄰的話,那么節(jié)點v被選為下一個關(guān)鍵節(jié)點的可能性會非常小。
基于以上描述,假設(shè)每個節(jié)點v都與一個二元組(s v,av)相關(guān),其中sv表示節(jié)點v的得分,a v表示節(jié)點v的打分能力,則節(jié)點v的得分sv可以定義為:
其中,γ1(v)表示節(jié)點v的一階鄰居節(jié)點集合,a u表示一階鄰居節(jié)點的打分能力。分三個階段挑選一組關(guān)鍵節(jié)點。初始時,每個節(jié)點的二元組均設(shè)置為(0,1)。步驟1,根據(jù)公式(1)計算每個節(jié)點的得分,并將得分最高的節(jié)點v選為關(guān)鍵節(jié)點。步驟2,由于關(guān)鍵節(jié)點v不再參與后續(xù)的打分,因此直接將它的打分能力設(shè)置為0,即av=0。為使選擇的一組關(guān)鍵節(jié)點盡可能地分散,需要減小關(guān)鍵節(jié)點v的所有一階鄰居節(jié)點和二階鄰居節(jié)點的打分能力。具體地說,對每個節(jié)點u∈γ1(v) ∪γ2(v),根據(jù)公式(2)更新它們的打分能力au,其中d表示折扣因子和γ2(v)表示節(jié)點v的二階鄰居節(jié)點集合。
最后,重復(fù)步驟1 和2,直到所需要的k個關(guān)鍵節(jié)點被選擇為止。
圖1 展示了ADScore 算法選擇2 個關(guān)鍵節(jié)點的過程。圖1(a)是一個具有15 個節(jié)點、19 條連邊和平均度w=2.5 的小樣本無向網(wǎng)絡(luò),每個節(jié)點v所對應(yīng)的二元組(s v,av)都初始化為(0,1)并已經(jīng)在圖1(a)中標(biāo)出。然后進(jìn)行第一輪打分,利用公式(1)計算出每個節(jié)點的得分sv,并選擇得分最高的節(jié)點7 作為第一個關(guān)鍵節(jié)點,結(jié)果如圖1(b)所示。接下來,由于關(guān)鍵節(jié)點7 不再參與后續(xù)的打分過程,所以直接將其打分能力設(shè)置為0,然后利用公式(2)減小關(guān)鍵節(jié)點7 的一階鄰居節(jié)點(4,5,6,8,11 和12)和二階鄰居節(jié)點(2,3,13,14 和15)的打分能力,即每個節(jié)點的打分能力au減小d=1/2.5=0.4(假設(shè)d=1/w)。同時為了下一輪打分做準(zhǔn)備,因此需要重新將每個節(jié)點的得分sv重新設(shè)置為0,結(jié)果如圖1(c)所示。循環(huán)進(jìn)行第二輪打分,重新利用公式(1)計算出每個節(jié)點的得分,并選擇得分最高的節(jié)點3 作為第二個關(guān)鍵節(jié)點,結(jié)果如圖1(d)所示。最終選擇7 號和3 號節(jié)點作為所需要的2 個關(guān)鍵節(jié)。
圖1 ADScore 算法挑選2 個關(guān)鍵節(jié)點的過程
使用SIR 模型[27]來評估算法(ADScore)的性能,并在真實網(wǎng)絡(luò)與人工網(wǎng)絡(luò)上與WVoteRank[28],Coreness[15],Betweenness[17]和Hindex[29]四個經(jīng)典算法進(jìn)行比較。
使用廣泛研究的SIR 模型來模擬網(wǎng)絡(luò)中的傳播過程。在SIR 模型中,網(wǎng)絡(luò)中的每個節(jié)點在任何時刻只能處于以下三種狀態(tài)之一:未感染狀態(tài)(S),已感染狀態(tài)(I)和已恢復(fù)狀態(tài)(R)。初始時,根據(jù)給定算法從網(wǎng)絡(luò)中選擇k個關(guān)鍵節(jié)點成為已感染節(jié)點,并默認(rèn)其余節(jié)點為易感染節(jié)點。已感染節(jié)點的狀態(tài)默認(rèn)為已感染狀態(tài)(I),易感染節(jié)點的狀態(tài)默認(rèn)為未感染狀態(tài)(S),恢復(fù)正常的節(jié)點狀態(tài)默認(rèn)為已恢復(fù)狀態(tài)(R)。在隨后的在每一個時刻,每個已感染節(jié)點會隨機(jī)接觸一個鄰居節(jié)點。如果這個鄰居節(jié)點處于未感染狀態(tài)(S),則已感染節(jié)點會以概率α把疾病傳染給它。同時,每個已感染節(jié)點會以概率β恢復(fù)正常。如果恢復(fù)成功,則該節(jié)點在以后的傳播過程中不會再被感染,也不會再感染其它易感染鄰居節(jié)點。根據(jù)上述的描述,疾病傳播率λ定義為α/β。當(dāng)網(wǎng)絡(luò)中沒有任何已感染節(jié)點時,傳播過程結(jié)束。如果最終感染的節(jié)點規(guī)模很大,則說明選擇的k個關(guān)鍵節(jié)點在網(wǎng)絡(luò)中具有重大的影響力。
在SIR 模型中,一個算法的性能取決于它最終感染的節(jié)點總數(shù)。假設(shè)F(t)表示網(wǎng)絡(luò)在t時刻感染的節(jié)點百分比(包括已恢復(fù)的節(jié)點),則最終的感染規(guī)模F(tc)定義為
四個真實無向網(wǎng)絡(luò)被用來評估算法的性能,其中包括Dimension[30],AS_dataset[31],CE-GN[32]和LastFM[33]。Dimension 網(wǎng)絡(luò)是為了解決現(xiàn)實中的二維問題,共包含4720 個節(jié)點和13724 條邊。網(wǎng)絡(luò)中的每個節(jié)點表示二維網(wǎng)絡(luò)中的一個節(jié)點,每條連邊表示兩個節(jié)點之間的距離。AS_dataset網(wǎng)絡(luò)是一個自治系統(tǒng)網(wǎng)絡(luò),共包含6474 個節(jié)點和13895 條邊。網(wǎng)絡(luò)中的每個節(jié)點表示一個路由器,每條連邊表示兩個路由器之間的流量交換。CE-GN 是一個生物網(wǎng)絡(luò),共包含2200 個節(jié)點和53683 條邊。網(wǎng)絡(luò)中的每個節(jié)點表示一個基因,每條連邊表示兩個基因之間的相互作用。LastFM是一個社交網(wǎng)絡(luò),共包含7624 個節(jié)點和27806 條邊。網(wǎng)絡(luò)中的節(jié)點表示來自亞洲國家的LastFM用戶,連邊表示用戶之間的相互關(guān)注關(guān)系。表1描述了四個真實網(wǎng)絡(luò)的詳細(xì)拓?fù)浣Y(jié)構(gòu)信息,分別包含節(jié)點數(shù)(),邊數(shù)(),平均度(<w>),平均聚類系數(shù)(<c>)和網(wǎng)絡(luò)度分類系數(shù)(<r>)。
表1 四個真實網(wǎng)絡(luò)的詳細(xì)拓?fù)浣Y(jié)構(gòu)信息
為研究網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)對算法性能的影響,四個由LFR 模型[34]生成的人工網(wǎng)絡(luò)被用來進(jìn)一步評估算法的性能。在LFR 模型中,網(wǎng)絡(luò)節(jié)點度和社團(tuán)大小都服從冪律分布,其指數(shù)分別為θ1和θ2。通常地,兩個指數(shù)θ1和θ2的取值范圍分別為2≤θ1≤ 3和1≤θ2≤ 2?;旌蠀?shù)μ控制著網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的強弱,即μ越小,社團(tuán)結(jié)構(gòu)越強。從表2 中可以看出,在生成四個人工網(wǎng)絡(luò)時,除混合參數(shù)μ不同外,其他三個參數(shù)θ1,θ2和<w>均相同。對網(wǎng)絡(luò)LFR1 和LFR2來說,它們的μ值分別為0.1 和0.2,因此它們具有較強的強社團(tuán)結(jié)構(gòu);反之,對于網(wǎng)絡(luò)LFR3 和LFR4 來說,它們的μ值分別為0.5 和0.6,因此它們具有較弱的社團(tuán)結(jié)構(gòu)。表2 描述了四個人工網(wǎng)絡(luò)的詳細(xì)拓?fù)浣Y(jié)構(gòu)信息,分別包含節(jié)點數(shù)()、邊數(shù)()、度指數(shù)(θ1)、社團(tuán)指數(shù)(2θ)、混合參數(shù)(u)和網(wǎng)絡(luò)的平均度(<w>)。
表2 四個人工網(wǎng)絡(luò)的詳細(xì)拓?fù)浣Y(jié)構(gòu)信息
首先,在四個真實網(wǎng)絡(luò)上評估了不同p=k/n對ADScore 算法性能的影響,其中k和n分別表示關(guān)鍵節(jié)點個數(shù)和網(wǎng)絡(luò)節(jié)點個數(shù),因此p表示關(guān)鍵節(jié)點的占比,實驗中參數(shù)λ=1.2 和β=1/<w>,實驗結(jié)果是200 次獨立運行的平均值,結(jié)果如圖2 所示。從圖2 可知,ADScore 算法在絕大部分情況下都優(yōu)于其它基準(zhǔn)算法。具體地說,在網(wǎng)絡(luò)Dimension 上,當(dāng)p≤0.05時,ADScore 算法的F(tc)與其他算法的F(tc)比較接近;當(dāng)p>0.05時,ADScore 算法開始優(yōu)于所有基準(zhǔn)算法;尤其當(dāng)p= 0.09時,與表現(xiàn)最差的Hindex 算法相比,ADScore 算法的F(tc)提升了17.8%。在網(wǎng)絡(luò)AS_dataset 上,當(dāng)p≤0.02時,WVoteRank 與ADScore兩個算法表現(xiàn)最好,它們的F(tc)非常接近;當(dāng)p> 0.02時,ADScore 算法開始優(yōu)于所有基準(zhǔn)算法;同樣的,在p=0.09時,ADScore 算法與表現(xiàn)最差的Hindex 算法相比,F(xiàn)(tc)提高了11.5%。在CE-GN 網(wǎng)絡(luò)上,對于所有p,ADScore 算法始終優(yōu)于所有基準(zhǔn)算法;在p=0.09時,ADScore 相比表現(xiàn)最差的Hindex 算法來說,F(xiàn)(tc)提升了11.9 %。在LastFM 網(wǎng)絡(luò)上,當(dāng)p≤0.02時,四個算法ADScore、WVoteRank、Hindex 和Betweenness 的F(tc)比較接近,但都比Coreness 方法高;然而,當(dāng)p>0.02時,ADScore 算法表現(xiàn)最好,并與其他算法逐漸拉開差距;在最后p=0.09時,ADScore 算法與表現(xiàn)最差的WVoteRank 算法相比,F(xiàn)(tc)提升了33.1%。從上面的分析可知,ADScore 算法具有兩個優(yōu)勢:(1)對于較小的p,ADScore 算法在所有網(wǎng)絡(luò)上的性能都不比其他四個基準(zhǔn)方法差;對于較大的p,ADScore 算法在所有網(wǎng)絡(luò)上的表現(xiàn)都是最好的;(2)與ADScore 算法相比,四個基準(zhǔn)算法的性能表現(xiàn)并不穩(wěn)定。比如,WVoteRank 算法在Dimension 網(wǎng)絡(luò)上的性能僅次于ADScore 方法;然而,在LastFM 網(wǎng)絡(luò)上,當(dāng)p>0.05時,它的性能卻是所有算法中最差的,因此ADScore 算法的性能相比其他算法具有更強的穩(wěn)定性。
圖2 在四個真實網(wǎng)絡(luò)上隨p 變化的 F (tc)
其次,在四個真實網(wǎng)絡(luò)上評估了不同傳播率λ對ADScore 算法性能的影響,其中p=0.05,以及β=1/<w>,實驗結(jié)果是200 次獨立運行的平均值,結(jié)果如圖3 所示。從圖3 可以看出,對所有λ,ADScore 算法的性能在所有網(wǎng)絡(luò)上都優(yōu)于所有基準(zhǔn)算法。另外,隨著λ的增加,所有算法的F(tc)在大部分情況下也會隨之增加。然而,與其他四個基準(zhǔn)算法相比,ADScore 算法在大部分情況下的性能提升相對更大。在Dimension 網(wǎng)絡(luò)上,當(dāng)λ=1.0 時,ADScore 算法與表現(xiàn)第二好的Hindex 算法相比,F(xiàn)(tc)只提升了3.5%;而當(dāng)λ=1.5 時,ADScore 算法與Hindex 算法相比F(tc)的提升卻高達(dá)9.2%。由此可以看出,當(dāng)λ較大時,ADScore 算法相對其他算法的性能提升也會變得更大。類似地,在AS_dataset 網(wǎng)絡(luò)上,當(dāng)λ=1.0 時,ADScore算法相比第二好的Hindex 算法F(tc)提升只有2.7%;而當(dāng)λ=1.5 時,ADScore 相比Hindex 算法F(tc)提升卻有7.8%。在CE-GN 網(wǎng)絡(luò)上,當(dāng)λ=1.0 時,ADScore 算法相對第二好的Betweenness算法性能F(tc)提升了 4.2%;而當(dāng)λ=1.5 時,兩者相比,ADScore 算法性能F(tc)提升了8.1%。同樣,在LastFM 網(wǎng)絡(luò)上,當(dāng)λ=1.0 時,ADScore 算法相比第二好的Hindex 算法F(tc)提升了6.3%;而當(dāng)λ=1.5 時,ADScore 算法相比Hindex 算法F(tc)的提升高達(dá)10.8%。綜合以上分析,ADScore 算法在λ較大時相比其他算法具有更大的性能優(yōu)勢。
圖3 在四個真實網(wǎng)絡(luò)上隨 變化的 F (tc)
進(jìn)一步在四個具有不同社團(tuán)結(jié)構(gòu)的人工網(wǎng)絡(luò)上評估ADScore 算法的性能。在實驗中,設(shè)置參數(shù)p=0.05,λ=1.5 和β=1/10。每個數(shù)據(jù)都是 200次獨立運行結(jié)果的平均值,實驗結(jié)果如表3 所示。從表3 可以看出,ADScore 算法的性能在四個人工網(wǎng)絡(luò)上都優(yōu)于其他四個基準(zhǔn)方法。比如說,在社團(tuán)結(jié)構(gòu)強度較強的LFR1 網(wǎng)絡(luò)上,ADScore,WVoteRank,Coreness,Betweenness 和Hindex 算 法F(tc)分 別為0.397,0.361,0.339,0.349 和0.352,其中ADScore算法的F(tc)最高,Coreness 算法最低,兩者相比,ADScore 算法的性能提高了17.1%。類似地,在社團(tuán)結(jié)構(gòu)強度較弱的LFR4 網(wǎng)絡(luò)上,ADScore 算法的性能表現(xiàn)依然是最好的,與Betweenness 算法相比性能提升了15.8%。此外,也可以看到網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的強弱對所有算法性能的影響都非常小。比如說,在社團(tuán)結(jié)構(gòu)比較強的LFR1 網(wǎng)絡(luò)上和社團(tuán)結(jié)構(gòu)比較弱的LFR4 網(wǎng)絡(luò)上,ADScore 算法的F(tc)分別為0.397 和0.395,兩者僅相差0.2 %;類似地,WVoteRank,Coreness,Betweenness 和Hindex 算 法分別相差0.8%,0.5%,0.8%和1.0%。由此可以看出,與其他四個基準(zhǔn)算法相比,ADScore 算法不僅在社團(tuán)結(jié)構(gòu)強度較強的網(wǎng)絡(luò)上具有優(yōu)勢,而且在社區(qū)結(jié)構(gòu)強度較弱的網(wǎng)絡(luò)上同樣具有優(yōu)勢。
表3 在四個具有不同社團(tuán)結(jié)構(gòu)的人工網(wǎng)絡(luò)上的實驗結(jié)果
許多傳統(tǒng)的識別一組關(guān)鍵節(jié)點的算法都只考慮了單個關(guān)鍵節(jié)點在網(wǎng)絡(luò)中的重要性,而忽略了關(guān)鍵節(jié)點之間的分布,因此常常導(dǎo)致選擇的一組關(guān)鍵節(jié)點集中在少數(shù)區(qū)域,從而無法最大化信息的傳播范圍?;谏鲜鲈颍疚奶岢隽艘环N啟發(fā)式的一組關(guān)鍵節(jié)點識別算法ADScore。在算法ADScore 中,每個節(jié)點的重要性取決于它的一階鄰居節(jié)點和二階鄰居節(jié)點的打分能力,而一階鄰居節(jié)點的打分能力又取決于它是否與關(guān)鍵節(jié)點相鄰,該策略保證了選擇的一組關(guān)鍵節(jié)點盡可能的分散。在真實網(wǎng)絡(luò)和人工網(wǎng)絡(luò)上的實驗表明ADScore 算法具有以下五個結(jié)論:(1)與四個基準(zhǔn)方法相比,p值越大,它越具有優(yōu)勢;(2)相比其他四個基準(zhǔn)方法的性能表現(xiàn),ADScore 算法的性能具有更強的穩(wěn)定性;(3)與四個基準(zhǔn)方法相比,傳播率λ越大,它越具有優(yōu)勢;(4)在具有任何社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)上,它都優(yōu)于其他四個基準(zhǔn)方法。