鄧 佩，何嘉林，朱力強

（西華師范大學 計算機學院，四川 南充 637009）

在現(xiàn)實世界中，人們往往將許多復雜系統(tǒng)抽象成復雜網(wǎng)絡來進行研究，其中每個節(jié)點可以表示復雜系統(tǒng)中的一個元素，而每條邊可以表示復雜系統(tǒng)中兩個元素之間的相互作用。如在生物網(wǎng)絡中，節(jié)點表示基因，而連邊則表示基因之間的交互關系；在社交網(wǎng)絡中，節(jié)點表示用戶，而連邊則表示用戶之間的朋友或親人關系；在合作網(wǎng)絡中，節(jié)點表示作者，而連邊則表示作者之間的合作關系。近年來，復雜網(wǎng)絡中的關鍵節(jié)點識別研究在許多領域都具有廣泛的應用，如電氣科學［1］、交通運輸［2］、物聯(lián)網(wǎng)［3］、生物醫(yī)學［4］和軟件安全等［5］。如在營銷行業(yè)中，應該重點關注客戶網(wǎng)絡中最具影響力的少數(shù)顧客，因為這些顧客會對他們的親人或者朋友產(chǎn)生直接影響［6］；在疾病傳播的過程中，只需要對網(wǎng)絡中的重要病人進行隔離并治療，就可以有效地控制疾病的傳播［7］；對許多重要軟件系統(tǒng)來說，為保證它們在意外情況下的安全，只需要保護重要程度很高的函數(shù)就可以保證整個系統(tǒng)的正常運行［8］。

過去幾十年，許多識別單個關鍵節(jié)點的方法被提出，它們基本上遵從以下三個思路：從節(jié)點的局部環(huán)境考慮，從節(jié)點所處的位置考慮和從節(jié)點對網(wǎng)絡功能的影響考慮。對第一種思路來說，節(jié)點的局部環(huán)境通常包括鄰居節(jié)點和聚類系數(shù)等。ClusterRank 指標同時考慮節(jié)點的度和聚類系數(shù)［9］。度中心性僅僅考慮節(jié)點的一階鄰居的數(shù)量，而半局部中心性則考慮了節(jié)點的四層鄰居的信息［10］。除了考慮鄰居節(jié)點的數(shù)量之外，一些挖掘算法還從鄰居節(jié)點的重要性進行了探索，這些算法主是指基于特征向量的系列算法［11-13］。另外，Katz 中心性［14］、接近中心性［15］和信息指標［16］從節(jié)點與網(wǎng)絡的其他節(jié)點的聯(lián)系強弱角度來評估節(jié)點的重要性。第二種思路分為兩種：節(jié)點在路徑中的位置和節(jié)點在網(wǎng)絡中的位置。前者主要包括介數(shù)中心性［17-19］、圖中心性［20］以及其他基于路徑的算法［21］，而k-core 分解法則是后者的典型代表［22］。第三種思路主要考察將節(jié)點移除之后的網(wǎng)絡結(jié)構和功能的變化，例如，殘余接近中心性和節(jié)點刪除的最短距離法主要關注網(wǎng)絡中的平均最短距離的變化［23］，生成樹法主要關注節(jié)點刪除后的網(wǎng)絡生成樹的變化［24］，節(jié)點收縮法關注節(jié)點刪除后的網(wǎng)絡凝聚度的變化［25］。

然而，在實際應用中，往往需要識別一組關鍵節(jié)點。以上這些指標通常選擇前top-k 個節(jié)點作為一組關鍵節(jié)點。然而，這種策略只考慮了單個關鍵節(jié)點的重要性，而忽略了關鍵節(jié)點之間的分布，從而導致前top-k 個節(jié)點往往集中在少數(shù)區(qū)域［26］。為解決這個問題，本論文提出了一種啟發(fā)式的識別一組關鍵節(jié)點算法——連邊折扣打分法（Adjacent Discount Score，ADScore），以下簡稱ADScore。該算法通過懲罰每個關鍵節(jié)點的一階鄰居節(jié)點和二階鄰居節(jié)點的打分能力，從而挑選一組足夠分散的關鍵節(jié)點。在真實網(wǎng)絡與人工網(wǎng)絡上的實驗表明，本文提出的算法在SIR 模型上的性能始終優(yōu)于其他四個基準算法，并且我們算法的性能具有更好的穩(wěn)定性。

1 研究方法

許多傳統(tǒng)的關鍵節(jié)點識別算法在選擇一組關鍵節(jié)點時，往往只考慮單個關鍵節(jié)點在網(wǎng)絡中的重要性，而忽略了一組關鍵節(jié)點之間的分布。因此選擇的一組關鍵節(jié)點往往過于集中在網(wǎng)絡的少數(shù)區(qū)域，從而導致信息無法傳播開來。為解決這個問題，不僅要考慮關鍵節(jié)點在網(wǎng)絡中的重要性，同時還要考慮關鍵節(jié)點在網(wǎng)絡中的均衡分布，盡可能使選擇的一組關鍵節(jié)點分散開來?；谶@樣的思路，認為一個節(jié)點v的重要性取決于它所有的一階鄰居節(jié)點u對它的打分，而一個鄰居節(jié)點u的打分能力又取決于它是否與一個關鍵節(jié)點相鄰。如果一個節(jié)點v還未被選為關鍵節(jié)點，而節(jié)點v中的大部分鄰居節(jié)點u都與關鍵節(jié)點相鄰的話，那么節(jié)點v被選為下一個關鍵節(jié)點的可能性會非常小。

基于以上描述，假設每個節(jié)點v都與一個二元組(s v,av)相關，其中sv表示節(jié)點v的得分，a v表示節(jié)點v的打分能力，則節(jié)點v的得分sv可以定義為：

其中，γ1(v)表示節(jié)點v的一階鄰居節(jié)點集合，a u表示一階鄰居節(jié)點的打分能力。分三個階段挑選一組關鍵節(jié)點。初始時，每個節(jié)點的二元組均設置為（0，1）。步驟1，根據(jù)公式（1）計算每個節(jié)點的得分，并將得分最高的節(jié)點v選為關鍵節(jié)點。步驟2，由于關鍵節(jié)點v不再參與后續(xù)的打分，因此直接將它的打分能力設置為0，即av=0。為使選擇的一組關鍵節(jié)點盡可能地分散，需要減小關鍵節(jié)點v的所有一階鄰居節(jié)點和二階鄰居節(jié)點的打分能力。具體地說，對每個節(jié)點u∈γ1(v) ∪γ2(v)，根據(jù)公式（2）更新它們的打分能力au，其中d表示折扣因子和γ2(v)表示節(jié)點v的二階鄰居節(jié)點集合。

最后，重復步驟1 和2，直到所需要的k個關鍵節(jié)點被選擇為止。

圖1 展示了ADScore 算法選擇2 個關鍵節(jié)點的過程。圖1（a）是一個具有15 個節(jié)點、19 條連邊和平均度w=2.5 的小樣本無向網(wǎng)絡，每個節(jié)點v所對應的二元組(s v,av)都初始化為（0，1）并已經(jīng)在圖1（a）中標出。然后進行第一輪打分，利用公式（1）計算出每個節(jié)點的得分sv，并選擇得分最高的節(jié)點7 作為第一個關鍵節(jié)點，結(jié)果如圖1（b）所示。接下來，由于關鍵節(jié)點7 不再參與后續(xù)的打分過程，所以直接將其打分能力設置為0，然后利用公式（2）減小關鍵節(jié)點7 的一階鄰居節(jié)點（4，5，6，8，11 和12）和二階鄰居節(jié)點（2，3，13，14 和15）的打分能力，即每個節(jié)點的打分能力au減小d=1/2.5=0.4（假設d=1/w）。同時為了下一輪打分做準備，因此需要重新將每個節(jié)點的得分sv重新設置為0，結(jié)果如圖1（c）所示。循環(huán)進行第二輪打分，重新利用公式（1）計算出每個節(jié)點的得分，并選擇得分最高的節(jié)點3 作為第二個關鍵節(jié)點，結(jié)果如圖1（d）所示。最終選擇7 號和3 號節(jié)點作為所需要的2 個關鍵節(jié)。

圖1 ADScore 算法挑選2 個關鍵節(jié)點的過程

2 實驗結(jié)果

使用SIR 模型［27］來評估算法（ADScore）的性能，并在真實網(wǎng)絡與人工網(wǎng)絡上與WVoteRank［28］，Coreness［15］，Betweenness［17］和Hindex［29］四個經(jīng)典算法進行比較。

2.1 SIR 模型

使用廣泛研究的SIR 模型來模擬網(wǎng)絡中的傳播過程。在SIR 模型中，網(wǎng)絡中的每個節(jié)點在任何時刻只能處于以下三種狀態(tài)之一：未感染狀態(tài)（S），已感染狀態(tài)（I）和已恢復狀態(tài)（R）。初始時，根據(jù)給定算法從網(wǎng)絡中選擇k個關鍵節(jié)點成為已感染節(jié)點，并默認其余節(jié)點為易感染節(jié)點。已感染節(jié)點的狀態(tài)默認為已感染狀態(tài)（I），易感染節(jié)點的狀態(tài)默認為未感染狀態(tài)（S），恢復正常的節(jié)點狀態(tài)默認為已恢復狀態(tài)（R）。在隨后的在每一個時刻，每個已感染節(jié)點會隨機接觸一個鄰居節(jié)點。如果這個鄰居節(jié)點處于未感染狀態(tài)（S），則已感染節(jié)點會以概率α把疾病傳染給它。同時，每個已感染節(jié)點會以概率β恢復正常。如果恢復成功，則該節(jié)點在以后的傳播過程中不會再被感染，也不會再感染其它易感染鄰居節(jié)點。根據(jù)上述的描述，疾病傳播率λ定義為α/β。當網(wǎng)絡中沒有任何已感染節(jié)點時，傳播過程結(jié)束。如果最終感染的節(jié)點規(guī)模很大，則說明選擇的k個關鍵節(jié)點在網(wǎng)絡中具有重大的影響力。

2.2 評價指標

在SIR 模型中，一個算法的性能取決于它最終感染的節(jié)點總數(shù)。假設F(t)表示網(wǎng)絡在t時刻感染的節(jié)點百分比（包括已恢復的節(jié)點），則最終的感染規(guī)模F(tc)定義為

3 實驗數(shù)據(jù)

3.1 真實網(wǎng)絡

四個真實無向網(wǎng)絡被用來評估算法的性能，其中包括Dimension［30］，AS_dataset［31］，CE-GN［32］和LastFM［33］。Dimension 網(wǎng)絡是為了解決現(xiàn)實中的二維問題，共包含4720 個節(jié)點和13724 條邊。網(wǎng)絡中的每個節(jié)點表示二維網(wǎng)絡中的一個節(jié)點，每條連邊表示兩個節(jié)點之間的距離。AS_dataset網(wǎng)絡是一個自治系統(tǒng)網(wǎng)絡，共包含6474 個節(jié)點和13895 條邊。網(wǎng)絡中的每個節(jié)點表示一個路由器，每條連邊表示兩個路由器之間的流量交換。CE-GN 是一個生物網(wǎng)絡，共包含2200 個節(jié)點和53683 條邊。網(wǎng)絡中的每個節(jié)點表示一個基因，每條連邊表示兩個基因之間的相互作用。LastFM是一個社交網(wǎng)絡，共包含7624 個節(jié)點和27806 條邊。網(wǎng)絡中的節(jié)點表示來自亞洲國家的LastFM用戶，連邊表示用戶之間的相互關注關系。表1描述了四個真實網(wǎng)絡的詳細拓撲結(jié)構信息，分別包含節(jié)點數(shù)（），邊數(shù)（），平均度（＜w＞），平均聚類系數(shù)（＜c＞）和網(wǎng)絡度分類系數(shù)（＜r＞）。

表1 四個真實網(wǎng)絡的詳細拓撲結(jié)構信息

3.2 人工網(wǎng)絡

為研究網(wǎng)絡社團結(jié)構對算法性能的影響，四個由LFR 模型［34］生成的人工網(wǎng)絡被用來進一步評估算法的性能。在LFR 模型中，網(wǎng)絡節(jié)點度和社團大小都服從冪律分布，其指數(shù)分別為θ1和θ2。通常地，兩個指數(shù)θ1和θ2的取值范圍分別為2≤θ1≤ 3和1≤θ2≤ 2?；旌蠀?shù)μ控制著網(wǎng)絡社團結(jié)構的強弱，即μ越小，社團結(jié)構越強。從表2 中可以看出，在生成四個人工網(wǎng)絡時，除混合參數(shù)μ不同外，其他三個參數(shù)θ1，θ2和＜w＞均相同。對網(wǎng)絡LFR1 和LFR2來說，它們的μ值分別為0.1 和0.2，因此它們具有較強的強社團結(jié)構；反之，對于網(wǎng)絡LFR3 和LFR4 來說，它們的μ值分別為0.5 和0.6，因此它們具有較弱的社團結(jié)構。表2 描述了四個人工網(wǎng)絡的詳細拓撲結(jié)構信息，分別包含節(jié)點數(shù)（）、邊數(shù)（）、度指數(shù)（θ1）、社團指數(shù)（2θ）、混合參數(shù)（u）和網(wǎng)絡的平均度（＜w＞）。

表2 四個人工網(wǎng)絡的詳細拓撲結(jié)構信息

4 實驗分析

4.1 真實網(wǎng)絡

首先，在四個真實網(wǎng)絡上評估了不同p=k/n對ADScore 算法性能的影響，其中k和n分別表示關鍵節(jié)點個數(shù)和網(wǎng)絡節(jié)點個數(shù)，因此p表示關鍵節(jié)點的占比，實驗中參數(shù)λ=1.2 和β=1/＜w＞，實驗結(jié)果是200 次獨立運行的平均值，結(jié)果如圖2 所示。從圖2 可知，ADScore 算法在絕大部分情況下都優(yōu)于其它基準算法。具體地說，在網(wǎng)絡Dimension 上，當p≤0.05時，ADScore 算法的F(tc)與其他算法的F(tc)比較接近；當p＞0.05時，ADScore 算法開始優(yōu)于所有基準算法；尤其當p= 0.09時，與表現(xiàn)最差的Hindex 算法相比，ADScore 算法的F(tc)提升了17.8%。在網(wǎng)絡AS_dataset 上，當p≤0.02時，WVoteRank 與ADScore兩個算法表現(xiàn)最好，它們的F(tc)非常接近；當p＞ 0.02時，ADScore 算法開始優(yōu)于所有基準算法；同樣的，在p=0.09時，ADScore 算法與表現(xiàn)最差的Hindex 算法相比，F(xiàn)(tc)提高了11.5%。在CE-GN 網(wǎng)絡上，對于所有p，ADScore 算法始終優(yōu)于所有基準算法；在p=0.09時，ADScore 相比表現(xiàn)最差的Hindex 算法來說，F(xiàn)(tc)提升了11.9 %。在LastFM 網(wǎng)絡上，當p≤0.02時，四個算法ADScore、WVoteRank、Hindex 和Betweenness 的F(tc)比較接近，但都比Coreness 方法高；然而，當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)絡上的性能都不比其他四個基準方法差；對于較大的p，ADScore 算法在所有網(wǎng)絡上的表現(xiàn)都是最好的；（2）與ADScore 算法相比，四個基準算法的性能表現(xiàn)并不穩(wěn)定。比如，WVoteRank 算法在Dimension 網(wǎng)絡上的性能僅次于ADScore 方法；然而，在LastFM 網(wǎng)絡上，當p＞0.05時，它的性能卻是所有算法中最差的，因此ADScore 算法的性能相比其他算法具有更強的穩(wěn)定性。

圖2 在四個真實網(wǎng)絡上隨p 變化的 F (tc)

其次，在四個真實網(wǎng)絡上評估了不同傳播率λ對ADScore 算法性能的影響，其中p=0.05，以及β=1/＜w＞，實驗結(jié)果是200 次獨立運行的平均值，結(jié)果如圖3 所示。從圖3 可以看出，對所有λ，ADScore 算法的性能在所有網(wǎng)絡上都優(yōu)于所有基準算法。另外，隨著λ的增加，所有算法的F(tc)在大部分情況下也會隨之增加。然而，與其他四個基準算法相比，ADScore 算法在大部分情況下的性能提升相對更大。在Dimension 網(wǎng)絡上，當λ=1.0 時，ADScore 算法與表現(xiàn)第二好的Hindex 算法相比，F(xiàn)(tc)只提升了3.5%；而當λ=1.5 時，ADScore 算法與Hindex 算法相比F(tc)的提升卻高達9.2%。由此可以看出，當λ較大時，ADScore 算法相對其他算法的性能提升也會變得更大。類似地，在AS_dataset 網(wǎng)絡上，當λ=1.0 時，ADScore算法相比第二好的Hindex 算法F(tc)提升只有2.7%；而當λ=1.5 時，ADScore 相比Hindex 算法F(tc)提升卻有7.8%。在CE-GN 網(wǎng)絡上，當λ=1.0 時，ADScore 算法相對第二好的Betweenness算法性能F(tc)提升了 4.2%；而當λ=1.5 時，兩者相比，ADScore 算法性能F(tc)提升了8.1%。同樣，在LastFM 網(wǎng)絡上，當λ=1.0 時，ADScore 算法相比第二好的Hindex 算法F(tc)提升了6.3%；而當λ=1.5 時，ADScore 算法相比Hindex 算法F(tc)的提升高達10.8%。綜合以上分析，ADScore 算法在λ較大時相比其他算法具有更大的性能優(yōu)勢。

圖3 在四個真實網(wǎng)絡上隨 變化的 F (tc)

4.2 人工網(wǎng)絡

進一步在四個具有不同社團結(jié)構的人工網(wǎng)絡上評估ADScore 算法的性能。在實驗中，設置參數(shù)p=0.05，λ=1.5 和β=1/10。每個數(shù)據(jù)都是 200次獨立運行結(jié)果的平均值，實驗結(jié)果如表3 所示。從表3 可以看出，ADScore 算法的性能在四個人工網(wǎng)絡上都優(yōu)于其他四個基準方法。比如說，在社團結(jié)構強度較強的LFR1 網(wǎng)絡上，ADScore，WVoteRank，Coreness，Betweenness 和Hindex 算 法F(tc)分 別為0.397，0.361，0.339，0.349 和0.352，其中ADScore算法的F(tc)最高，Coreness 算法最低，兩者相比，ADScore 算法的性能提高了17.1%。類似地，在社團結(jié)構強度較弱的LFR4 網(wǎng)絡上，ADScore 算法的性能表現(xiàn)依然是最好的，與Betweenness 算法相比性能提升了15.8%。此外，也可以看到網(wǎng)絡社團結(jié)構的強弱對所有算法性能的影響都非常小。比如說，在社團結(jié)構比較強的LFR1 網(wǎng)絡上和社團結(jié)構比較弱的LFR4 網(wǎng)絡上，ADScore 算法的F(tc)分別為0.397 和0.395，兩者僅相差0.2 %；類似地，WVoteRank，Coreness，Betweenness 和Hindex 算 法分別相差0.8%，0.5%，0.8%和1.0%。由此可以看出，與其他四個基準算法相比，ADScore 算法不僅在社團結(jié)構強度較強的網(wǎng)絡上具有優(yōu)勢，而且在社區(qū)結(jié)構強度較弱的網(wǎng)絡上同樣具有優(yōu)勢。

表3 在四個具有不同社團結(jié)構的人工網(wǎng)絡上的實驗結(jié)果

5 結(jié)論

許多傳統(tǒng)的識別一組關鍵節(jié)點的算法都只考慮了單個關鍵節(jié)點在網(wǎng)絡中的重要性，而忽略了關鍵節(jié)點之間的分布，因此常常導致選擇的一組關鍵節(jié)點集中在少數(shù)區(qū)域，從而無法最大化信息的傳播范圍?；谏鲜鲈?，本文提出了一種啟發(fā)式的一組關鍵節(jié)點識別算法ADScore。在算法ADScore 中，每個節(jié)點的重要性取決于它的一階鄰居節(jié)點和二階鄰居節(jié)點的打分能力，而一階鄰居節(jié)點的打分能力又取決于它是否與關鍵節(jié)點相鄰，該策略保證了選擇的一組關鍵節(jié)點盡可能的分散。在真實網(wǎng)絡和人工網(wǎng)絡上的實驗表明ADScore 算法具有以下五個結(jié)論：（1）與四個基準方法相比，p值越大，它越具有優(yōu)勢；（2）相比其他四個基準方法的性能表現(xiàn)，ADScore 算法的性能具有更強的穩(wěn)定性；（3）與四個基準方法相比，傳播率λ越大，它越具有優(yōu)勢；（4）在具有任何社團結(jié)構的網(wǎng)絡上，它都優(yōu)于其他四個基準方法。