基于最低度偏置重啟隨機游走的鏈路預測方法

收稿日期：2022-01-20；修回日期：2022-03-15" 基金項目：國家自然科學基金青年科學基金資助項目（111701435）；國家自然科學基金資助項目（12071364）

作者簡介：李巧麗（1991-），女，河南平輿人，碩士，主要研究方向為復雜網絡動力學、鏈路預測；韓華（1975-），女（通信作者），山東萊州人，教授，博士，主要研究方向為復雜性分析與評價、經濟控制與決策（1104768792@qq.com）．

摘 要：鏈路預測是數據挖掘主題中的一個重要問題。基于隨機游走的相似性方法一般設定游走粒子轉移到相鄰節點的概率是相等的，忽略了節點度值對轉移概率的影響。針對此問題，提出一種基于lowest-degree偏置重啟隨機游走的鏈路預測方法。首先引入最低度偏置函數，對游走粒子的轉移概率進行重新定義，然后將最低度偏置隨機游走策略運用到重啟隨機游走中，探究粒子在游走過程中最低度偏向策略對節點相似度的影響。在九個真實網絡數據集上進行鏈路預測，結果表明，所提方法具有良好的預測精度，且挖掘了更多網絡拓撲結構信息，證明該算法在節點相似性的評估上具有一定的優勢。

關鍵詞：復雜網絡；鏈路預測；重啟隨機游走；最低度偏置

中圖分類號：TP393；N94"" 文獻標志碼：A

文章編號：1001-3695（2022）09-037-2799-05

doi：10.19734/j.issn.1001-3695.2022.01.0051

Link prediction algorithm based on lowest-degree preference random walk with restart

Li Qiaoli，Han Hua

（School of Science，Wuhan University of Technology，Wuhan 430070，China）

Abstract：Link prediction is an important issue in the subject of data mining.The similarity algorithm based on random walk often sets the probability of particles transferring to adjacent nodes to be equal，but ignores the effect of node degree on the transition probability.To solve this problem，this paper proposed a link prediction algorithm based on lowest-degree preference random walk with restart.Firstly，the algorithm redefined the transition probability of the walkers by introducing lowest-degree preference function，then applied it to the random walk with restart，and explored the effect of lowest-degree preference strategy on node similarity.The experimental results of nine real networks show that the proposed method has higher prediction accuracy，and gives more network topology information，which proves that the algorithm has certain advantages in the evaluation of node similarity.

Key words：complex networks；link prediction；random walk with restart；lowest-degree preference

0 引言

近年來，網絡科學領域的研究蓬勃發展，越來越多的復雜系統成為復雜網絡學［1］的研究對象。復雜系統中的個體和個體間的聯系可以抽象為復雜網絡來表示。常見的復雜網絡有生物網絡［2］、社會網絡［3］、通信網絡［4］等。鏈路預測作為復雜網絡的重要研究工具，旨在借助網絡中已知數據信息挖掘網絡中未知的連邊關系［5～7］。鏈路預測的研究在眾多領域發揮著重要價值，從理論上來說，可以幫助更好地理解網絡演化機制及網絡動力學行為［8］；從應用上來說，當前社交網絡上的用戶拓展、電信網絡上的詐騙源頭識別、電商網絡上的客戶精準營銷等［9，10］都是鏈路預測在現實網絡中的典型應用。

目前，許多經典的鏈路預測算法被提出。基于相似性的鏈路預測算法應用領域最為廣泛。基于網絡結構相似性的方法可大致分為：a）基于局部信息的方法［5］；b）基于路徑的相似性方法［11］；c）基于隨機游走的方法［12］。基于局部信息的方法主要利用節點的局部信息（如節點的度、共同鄰居數目等）進行鏈路預測。這類方法的計算復雜度較低，但往往以犧牲精度為代價。基于路徑的方法傾向于利用節點之間的路徑信息（如節點之間路徑數量、路徑中間節點的信息等）計算節點相似性。這類方法在涉及到多階路徑信息以及全局路徑信息時，計算復雜度相對較高。基于隨機游走的方法是基于粒子隨機游走過程定義的，即假設粒子從初始節點開始，以一定的概率隨機游走到它的相鄰節點，這個過程一直持續到粒子出現在每個節點上的概率分布達到平穩狀態。這類指標只關注節點鄰居的局部信息，可以在計算復雜度和預測性能之間取得良好的折中，因此還被廣泛應用于推薦系統、信息傳播和社團劃分等問題中［13，14］。

隨機游走的這一優勢使其成為解決鏈路預測問題的主要方法，并取得了許多成果。一個典型的例子是PageRank［15］算法，其中隨機游走方法起著關鍵作用。此外，Li等人［16］認為在現實網絡中，節點不僅趨向于連接度小的節點，而且也趨向于連接中心節點，提出一種最大熵隨機游走的鏈路預測算法，此算法涉及到網絡節點中心性的計算，復雜度相對較高。文獻［17］通過DeepWalk網絡表示學習算法得到節點的向量表示，并通過歐氏距離表征各節點的結構相似度，提出一種網絡表示學習與隨機游走的鏈路預測算法，該算法在預測過程中同時考慮網絡結構信息和節點屬性信息，在處理較大規模的網絡時很吃力。Jin等人［18］提出了一種有監督和擴展的重啟隨機游走方法，其中每個節點對應一個重啟概率，實驗結果表明，所提算法為排名和鏈接預測任務提供了較好性能，但節點重啟概率的設置具有非普適性，限制了該類算法的應用范圍。

上述基于隨機游走的方法大多使用均勻分布來定義粒子的轉移概率，忽略了節點局部區域的細微結構對轉移概率的影響［19～21］。事實上，由網絡的度相關性［22］可以看出，節點之間的連接不是隨機產生的，粒子在游走過程中會受到節點度值的影響。最近，文獻［23］發現，隨機游走者通常頻繁訪問網絡上的高度節點，這種搜索策略更有可能導致較低的搜索效率，并受PageRank算法［24］的啟發，提出一種最低度偏好隨機游走的搜索策略（LPRW），實驗結果表明，與無偏向的隨機游走相比，LPRW方法可以顯著減少搜索時間。呂亞楠等人［25］認為粒子在游走過程中具有一定的度偏向性，提出了BRWR方法，實驗結果同樣表明，粒子偏向游走到高度節點的程度越大，預測的精度越低。

受上述方法和PageRank算法的啟發，本文提出了一種最低度偏置重啟隨機游走鏈路預測算法，該算法是由純隨機游走策略和僅訪問最低度鄰居組成的混合游走策略，并將其應用到鏈路預測中。該方法首先通過引入最低度偏置函數，對游走粒子的轉移概率進行重新定義；然后將最低度隨機游走策略運用到重啟隨機游走中，探究粒子在游走過程中最低度偏向策略對其轉移的作用；最后通過多個真實網絡數據集驗證了所提方法的有效性。

1 相關工作

1.1 問題描述

給定一個無權無向網絡，用一個二元序對G=（V，E）表示，包含|V|=N個節點和|E|=M條邊。對于網絡中所有的節點，所有可能產生連邊的兩點集合用Ω=V×V表示。連通的網絡G可以用鄰接矩陣A=（auv）N×N（u，v∈V）表示，其中A中的元素auv=1，代表節點對（u，v）之間有連邊，否則auv=0。預測算法為網絡中每一對未連接的節點賦予一個相似性分數值Sxy，將所有Sxy降序排列，排在最前面的邊存在的可能性越大。

在實際預測中，一般根據不同評價需求設定相似分數閾值，相似度高于閾值的連邊將選取為推薦結果；或根據相似分數值排序結果，選取前面l條預測連邊作為預測結果。預測連邊可進一步應用于電商推薦系統或在生物實驗中作為指導依據等。

1.2 鏈路預測方法

對于網絡中任意兩個節點u，v∈V，設Γ（u）和Γ（v）分別為節點的鄰居集合，以|Γ（u）|表示集合的勢，Γ（u）∩Γ（v）表示節點的共同鄰居集合，ku代表節點的度。對幾種常用的相似性指標［7］介紹如下：

a）共同鄰居（CN）。通過節點對之間的共鄰節點的個數刻畫節點u和v的相似性，用式（1）表示。

SCNuv=|Γ（u）∩Γ（v）|（1）

其中：Γ（u）為節點u的鄰居集合；||表示集合的勢。

b）PA指標。基于節點間的偏好連接特性提出的指標，認為節點更傾向于與高度節點相連，即

SPAuv=kukv（2）

c）RA指標。是一種基于共享特征的相似性度量方法，其思想是度小的共鄰節點的貢獻大于度大的共鄰節點，采用共鄰節點的度的倒數對相似性進行加權，則節點的相似性定義為

SRAuv=∑ω∈Γ（u）∩Γ（v）1kω（3）

d）HDI指標。該指標稱為高度節點不利指標。

SHDIuv=|Γ（u）∩Γ（v）|max{ku，kv}（4）

e）Katz指標。該指標實際上是一種最短路徑方法，考慮了兩個節點間所有跳的路徑數，并根據路徑長度的不同采取分級懲罰，即

SKatzuv=∑∞l=1βl|path〈l〉u，v|=βAuv+β2（A2）uv+β3（A3）uv+…（5）

其中：β為路徑權重調節參數；|path〈l〉u，v|代表連接節點u和v之間路徑長度為l的路徑數。

f）SimRank指標（SimR）。它假設如果兩個節點所相連的節點相似，則這兩個節點就相似，描述了兩個分別從節點u和v出發的粒子相遇時平均經過的時間，用式（6）表示。

SSimRuv = C∑ω∈Γ（u） ∑ω′∈Γ（v） SSimRωω′kukv（6）

其中：假定Suu=1，C∈［0，1］代表相似性傳遞時的衰減參數。

g）平均通勤時間（ACT）。基于隨機游走定義的相似性指標，表示一個粒子從節點u游走到v所需走的平均步數。節點的相似性表示為

SACTuv=1l+uu+l+vv-2l+uv（7）

其中：l+uv代表網絡的拉普拉斯矩陣中第u行第v列對應的元素值。

h）有重啟的隨機游走指標（RWR）。該指標是由PageRank算法拓展而來的。它是指執行隨機游走的粒子在每走一步都可能以一定概率返回到它的初始位置。設粒子返回概率為1-c，網絡的馬爾可夫轉移矩陣P可表示為puv=auv/ku，其中puv和auv分別表示矩陣P和鄰接矩陣A中的元素。某一個粒子初始時刻在節點u，則t+1時刻到達網絡中各個節點的概率分布向量可表示為

πu（t+1）=c·PTπu（t）+（1-c）eu（8）

其中：eu代表初始狀態。式（8）的穩定解可以表示為πu=（1-c）（I-cPT）-1eu，πu代表穩態解向量，πuv代表πu的第v個元素，則RWR相似性定義為

SRWRuv=πuv+πvu（9）

2 基于最低度偏置重啟隨機游走的相似性方法

隨機游走在復雜網絡領域中起著至關重要的作用，并在各個領域取得了一系列研究成果，包括社區檢測、鏈接預測、重要節點挖掘等，一般分為純隨機游走和有偏隨機游走［26］。純隨機游走是指游走者從任意節點或源節點u開始，只能以等概率隨機游走的方式跳到一個相鄰節點。相比之下，有偏隨機游走是指在未知網絡中強制尋找最近的目標節點進行游走。一個有偏向的隨機游走者從當前節點跳轉到潛在的新節點之一的跳轉概率是不等的，并且游走者傾向于訪問或忽略高拓撲屬性值的節點，包括強度、集聚系數或度等。因此，本文假設粒子在隨機游走的過程中，采用純隨機游走和偏向于訪問最低度鄰居的混合游走策略，并基于混合游走策略得到粒子的跳轉概率矩陣。在此基礎上，讓粒子以重啟隨機游走的方式進行游走，對網絡中未連邊的節點對進行相似性計算，找到每個網絡最佳的最低度偏置調節參數，以達到提高預測精度的目的。

2.1 最低度偏置的重啟隨機游走

定義1 最低度偏置轉移概率。考慮一個在網絡相鄰節點之間跳躍的粒子，由馬爾可夫過程［27］可知，粒子下一個時刻的狀態只與現在的狀態有關。基于最低度偏置隨機游走過程中，在每一個時間步，游走者采取純隨機游走和偏向于訪問最低度鄰居節點的混合游走策略，使用一個可變參數β來調整兩者的融合比率，則當前在節點u的游走者跳轉到v的轉移概率［23］為

wuv=（1-β）w（1）uv+βw（2）uv（10）

其中：β∈（0，1）；w（1）uv=auv/ku表示純隨機游走策略的轉移概率；w（2）uv表示最低度游走策略的概率。w（2）uv的定義為

w（2）uv=1card（Uv）v∈Uv

0vUv（11）

其中：Uv表示節點u的最低度鄰居節點的集合；card（Uv）表示最低度鄰居節點的個數。值得注意的是，當β=0時，最低度偏好隨機游走退化為通用隨機游走，這種情況下，游走者在任何時間停留在節點u上的平穩狀態概率與節點u的度數成正比［27］，因此游走者更有可能在搜索過程中訪問度數高的節點。而在最低度偏好隨機游走的過程中，游走者同時采取βgt;0時的最低度搜索策略，因此避免了這種情況的發生。圖1給出了β=1/3時最低度偏置隨機游走的轉移概率。

基于最低度偏置的重啟隨機游走是指游走粒子從網絡中的某一個節點出發，每游走一步將選擇是以概率1-α跳轉到相鄰節點，還是以概率α返回初始位置。如果粒子選擇以概率1-α跳轉到相鄰節點，此時會以定義1中的最低度偏置轉移概率wuv選擇下一步跳轉到的節點，重復上述過程，直至達到平穩狀態。采用最低度偏置轉移的重啟隨機游走既避免了隨機游走過程中節點等概率轉移和偏向高度節點游走的現象，又解決了有偏置隨機游走在達到平穩狀態之前游走粒子就發生終止的問題。

定義2 最低度偏置重啟隨機游走指標。將定義1中節點的最低度偏置轉移概率用于有重啟隨機游走中進而得到最低度偏置的重啟隨機游走算法（lowest-degree preference random walk with restart，LPRWR）。令πuv（t）表示粒子在時間t=0從節點u出發，在t時刻停留在節點v的概率。這個概率的演化由下面的主方程給出，定義為

πuv（t+1）=（1-α）∑Nl=1alvwlvπul（t）+απuv（0）（12）

其中：α為重啟概率；πuv（0）表示初始狀態向量的第v個元素。

令一步轉移概率的矩陣表示為W，則隨機游走的迭代公式定義為

πu（t+1）=（1-α）WTπu（t）+απu（0）（13）

根據C-K方程，粒子的m步轉移概率可表示為（WT）m，所以粒子隨機游走m步的迭代公式為

πu（t+m）=（1-α）（WT）mπu（t）+απu（0）（14）

當t→∞時，由馬爾可夫鏈的平穩狀態［26］可知，隨機游走的概率分布可能會收斂到一個極限概率分布，也是平穩分布，即滿足Π=（1-α）WTΠ+απu（0），因此式（14）可以改寫為

πu=（1-α）WTπu+απu（0）=α（I-（1-α）WT）-1πu（0）=Rπu（0）（15）

其中：πu為穩態時的概率分布；R為初始狀態πu（0）下的點的相關度。計算穩態解時所有路徑都已考慮。R可寫成無窮級數的形式：

R=α（I-（1-α）WT）-1=α∑∞n=0（1-α）n（WT）n（16）

其中：R還可以看做（WT）n的加權和，其元素（WT）nuv表示經過n次迭代后，隨機游走粒子從節點u停留在v的概率。n表示一個大規模的轉換，隨著n的不斷增加，隨機游走將轉換得更遠［28］。故LPRWR算法可以認為是基于考慮兩節點之間轉移的所有路徑來對相似性進行優化。由此定義LPRWR相似度為

SLPRWRuv=πuv+πvu（17）

其中：元素πuv代表由節點u出發的粒子最終到達節點v的概率。

綜上所述，該算法的流程如算法1所示。

算法1 LPRWR算法

輸入：網絡鄰接矩陣A=（auv）N×N（u，v∈V），最低度偏置調節參數β，重啟概率α。

輸出：網絡的節點相似度得分矩陣S。

a）初始化最低度偏向轉移矩陣W←ON×N，節點相似度得分矩陣S←IN×N

b） for i=1 to N，j=1 to N

c）" 根據式wuv=（1-β）w（1）uv+βw（2）uv計算節點間的最低度偏置轉移概率；更新最低度偏置轉移矩陣W

d）" for i=1 to N do

e）""" πu=α（I-（1-α）WT）-1πu（0） /*計算節點u和網絡中其他各節點的相似度得分值 */

f）" end while

g） end for

h）return S

2.2 算法收斂性

LPRWR算法中粒子隨機游走過程的收斂性是保證算法能應用的必要條件，下文給出算法收斂性的嚴格證明。

定理1 LPRWR算法是收斂的。

證明 a）由于最低度偏置轉移矩陣W中的元素wuv滿足wuv≥0，∑v∈Vwuv=1，u，v∈V，所以矩陣W是隨機矩陣。由隨機矩陣性質可得出，矩陣W是不可約的。

b）隨機游走過程是一個馬爾可夫鏈，對于其中的任一狀態，當隨機游走經過這一狀態后，由于存在重啟概率，再次遍歷這一狀態所需游走的步數是不確定的，所以整個游走過程是非周期性的。

由此得出LPRWR算法采用的隨機游走過程是各態歷經的［29］，故LPRWR算法是收斂的。

2.3 復雜度分析

定理2 LPRWR算法的時間復雜度是O（N3）。

證明 由于在t→∞，LPRWR算法的概率分布會收斂到一個平穩分布，根據穩態解πu=α（I-（1-α）WT）-1πu（0），故算法的關鍵是計算矩陣（I-（1-α）WT）-1的逆，而求一個N×N矩陣的逆或偽逆的復雜度是O（N3），故LPRWR算法的時間復雜度是O（N3）。

3 實驗條件介紹

實驗中，將網絡連邊E劃分為訓練集ET和測試集EP，其中E=ET∪EP，且ET∩EP=。訓練集被認為已知信息用于計算未連邊節點對的得分，有效的算法應當賦予測試集更高的分值，而對不存在的連邊賦予較低的分值。

文中采用十折交叉檢驗來測試所提算法的性能，并且為了方便進行數據處理，將所有數據以CSV格式保存在MySQL數據庫中。使用Rapidminer數據挖掘工具，按比例EP：ET=1：9隨機選取訓練集和測試集。實驗中，每個AUC和precision均為不少于100次獨立實驗結果的均值。

3.1 衡量指標

鏈路預測算法的主流衡量指標包括AUC（area under the curve）［30］和精確度（precision）［31］。前者側重于從整體上評價算法對未知對象的區分度；后者側重于精準預測，關注的是預測前列結果命中的比率。

AUC是指在衡量算法性能時，從測試集EP中隨機選擇一條邊的分數值大于一條不存在邊的分數值的概率。實驗時，若測試集中邊的預測分數值大于不存在邊的分數值加1，此種情況次數記為n′次，兩者相等時則加0.5，情況次數記為n″次，則AUC指標可以表示為

AUC=n′+0.5n″n（18）

其中：n為獨立比較的次數。顯然，隨機預測下AUC≈0.5。此外，在計算AUC時還需考慮到比較次數n的取值問題。Lyu等人［7］證明了無論測試集比例取何值，n最多取672 400次時，能夠以90%的置信度確保AUC的絕對計算誤差不超過1‰。因此，在本文實驗中n均取672 400次。

Precision指標關注的是排在前L個預測邊中預測準確的比率，表示為

precision=lL（19）

其中：l代表預測分數值排在前L個的連邊中出現在EP中的個數。

3.2 數據集

實驗選取九個不同規模的真實網絡數據集，這些數據集均來源于網絡公開數據庫［32］，包括dolphins、neural、polbook、me-tabolic、netscience（NS）、football、circuit、Facebook、Hamster。上述網絡數據集的相關統計特性如表1所示。其中，N與M分別為節點數與邊數，〈k〉為網絡平均度，〈d〉為平均最短路徑，r為同配性系數，H為度異質性，C為集聚系數。

4 實驗結果與分析

為了評估LPRW方法的性能，本文首先計算節點間的相似度得分，然后使用AUC和precision兩個衡量指標來量化本文方法進行鏈接預測的準確性。在實驗中，按照基于隨機游走方法中的典型做法，設置重啟系數α=0.15［12，15，23］。由于篇幅所限，下文只給出AUC指標的運行結果。

4.1 相關參數對AUC結果的影響

在式（10）中，β主要用來調節最低度偏置游走的比例，其中β∈［0，1）。本文研究了參數β對預測結果的影響，實驗結果如圖2所示。結果表明，相比β=0（無偏向隨機游走），指標的預測精度都得到一定的提高，且在一定的參數范圍內均可以取得最佳的預測精度，這說明最低度偏置游走對相似性的影響是不可或缺的。從圖2中的每個子圖可以觀察到，不同網絡的AUC曲線到達峰值后會呈現不同程度的下降，其中大部分網絡，如dolphins、neural、polbook等網絡的下降趨勢較快。這在一定程度上表明最低度偏置程度較小時，預測的準確度較高。從圖中可以看出，在dolphins、metabolic、NS網絡中，β在0.05時預測效果最好；在neural、Hamster網絡中，β在0.1時預測效果更好；對于polbook、Facebook網絡，最優的β為0.15；對于football網絡，最優的β為0.25；circuit網絡中，最優的β主要分布在β=0.45和β=0.1附近。因此，不同的網絡取得最優AUC值時對應的參數值有一定的不同，然而最優的參數值取得較小時，如在0～0.2時，可以取得較好的預測效果。此外，AUC值取得最優時β≠0也相當于粒子在游走時偏向于度小的節點，這與RA指標的思想一致，即低度值的共鄰節點的作用大于高度值的共鄰節點的作用。綜上分析，在實際應用中，可以選取較小的β值進行預測。

4.2 可行性分析

為了進一步驗證最低度偏置隨機游走的可行性及LPRWR算法的有效性，將所提方法與八個主流指標（包括四個局部指標和四個全局指標）進行預測性能的對比分析，各個指標的AUC值如表2所示。可以看出，LPRWR算法在八個網絡中取得了最高AUC值，僅在Facebook網絡中略低于RWR指標。另外，雖然其他幾種方法在某些網絡上的得分可能接近本文方法，但它們在其他一些網絡上的表現存在明顯差異。這一事實表明了本文方法預測結果較為穩定，在廣泛的網絡上具有一定的優勢，而其他基準指標可能僅在某些特定的網絡上表現良好。

此外，CN、PA、RA、HDI這些局部指標中，RA指標對度大的節點進行懲罰，在局部指標中預測效果相對較好。在Katz、SimR、ACT、RWR這些全局指標中，其中Katz指標是考慮節點之間的所有路徑，SimR、ACT、RWR都是基于隨機游走過程定義的指標，且RWR在這幾個指標中整體表現相對較好。若以RWR指標為基準，LPRWR算法預測準確度平均提升了2.14%，且在football網絡中AUC結果提升了4.48%。由定理2可知，LPRWR算法的時間復雜度和RWR算法相同，均為O（N3），在兩者時間復雜度相同的情況下，LPRWR方法的預測準確度比RWR方法更好，進一步表明了最低度偏置重啟隨機游走對鏈路預測是有效和可行的。

5 結束語

準確預測復雜網絡中節點間的相似性對于加快積極信息在網絡中傳播、預防電信詐騙、促進電商網絡的發展具有現實意義。對于當前基于隨機游走過程的鏈接預測方法，大多認為粒子轉移到其不同鄰居的概率相等，然而，該方法在分析中忽略了網絡的詳細結構信息。本文通過考慮最低度偏置游走對粒子轉移概率的影響，定義了最低度偏置函數，提出一種混合游走策略，并將其應用到重啟隨機游走中，進而量化節點間的相似性。以本文方法為基礎，在真實網絡上經過大量實驗，并對各指標的預測效果進行對比分析，證實了本文方法的有效性和可行性，表明算法在節點相似性的度量上具有一定的優勢。

本文算法僅適用于無權無向的單層網絡，具有一定的局限性，如何設計適用于加權有向的多層網絡的鏈路預測算法，是接下來要研究的問題。在下一步的研究中，可以嘗試挖掘更多影響隨機游走過程的結構信息，將此應用在多層網絡上，進一步提高鏈路預測的準確度。

參考文獻：

［1］Tan Yangxin，Wu Junlin，Zhong Qing.Complex network［J］.Journal of Physics：Conference Series，2020，1601：032011.

［2］Cannistra C V，Alanislobato G，Ravasi T.From link prediction in brain connectomes and protein interactomes to the local community paradigm in complex networks［J］.Scientific Reports，2013，3（4）：1-13.

［3］Fan Tongrang，Xiong Shixun，Zhao Wenbin，et al.Information spread link prediction through multi-layer of social network based on trusted central nodes［J］.Peer-to-Peer Networking and Applications，2019，12（5）：1028-1040.

［4］Dzaferagic M，Kaminski N，Mcbride N，et al.A functional complexity framework for the analysis of telecommunication networks［J］.Journal of Complex Networks，2018，6（6）：971-988.

［5］Zhou Tao，Lyu Linyuan，Zhang Yicheng.Predicting missing links via local information［J］.European Physical Journal B，2009，71（4）：623-630.

［6］Gul H，Amin A，Adnan A，et al.A systematic analysis of link prediction in complex network［J］.IEEE Access，2021，9：20531-20541.

［7］Lyu Linyuan，Zhou Tao.Link prediction in complex networks：a survey［J］.Physica A：Statistical Mechanics and Its Applications，2011，390（6）：1150-1170.

［8］譚索怡，祁明澤，吳俊，等.復雜網絡鏈路可預測性：基于特征譜視角［J］.物理學報，2020，69（8）：188-197.（Tan Suoyi，Qi Mingze，Wu Jun，et al.Link predictability of complex network from spectrum perspective［J］.Acta Physica Sinica，2020，69（8）：188-197.）

［9］Assouli N，Benahmed K，Gasbaoui B.How to predict crime informa-tics-inspired approach from link prediction［J］.Physica A：Statistical Mechanics and Its Applications，2021（8）：125-143.

［10］Ai Jun，Liu Yayun，Su Zhan，et al.Link prediction in recommender systems based on multi-factor network modeling and community detection［J］.Europhysics Letters，2019，126（3）：38003.

［11］Lyu Linyuan，Jin Cihuang，Zhou Tao.Similarity index based on local paths for link prediction of complex networks［J］.Physical Review E，2009，80（4）：046122.

［12］Tong Hanghang，Faloutsos C，Pan Jiayu，et al.Fast random walk with restart and its applications［C］//Proc of the 6th International Confe-rence on Data Mining.Piscataway，NJ：IEEE Press，2006：613-622.

［13］Fu Xianghua，Wang Chao，Wang Zhiqiang.Scalable community discovery based on threshold random walk［J］.Journal of Computational Information Systems，2012，8（21）：8953-8960.

［14］趙海燕，張健，曹健.基于主題分組與隨機游走的App推薦算法［J］.計算機應用研究，2018，35（8）：2277-2280.（Zhao Haiyan，Zhang Jian，Cao Jian.Personalized App recommendation algorithm based on topic grouping and random walk［J］.Application Research of Computers，2018，35（8）：2277-2280.）

［15］Nassar H，Benson A R，Gleich D F.Neighborhood and PageRank methods for pairwise link prediction［J］.Social Network Analysis and Mining，2020，10（1）：211-230.

［16］Li Ronghua，Yu J，Liu Jianquan.Link prediction：the power of maximal entropy random walk［C］//Proc of the 20th ACM Conference on Information and Knowledge Management.New York：ACM Press，2011：24-28.

［17］劉思，劉海，陳啟買，等.基于網絡表示學習與隨機游走的鏈路預測算法［J］.計算機應用，2017，37（8）：2234-2239.（Liu Si，Liu Hai，Chen Qimai，et al.Link prediction algorithm based on network representation learning and random walk［J］.Journal of Computer Applications，2017，37（8）：2234-2239.）

［18］Jin W J，Jung J H，Kang U，et al.Supervised and extended restart in random walks for ranking and link prediction in networks［J］.PLoS One，2019，14（3）：0213857.

［19］Zhou Yinzuo，Wu Chencheng，Tan Lulu.Biased random walk with restart for link prediction with graph embedding method［J］.Physica A：Statistical Mechanics and Its Applications，2021（6）：125783.

［20］Berahmand K，Nasiri E，Forouzandeh S，et al.A preference random walk algorithm for link prediction through mutual influence nodes in complex networks［EB/OL］.（2021-05-20）.https：//arxiv.org/abs/2105.09494.

［21］Elahe N，Kamal B，Li Yuefeng.A new link prediction in multiplex networks using topologically biased random walks［J］.Chaos，Solitons amp; Fractals，2021，151：111230.

［22］Vázquez A，Moreno Y.Resilience to damage of graphs with degree correlations［J］.Physical Review E Statistical Nonlinear amp; Soft Matter Physics，2003，67（1）：015101.

［23］Wang Yan，Cao Xinxin，Weng Tongfeng，et al.Lowest-degree prefe-rence random walks on complex networks［J］.Physica A：Statistical Mechanics and Its Applications，2021，577：126075.

［24］Langville A N，Meyer C D.Google’s PageRank and beyond：the science of search engine rankings［J］.The Mathematical Intelligencer，2011，30（1）：68-69.

［25］呂亞楠，韓華，賈承豐，等.基于有偏向的重啟隨機游走鏈路預測算法［J］.復雜系統與復雜性科學，2018，15（4）：17-24.（Lyu Yanan，Han Hua，Jia Chengfeng，et al.Link prediction algorithm based on biased random walk with restart［J］.Complex Systems and Complexity Science，2018，15（4）：17-24.）

［26］Fronczak A，Fronczak P.Biased random walks in complex networks：the role of local navigation rules［J］.Physical Review E，2009，80（1）：016107.

［27］徐全智.隨機過程及應用［M］.北京：高等教育出版社，2013：113-219.（Xu Quanzhi.Stochastic processes with its applications［M］.Beijing：Higher Education Press，2013：113-219.）

［28］Kim T H，Lee K M，Lee S U.Generative image segmentation using random walks with restart［J］.Lecture Notes in Computer Science，2008，5304（1）：264-275.

［29］鄭偉，王朝坤，劉璋，等.一種基于隨機游走模型的多標簽分類算法［J］.計算機學報，2010，33（8）：1418-1426.（Zheng Wei，Wang Chaokun，Liu Zhang，et al.A multi-label classification algorithm based on random walk model［J］.Chinese Journal of Computers，2010，33（8）：1418-1426.）

［30］Hanley J A，McNeil B J.The meaning and use of the area under a receiver operating characteristic（ROC） curve［J］.Radiology，1982，143（1）：29-36.

［31］Lawera M.Predictive inference：an introduction［J］.Technometrics，1995，37（1）：121.

［32］Kunejis J.Konect：the Koblenz network collection［C］//Proc of International Conference on World Wide Web Companion.New York：ACM Press，2013：1343-1350.