背景圖增強的社交網絡重要節點自適應排序算法

摘 要：社交網絡中的重要節點對網絡結構和功能具有決定性影響，開發精度更高的重要節點排序算法成為當前的研究熱點之一。其中，LR（LeaderRank）引入一個背景節點明顯提升了經典PageRank排序算法的性能，但仍面臨著網絡中小出度用戶的投票權偏見問題。因此，提出背景圖增強的社交網絡重要節點自適應排序算法AGR（adaptive GraphRank），構建多節點背景圖替代LR的單一背景節點，基于H指數設計有偏向的隨機游走，緩解投票權偏見。調參實驗初步確定了背景圖的最優規模和結構;與K-TOPSIS等現有優秀算法進行對比實驗，驗證了AGR在傳播、瓦解、魯棒性三個關鍵維度上的性能提升;實際案例檢驗了算法在真實場景下的有效性。綜上，AGR有效緩解了投票權偏見，提高了排序精度，展示出較優的性能和應用潛力。

關鍵詞：重要節點；LeaderRank；adaptive GraphRank；背景圖；H指數

中圖分類號：TP393"" 文獻標志碼：A"" 文章編號：1001-3695（2025）03-013-0742-07

doi：10.19734/j.issn.1001-3695.2024.07.0300

Self-adaptive algorithm for ranking important nodes in socialnetworks enhanced by ground graph

Feng Junyou，Chen Lizhou，Liu Xianbo，Xu Xuanxiang，Du Yanhui

（College of Information Network Security，People’s Public Security University of China，Beijing 100038，China）

Abstract：Important nodes in social networks have a decisive influence on the network structure and function.Developing more accurate ranking algorithms has become one of the current research hotspots.LR（LeaderRank）introduces a ground node，significantly improving the performance of the classic PageRank.However，it still faces the voting bias problem of users with small out-degrees in the network.Therefore，this paper proposed AGR（adaptive GraphRank），a self-adaptive algorithm for ranking important nodes in social networks enhanced by ground graph.AGR constructed a multi-node ground graph to replace LR’s single ground node and designed a biased random walk based on the H-index to alleviate voting bias.Preliminary para-meter experiments determine the optimal scale and structure of the ground graph.Comparative experiments with excellent existing algorithms such as K-TOPSIS verify AGR’s performance improvements in three key dimensions：propagation，disintegration，and robustness.A real-world case study further demonstrates the effectiveness of the algorithm in practical scenarios.In conclusion，AGR effectively reduces voting bias，improves ranking accuracy，and shows superior performance and application potential.

Key words：important node;LeaderRank;adaptive GraphRank;ground graph;H-index

0 引言

社交網絡中的重要節點是指相比普通節點而言，能夠在更大程度上影響網絡的結構與功能的特殊節點［1］，雖然數量較少，但其影響卻可以快速波及整個網絡，是網絡的核心角色［2］。例如微博中最有影響力的幾個用戶所發的微博很快就能傳遍整個網絡［3］。準確識別這些節點并進行節點重要性排序對于輿情管控等工作意義重大。

目前普遍認為，重要節點在網絡中占據了關鍵位置，控制著網絡中的信息流動和傳播，支撐著網絡結構的穩定性，最終獲得了顯著的影響力［4］。基于該思路，出現了多種網絡重要節點排序算法，如基于節點鄰近、路徑和特征向量的算法等［5～7］，其中PR（PageRank）算法［8］是一個重要里程碑。PR算法最初用于評估網頁的重要性，后來被廣泛應用于各類復雜網絡分析中［9］。在其基礎上，LR（LeaderRank）［10］引入一個背景節點與原始網絡中的所有節點雙向連接，構建了一個新的強連通網絡，解決了PR的懸掛節點問題，提供了一種無參數且更簡潔的算法形式，表現出更快的收斂速度和更高的魯棒性。WLR（weighted LeaderRank）［11］將LR應用于有權重的網絡，根據節點的度為節點到背景節點的對應鏈接賦予權重，使得度數高的節點能獲得更高的分數，從而更有效地識別網絡中的關鍵影響者。ALR（adaptive LeaderRank）［12］在LR和WLR的基礎上引入H指數，根據節點的H指數進行有偏向的隨機游走，進一步提升了算法性能，是目前LR家族中較為突出的改進。后來Wang等人［13］提出了一種考慮局部網絡特征的LR變體，Fu等人［14］提出改進的SLR用于重大傳染病流行風險識別。而在其他幾種思路下，KT（K-TOPSIS）［15］是近期一個較好的改進，它在K-shell分解的基礎上引入TOPSIS，解決了K-shell只能有效識別單個最具影響力節點的問題，取得了較好的結果。然而，文獻［10］提出LR系列算法中仍存在小出度用戶的投票權偏見問題。這是指一些節點只有極少的幾個鄰居節點，導致它們在投票時會將自身的全部分數都分配給僅有的這幾個鄰居，最終導致強烈的偏見。為了緩解這種偏見進而提高LR的精確性，本文提出了一種背景圖增強的社交網絡重要節點自適應排序算法AGR（adaptive GraphRank）。AGR構建一個多節點的復雜背景圖（ground graph）替代LR中的單一背景節點，為小出度節點提供了明顯更多的游走路徑，使它們能夠更多地將分數分配給代表通用信息的多節點背景圖，而不是全部集中于極少的幾個鄰居節點。在此基礎上，AGR建立基于H指數［16］的轉移矩陣，指導隨機游走過程中的資源分配，降低小出度節點在隨機游走過程中的地位，從源頭上直接減少其投票權從而緩解偏見，最終實現更精確的排序。AGR對偏見的緩解效果將在1.2節進行詳細討論。需要注意的是，應當證明引入背景圖和H指數的合理性，即整個隨機游走過程仍滿足LR的基本要求并保證其最終收斂到唯一穩態，1.1節將對此進行詳細論述。

本文的主要貢獻如下：a）構建多節點的復雜背景圖替代LR中的單一背景節點與原始網絡雙向連接，對偏見分數進行分流，設計了簡化的重要節點排序算法GR；b）在貢獻a）的基礎上，構建轉移概率與目標節點H指數正相關的轉移矩陣，具體指導每一步隨機游走過程中的資源分配，構建排序算法AGR；c）調參實驗研究了背景圖的規模、拓撲結構對算法性能的影響；對比實驗驗證了AGR相對LR等現有算法的性能優勢；真實案例驗證了AGR的良好應用效果。

1 背景圖增強的社交網絡重要節點自適應排序算法AGR

對社交網絡中的重要節點進行排名時，先將真實網絡抽象成一個由N個節點和E條有向邊組成的有向圖，節點代表用戶，邊代表用戶之間的關系。在進行排序之前，在現有有向圖之外，AGR單獨構建一個n個節點e條邊的背景圖。本文中的背景圖規模選擇13個節點，使用常用的Barabasi-Albert（BA）模型［17］生成，背景圖內部均使用雙向邊，保證其內部的強連通性，此處規模和結構對性能的影響將在3.1節中詳細闡述。參考LR的連接方法，將背景圖的每個節點與原始網絡中的每個節點建立雙向連接，保證了新網絡是一個強連通網絡。這樣，排序過程不僅考慮了用戶之間的直接聯系，還考慮了通過背景圖共享的公共信息，更準確地評估每個用戶的影響力［10］。背景節點和背景圖的結構差異如圖1所示。

為了開始排序，除了背景圖中的節點之外，首先給每個節點分配一個單位初始資源，按照一定比例通過有向邊將資源分配給其鄰居。這相當于有向網絡上的隨機游走，由轉移矩陣P來描述，P中每個元素表示游走者從某一節點j向i進行跳轉的轉移概率。如果此時執行類似LR的標準隨機游走，即節點j以相同的比例向它的每個后繼鄰居節點分配資源，則節點j到任意后繼鄰居節點的轉移概率均相同，這將得到AGR的簡化版本GR。具體的分數更新規則見式（1）。

Si（t+1）=∑N+nj=1ajidoutj×Sj（t）

（1）

其中：n為背景圖的節點數；Si（t+1）代表第t+1輪迭代中節點的GR分數；Sj（t）代表第t輪迭代中節點j的GR分數；aji/doutj表示j到i的轉移概率;doutj為j的出度，當邊j到i存在時，aji為1，否則為0；多輪迭代達到穩態之后，Si（t+1）即為節點i的重要性分數。

與LR、GR不同，AGR認為應當根據節點的H指數［16］有傾向性地分配資源。H指數既能反映節點的連接數量，又能體現與節點相鄰的其他節點的質量，按照H指數分配資源，允許AGR在每次隨機游走過程中考慮與目標節點相連的其他節點的質量，兼顧更多的網絡拓撲信息。這樣就能夠降低大部分小出度節點在隨機游走過程中的地位，從源頭上直接減少其投票權，緩解偏見。H指數的計算方式如下，首先定義一個運算符H，它作用于有限個實數（x1，x2，x3，…，xn）并返回一個整數y=H（x1，x2，x3，…，xn），其中y是使得實數集中至少有y個元素不小于y的最大整數。而對于復雜網絡中的某一節點i，其H指數表示為hi=H（dj1，dj2，dj3，…，djdi），其中（j1，j2，j3，…，jdi）代表節點i的di個鄰居節點，di為i的度。AGR利用網絡中每個節點的H指數構建加權的轉移矩陣P，其中每個節點向鄰居節點轉移概率與該節點的H指數正相關，使得資源更傾向于流向H指數較高的節點，由于背景圖節點不參與最終排名，其H指數統一設為1。具體轉移概率和分數更新規則見式（2）。

Si（t+1）=∑N+nj=1ajihi∑N+nk=1ajkhk×Sj（t）

（2）

其中：k為添加了背景圖的新網絡中的任意節點；ajihi/∑N+nk=1ajkhk代表j到i的轉移概率，表示節點i的H指數占所有節點j的后繼鄰居節點的H指數之和的比例，它與hi始終正相關。

多輪迭代達到穩態之后，Si（t+1）即為節點i的重要性分數。該算法的主要工作流程如下：a）構建背景圖，并使其中節點與原網絡所有節點雙向連接；b）計算網絡中所有節點的H指數，背景圖H指數設為1;c）初始化節點的AGR分數，普通節點設為1，背景節點設為0;d）基于節點間的轉移概率，迭代更新分數，直到達到穩定狀態。

1.1 AGR的隨機游走過程

LR執行標準隨機游走，其中隨機游走者移動到其每個鄰居的概率是相同的。AGR則基于H指數的有偏隨機游走，其中的隨機游走者始終傾向于訪問具有較高H指數的節點，無論隨機游走者位于背景節點還是普通節點。下面證明這種新構造的隨機游走始終能夠收斂到一個唯一穩態。

對于一個由節點和邊構成的有向圖，假設存在一個正整數n，使得對于所有節點對（i，j），在n步內從i到j的轉移概率都大于零（即矩陣P中的所有元素都大于零），則該矩陣為本原隨機矩陣。根據Perron-Frobenius定理，本原隨機矩陣有一個唯一的最大特征值1，并且與之關聯的特征向量（即穩態向量）是唯一的且所有元素均為正數，因而只需證明本文構建的隨機矩陣是本原的，即可證明隨機游走的唯一收斂性。

由于背景圖和原始網絡的所有節點雙向連接，且其內部也是強連通的，這確保了新構建的網絡中，任意節點都能夠訪問任意其他節點，背景圖也同樣如此，因而新網絡也是強連通的。所以，任意節點均擁有至少1個前驅和后繼鄰居節點，在新網絡中，任意節點H指數至少為1，對于任意節點j到i，只要其連邊j到i存在，轉移概率pji=ajihi/∑N+nk=1ajkhk必然大于0。因此，每個節點都能夠在n步之內訪問到任意其他節點。

綜上，對于AGR工作的網絡，始終存在一個正整數n，使得對于所有節點對（i，j），必然存在正整數n使得n步內任意節點j到i的轉移概率大于零，因此轉移矩陣P是本原的。這意味著無論初始狀態如何，基于該轉移矩陣的隨機游走過程最終都將收斂到這個穩態向量，所有節點的分數必將穩定。此時假設存在另一個與特征值1相關的特征向量，由于矩陣是本原的，任何這樣的特征向量必須與第一個特征向量成正比，特征向量是唯一的。綜上所述，AGR隨機游走的過程中，其最終的節點分數必將收斂到一個唯一穩態。

1.2 AGR對投票權偏見的緩解效果

下面分析新算法對小出度用戶的投票權偏見的緩解效果。假設原始網絡中有節點j出度為dj，其在PR算法中，不考慮隨機跳轉的情況下，向其任意后繼節點i的轉移概率為1/dj，LR為1/（dj+1），而在AGR中為hi/∑dj+13k=1hk，若所有節點H指數均相同，該概率為1/（dj+13），可以看出對于一個小出度節點來說，背景圖中的13個節點相比單一背景節點極大降低了其訪問原始網絡中后繼節點的概率。進一步考慮其H指數會發現，由于節點j出度更小，一般其H指數也就更低，可以認為hilt;hk，同樣可以推出其訪問有原始網絡中后繼節點的概率更低。另外，其本身H指數較小，所以當作為被分配的后繼節點時，這個小出度節點從其他節點獲取分數的能力也更低，這從源頭上限制了其投票權。類似地，可以推出較大出度的節點受到的影響相對較小，這保證了AGR更多地針對小出度節點進行修正，而不是像PR那樣使用固定的隨機跳轉概率簡單地修正所有節點。這意味著AGR能夠像LR那樣自動根據節點出度來調整其訪問背景圖和訪問原始網絡的概率，保留了LR的自適應特性。綜上，AGR確實進一步緩解了系列算法的投票權偏見。

1.3 AGR的時間和空間復雜度

LR的每一輪迭代需要遍歷整個網絡中的每一個節點，計算其本輪LR分數，也就是需要遍歷N+1個節點。而針對每個節點i，需要遍歷其每一個前驅節點j，獲取j到i的轉移概率以及j上一輪的LR分數，算出i本輪的分數，該過程的時間復雜度可以近似為O（t（N+1）dinaverage），dinaverage表示網絡中所有節點的平均入度，t表示整個迭代輪次數，一般處于50～100次迭代就可以獲得較好的結果［18］。類似地，AGR算法用背景圖替代了背景節點，需要遍歷N+13個節點后獲取轉移概率及分數，其時間復雜度可以近似為O（t（N+13）（dinaverage+13））。

空間復雜度方面，LR算法需要存儲整個網絡的節點列表和邊列表，其空間復雜度約為O（（N+1）+（E+N）），其中E為原始網絡中的連邊數。類似地，AGR的空間復雜度約為O（（N+13）+（E+13×N+e））。在本文研究的社交網絡中，一般針對某一社群或者某一目標群體進行重要性排序，因此AGR的開銷是可以接受的。

2 實驗數據和評價方法

2.1 數據

實驗包括八個不同規模和類型的真實社交網絡數據集，包括動物社群、傳染病傳播、犯罪團伙關系、傳統社交媒體以及互聯網社交媒體等多種類型，涵蓋了從微型到中大型多種規模的社交網絡，有助于全面評估算法的適用性和真實性能。每個數據集詳細的網絡拓撲特征見表1，其中N表示網絡中的節點個數，E為邊數，〈d〉為節點的平均度數，dmax為最大度數，δ為網絡直徑。

karate為某空手道俱樂部的成員間的關系［19］；Facebook為社交平臺的用戶及其好友關系［20，21］；dolphin描繪了某海域中海豚之間的社交互動關系［21，22］；crime展示了犯罪分子之間的共犯關系［21］;COVD記錄了一條獨立的新冠病毒傳播鏈［23］;arenas-email表示一所大學的電子郵件通信網絡［21，24］；arenas-pgp表示PGP網站用戶的互動網絡［21，25］;advogato表示在線社區平臺用戶的認證關系網絡［21，26］。

2.2 評價方法

一般從三個關鍵維度評估網絡重要節點排序算法的性能：

a）傳播模擬實驗。測試算法結果中的重要節點在網絡中傳播信息的能力，更重要的節點傳播疾病或信息的能力應當更強。

b）網絡瓦解實驗。測試刪除算法結果中的重要節點對網絡連通性的影響，重要節點的移除應該會導致網絡結構更迅速地瓦解，網絡連通性下降更快。

c）魯棒性實驗。檢驗算法在面對網絡連邊噪聲時的魯棒性，魯棒性更強的算法應該能在網絡噪聲環境中保持更穩定的評分，添加噪聲前后的評分變化應當更小。

2.2.1 傳播模擬實驗

針對維度1開展SIR傳播模擬實驗。實驗使用SIR模型，這是一種傳染病動力學模型［27，28］，可以模擬疾病、信息的一般傳播過程，本文將其用于評估算法排序結果中節點的傳播能力。模型將人群分為易感者susceptible、感染者infected和移除者recovered三個狀態，模擬三個狀態人群數量的動態變化來分析疾病、信息如何在網絡中傳播。使用式（3）描述三個組別中人數隨時間的演化。

dSdt=-β×S×IdIdt=β×S×I-γ×IdRdt=γ×I

（3）

其中：β表示傳染率；γ表示康復率；S表示易感者數量；t表示時間步；I表示感染者數量；R表示康復者數量；N表示總人數。下文實驗中，感染率β均設置為0.3，免疫率γ為0.05。

將不同算法排序得出的重要節點作為傳播源節點即初始感染者I進行傳播模擬，模擬過程中使用SIR_index指標描述每一個傳播時間步下的傳播規模，具體見式（4）。

SIR_index=I+RN

（4）

該指標反映了某一時間步下感染和康復人數占總人口的比例，該指標越大，傳播規模越廣。各種算法取相同數目的重要節點作為源節點，記錄整個傳播過程的SIR_index，分析在相同時間步的傳播規模即可得出本次傳播過程的速度和范圍，判別不同算法得到的源節點的傳播能力，進而驗證算法的排序精度。

2.2.2 網絡瓦解實驗

針對維度2開展網絡瓦解實驗。該實驗的原理是網絡中重要節點的移除應當更大程度地破壞網絡的連通性［29］，主要的連通性指標包括連通組件的數量、節點間的連通性、巨連通組件（GCC）的規模等。在眾多指標中，GCC因其與網絡的最優攻擊和最優傳播策略緊密相關而被廣泛使用［30，31］。巨連通組件指一個圖中最大的連通子圖在圖中占據主導地位，通常包含圖中絕大多數的節點，是研究網絡全局性質的重要依據，組件的規模即節點數。網絡瓦解實驗按照算法排序結果逐個刪除網絡中的節點，記錄每一步的巨連通組件規模，分析相同步的規模即可得出本次節點刪除過程中網絡的瓦解速度，判別不同算法得出的重要節點對網絡連通性的影響力，進而驗證算法精度。

為了量化描述整個瓦解過程的算法性能，引入文獻［32］設計的指標ANC。ANC反映了節點刪除過程中網絡連通性減弱的總體速度，具體見式（5）。

ANC=1N∑Nk=1σ（G＼{v1，v2，…，vk}）σ（G）

（5）

其中：σ（G＼{v1，v2，…，vk}）表示刪去第k個節點后剩余網絡的巨連通組件大小；N為原始網絡的節點數，即待刪除節點序列的節點個數；σ（G）是進行節點移除前巨連通組件的大小，該指標越低，按序進行節點移除導致網絡連通性降低的速度越快，算法性能越好。

2.2.3 魯棒性實驗

針對維度3進行魯棒性實驗。考慮到數據獲取過程中存在各種問題，數據集中可能存在大量虛假和缺失連邊，影響節點排序的精度，因此，排序算法對連邊噪聲的容忍度尤為重要［33］。參考文獻［10］，在網絡中人工添加、刪去一定比例的連邊模擬這種噪聲，使用其構建的魯棒性指標IS量化算法結果的變化程度，進而評估算法的魯棒性，具體見式（6）。

IS=∑Ni=1|S′i-Si|

（6）

在N個節點的網絡中，Si和S′i分別對應相同算法下相同節點i在無噪聲網絡和有噪聲網絡中得到的分數，IS計算了所有節點在有噪聲和無噪聲網絡下的分數差之和，IS值較高意味著算法對噪聲的敏感度高，算法穩定性較低，魯棒性較差。

3 實驗分析

使用Python編程語言在PyCharm集成開發環境中實現了所有算法和實驗。數據集均以邊列表形式存儲，網絡分析和實驗操作主要依賴于NetworkX庫，最終的實驗結果使用Matplotlib庫進行繪制。

3.1 調參實驗

為了全面評估AGR算法中背景圖的參數（包括規模和拓撲結構）算法精度的影響，不僅在八個真實社交網絡上進行了驗證，還構建了小世界網絡、無標度網絡、隨機網絡三類各5個規模的人工模擬網絡參與評價，共在23個網絡數據集進行了傳播和網絡瓦解實驗，盡可能全面地評估背景圖的最佳參數。

3.1.1 背景圖規模n

采用BA模型構建背景圖，選擇{1，3，5，…，19}作為背景圖的規模n，對應背景圖中包含1、3、5到19個節點。在此基礎上構建對應的AGR_n算法并對每個數據集進行節點重要性排序，取各算法排序結果的前30%節點作為源節點在各自數據集上進行傳播的模擬實驗，每次實驗進行1 000次獨立傳播模擬，記錄SIR_index并取平均值。取傳播結束時SIR_index的最大值，也就是最大傳播規模，作為算法在單一數據集上的性能得分，所有數據集的平均分作為該算法的最終得分，實驗結果如圖2所示。

類似地，進行網絡瓦解實驗，計算所有算法在所有數據集上進行節點刪除過程的ANC指標，根據該指標對一個數據集上的不同算法進行排名。實驗完成后取一個算法在所有數據集的名次平均值作為該算法的最終名次，實驗結果如圖3所示。

圖2中SIR實驗的平均結果表明，算法性能隨背景圖節點數增加而不斷提升，在大于等于11時提升效果放緩。圖3中網絡瓦解實驗的平均結果表明，當背景圖節點數取91時，按照算法排序結果刪除網絡中的節點能夠最快地瓦解網絡，且繼續增加節點數，算法性能呈現下降趨勢，不過節點數取11時仍能保持較高的性能。

3.1.2 背景圖拓撲結構

在確定了最佳節點規模之后，還需要對背景圖的拓撲結構進行討論。采用9種經典的網絡建模方法構建背景圖，這些方法構建的網絡各自具有鮮明的拓撲結構特征，具體見表2。

實驗發現，使用所有結構的背景圖構建AGR在23個網絡數據集上的排序結果差別極小。具體來說，將每個算法在某一網絡數據集的排序結果取平均值，計算各算法排序結果和該平均結果的Kendall τ相似性系數［34］，見式（7）。

τ=P-Q（P+Q+T）（P+Q+U）

（7）

其中：τ表示兩個排序結果之間的Kendall τ系數，該系數常用于評估兩個排名列表之間的相似程度；P表示兩個排名中一致對的數量，即兩個排名都認為一個項目應該在另一個項目之前；Q表示不一致對的數量，即兩個排名對于項目順序的判斷是相反的；U和T分別表示兩個排序中的平局對數量。該系數的取值為-1～1，1表示兩個排名完全一致，-1表示完全相反，0表示關聯較小。

對每個網絡數據集進行上述操作，記錄每個數據集上的所有算法與平均排序結果的相似性，結果如圖4所示。由圖4可見，所有算法的排序結果和平均排序結果的Kendall τ系數幾乎都是1，也就是說這些排序結果幾乎完全一致，背景圖拓撲結構對于AGR算法的排序結果影響極小。本文背景圖僅采用當前常用的BA模型生成，該模型生成的網絡具有無標度特性，符合真實網絡的拓撲特點。

兩個實驗的結果表明，當篩選傳播能力更高的節點時，背景圖規模可以適當提高，更大的規模可以帶來一定的效果提升；當篩選網絡瓦解能力更強的節點時，背景圖規模為9時更合適，此時篩選出的節點已經能夠較快瓦解網絡，繼續增大規模反而會影響效果。綜合來看，選用11個節點，可以在保證瓦解能力的同時獲得更好的傳播能力，總體性能更好。而背景圖拓撲結構對排序結果影響不大。

3.2 對比實驗

在8個真實網絡數據集中，將AGR、GR與PR、LR、ALR、K-Topsis幾個現有算法在三個維度上進行對比實驗以驗證AGR的綜合性能。其中GR主要與LR、PR兩個算法對比，用于分析其他方面均相同的情況下，構建背景圖和背景節點的算法之間的性能差異，進而驗證背景圖結構引入的效果。不同于調參實驗中僅描述算法的最終實驗性能，對比實驗希望盡可能公平地描述各個算法的效果，因而直接展示實驗完整的過程。

3.2.1 傳播實驗

采用每個算法中排名前30%的節點作為傳播源節點進行傳播實驗，為了凸顯算法結果的差異性，還對源節點進行了去重，排除了所有算法中排名都相同的重復節點。在八個真實網絡上進行1 000次獨立傳播模擬，記錄每次模擬過程的SIR_index并取平均值，最終實驗結果如圖5所示。

實驗結果表明，相比本系列其他算法，AGR識別出的源節點始終展現出最好的傳播能力：在傳播的前中期表現出了更快的傳播速度，在最終階段也能夠將信息傳播到更大范圍、更多數量的節點。而相比最新的K-Topsis，AGR也達到了持平的效果。另外，在與LR的對比中，簡化的GR在大部分情況下性能更好，這驗證了僅將單一背景節點替換成背景圖即可有效提升算法的識別精度。

3.2.2 網絡瓦解實驗

按照不同算法在數據集上的排序結果刪去網絡中的節點，記錄每次刪除節點后的GCC規模直到節點數趨于穩定。不同于調參實驗，這種方法可以分析整個瓦解實驗過程中巨連通組件規模的變化情況，更精確地判斷瓦解過程中網絡瓦解的速度和幅度，進而評估算法的排序精度，實驗結果如圖6所示。

實驗結果表明，在所有數據集中，按照AGR的排名移除節點時，巨連通組件GCC的大小下降速度和幅度均較為出色，始終能在較小的移除數目下將網絡巨連通組件規模降到極低。在五個網絡中，AGR效果最好，移除更少的節點就能最快縮小巨連通組件的規模。深入研究AGR未能取得最佳效果的advgato和COVD數據集，可以發現同樣使用了H指數的ALR算法效果不佳，而未使用H指數的GR排名第一。因此，AGR并未取得最佳效果是因為H指數在這兩個數據集中未能較好地評價那些支撐網絡結構穩定性的節點。另外，最新的K-Topsis在部分數據集的瓦解前期有一定的優勢，但是總體效果明顯不佳，而AGR在所有數據集中均能保持較好的效果，排序結果較為精準的同時具有更好的通用性，綜合性能更好。

同時，相比傳統的PR和LR，簡化的GR在幾乎所有網絡中都顯著提升了瓦解速度，展現了較快的網絡瓦解速度和較大的瓦解幅度，在advogato網絡中甚至排名第一，這驗證了背景圖策略的合理性。

3.2.3 魯棒性實驗

為了比較算法面對網絡噪聲的魯棒性，在八個網絡中按不同比例隨機增刪網絡中的連接，模擬真實網絡中的連邊噪聲環境，計算不同算法在各個增刪比例下的IS，分析其評分變化程度。由于K-Topsis與PR系列算法原理不同，此處不參與評價。進行50次重復實驗并計算平均值，實驗結果如圖7所示。

結果表明，ALR在面對網絡連邊噪聲時常常顯示出較低的魯棒性，而構建背景圖替代ALR中單一背景節點的AGR在面對假陽性和假陰性連接時的IS相對ALR始終更小，這表明背景圖很好地提升了ALR的抗連邊噪聲能力，增強了算法的穩定性和可靠性。一種可能的解釋是，AGR使用背景圖替換ALR的單一背景節點，在網絡中新增了大量代表通用信息的背景圖的合理雙向連接，從而弱化了連邊噪聲在網絡中的影響。

同時，GR在各個網絡中的IS指標始終保持在五個算法的最低水平。換句話說，當網絡中出現了連邊噪聲時，GR的評分偏差在五種算法里始終最小，顯示出最好的魯棒性。這驗證了背景圖結構對連邊噪聲的高適應性。

4 真實案例分析

模擬網絡實驗驗證了AGR在仿真場景下的優勢，但仿真場景中表現良好的算法并不一定在真實環境中表現出色。因此，有必要在真實網絡中進行驗證實驗，進一步檢驗算法應用效果。采用文獻［35］構建的某學校信息系統局域網作為實驗數據集，包括30臺PC、5臺接入交換機、1臺匯聚交換機和2臺服務器。該文獻已經通過分析4周的網絡日志、故障信息和安全軟件的攻擊檢測數據，使用期望損失的風險評估方法計算了每個節點的風險值，并給出了真實的風險排序結果。

在此基礎上，將網絡設備抽象為節點，并使用上文所有算法對該局域網中的節點進行排序，與文獻［35］給出的真實風險值排序結果進行比較，以驗證算法能否識別出該局域網中風險值更高的重要節點（設備），實驗結果如表3所示。

如表3所示，AGR得到該網絡的節點重要性排序與風險評估得到的網絡節點風險值排序的top 6是完全一致的，在所有排序結果中效果最好。結果表明，AGR得到的節點重要性排序結果能夠為網絡節點的風險評估、重要節點防護和網絡中節點的風險處置優先級排序提供依據，在本案例中有著較好的應用效果。

5 結束語

針對社交網絡提出一種新的重要節點排序算法AGR，構建多節點背景圖替代單一背景節點，建立基于H指數的轉移矩陣指導隨機游走中的資源分配，緩解PR系列算法中小出度節點的投票權偏見，提高了排序精度。實驗研究了背景圖的最優規模和拓撲結構；與K-Topsis等現有算法相比，AGR在三個關鍵維度表現出相當的競爭力，在進一步提升排序精度的同時兼具較好的魯棒性，是更平衡的算法；真實案例進一步檢驗了算法的應用效果。但是，不同規模的網絡中如何選擇最優背景圖、背景圖和原始網絡的各種連接方式對算法性能的影響尚未深入研究。

參考文獻：

［1］任曉龍，呂琳媛.網絡重要節點排序方法綜述［J］.科學通報，2014，59（13）：1175-1197.（Ren Xiaolong，Lyu Linyuan.Review of ranking nodes in complex networks［J］.Chinese Science Bulletin，2014，59（13）：1175-1197.）

［2］Albert R，Jeong H，Barabasi A L.Error and attack tolerance of complex networks［J］.Nature，2000，406（6794）：378-382.

［3］Weng Jianshu，Lim E P，Jiang Jing，et al.TwitterRank：finding topic-sensitive influential Twitterers［C］//Proc of the 3rd ACM International Conference on Web Search and Data Mining.New York：ACM Press，2010：261-270.

［4］Pei Sen，Morone F，Makse H A.Theories for influencer identification in complex networks［M］//Lehmann S，Ahn Y Y.Complex Spreading Phenomena in Social Systems.Cham：Springer，2018：125-148.

［5］Kitsak M，Gallos L K，Havlin S，et al.Identification of influential spreaders in complex networks［J］.Nature Physics，2010，6：888-893.

［6］Dolev S，Elovici Y，Puzis R.Routing betweenness centrality［J］.Journal of the ACM，2010，57（4）：article No.25.

［7］羅芳，徐陽，蒲秋梅，等.基于PageRank的多維度微博用戶影響力度量［J］.計算機應用研究，2020，37（5）：1354-1358，1367.（Luo Fang，Xu Yang，Pu Qiumei，et al.Multi-dimensional measure of microblog user influence based on PageRank［J］.Application Research of Computers，2020，37（5）：1354-1358，1367.）

［8］Page L，Brin S，Motwani R，et al.The PageRank citation ranking：bringing order to the Web，1999-66［R］.［S.l.］：Stanford InfoLab，1999.

［9］Gleich D F.PageRank beyond the Web［J］.SIAM Review，2015，57（3）：321-363.

［10］Lyu Linyuan，Zhang Yicheng，Yeung C H，et al.Leaders in social networks，the delicious case［J］.PLoS One，2011，6（6）：e21202.

［11］Li Qian，Zhou Tao，Lyu Linyuan，et al.Identifying influential spreaders by weighted LeaderRank［J］.Physica A：Statistical Mechanics and Its Applications，2014，404：47-55.

［12］Xu Shuang，Wang Pei.Identifying important nodes by adaptive Lea-derRank［J］.Physica A：Statistical Mechanics and Its Applications，2017，469：654-664.

［13］Wang Jingjing，Xu Shuqi，Mariani M S，et al.The local structure of citation networks uncovers expert-selected milestone papers［J］.Journal of Informetrics，2021，15（4）：101220.

［14］Fu Lingmei，Yang Qing，Liu Zheng，et al.Risk identification of major infectious disease epidemics based on complex network theory［J］.International Journal of Disaster Risk Reduction，2022，78：103155.

［15］Liu Xiaoyang，Ye Shu，Fiumara G，et al.Influential spreaders identification in complex networks with TOPSIS and K-shell decomposition［J］.IEEE Trans on Computational Social Systems，2023，10（1）：347-361.

［16］Lyu Linyuan，Zhou Tao，Zhang Qianming，et al.The H-index of a network node and its relation to degree and coreness［J］.Nature Communications，2016，7：10168.

［17］Barabasi A L，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439）：509-512.

［18］Brin S.The PageRank citation ranking：bringing order to the Web［J］.Proceedings of ASIS，1998，98：161-172.

［19］Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977，33（4）：452-473.

［20］McAuley J，Leskovec J.Learning to discover social circles in ego networks［J］.Advances in Neural Information Processing Systems，2012，1：539-547.

［21］Kunegis J.KONECT：the Koblenz network collection［C］//Proc of the 22nd International Conference on World Wide Web.New York：ACM Press，2013：1343-1350.

［22］Lusseau D，Schneider K，Boisseau O J，et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations［J］.Behavioral Ecology and Sociobiology，2003，54（4）：396-405.

［23］韓奕.面向公安業務的社交網絡分析關鍵技術研究［D］.北京：中國人民公安大學，2023.（Han Yi.Research on key technology of social network analysis in public security［D］.Beijing：Chinese People’s Public Security University，2023.）

［24］Guimerà R，Danon L，Díaz-Guilera A，et al.Self-similar community structure in a network of human interactions［J］.Physical Review E，Statistical，Nonlinear，and Soft Matter Physics，2003，68（6）：065103.

［25］Boguá M，Pastor-Satorras R，Díaz-Guilera A，et al.Models of social networks based on social distance attachment［J］.Physical Review E，Statistical，Nonlinear，and Soft Matter Physics，2004，70（5）：056122.

［26］Massa P，Salvetti M，Tomasoni D.Bowling alone and trust decline in social network sites［C］//Proc of the 8th IEEE International Confe-rence on Dependable，Autonomic and Secure Computing.Piscataway，NJ：IEEE Press，2009：658-663.

［27］Pastor-Satorras R，Vespignani A.Epidemic spreading in scale-free networks［J］.Physical Review Letters，2001，86（14）：3200-3203.

［28］Newman M J.Spread of epidemic disease on networks［J］.Physical Review E，Statistical，Nonlinear，and Soft Matter Physics，2002，66（1）：016128.

［29］Cohen R，Erez K，Ben-Avraham D，et al.Breakdown of the Internet under intentional attack［J］.Physical Review Letters，2001，86（16）：3682-3685.

［30］Braunstein A，Dall’Asta L，Semerjian G，et al.Network dismantling［J］.PNAS，2016，113（44）：12368-12373.

［31］Morone F，Makse H A.Influence maximization in complex networks through optimal percolation［J］.Nature，2015，524（7563）：65-68.

［32］Fan Changjun，Zeng Li，Sun Yizhou，et al.Finding key players in complex networks through deep reinforcement learning［J］.Nature Machine Intelligence，2020，2（6）：317-324.

［33］Frantz T L，Cataldo M，Carley K M.Robustness of centrality measures under uncertainty：examining the role of network topology［J］.Computational and Mathematical Organization Theory，2009，15（4）：303-328.

［34］Kendall M G.A new measure of rank correlation［J］.Biometrika，1938，30（1/2）：81-93.

［35］謝麗霞，孫紅紅，楊宏宇，等.基于K-shell的復雜網絡關鍵節點識別方法［J］.清華大學學報：自然科學版，2022，62（5）：849-861.（Xie Lixia，Sun Honghong，Yang Hongyu，et al.Key node recognition in complex networks based on the K-shell method［J］.Journal of Tsing-hua University：Science and Technology，2022，62（5）：849-861.）