一種基于給定目標節點的個性化PageRank算法設計

易黎

摘? ?要：以往衡量圖網絡節點重要性時，多基于給定源節點，計算該節點到其余目標節點的個性化PageRank值并推出重要目標節點，運算效率低且存儲量大。基于此，提出了一種基于給定目標節點的個性化PageRank算法（TPPR），該算法結合本地更新與優先隊列算法，通過計算從所有源節點到給定目標節點的個性化PageRank值來推出重要源節點，相較于傳統算法運算精度更高，運行時間大幅減少。

關鍵詞：個性化PageRank;目標節點;本地更新算法;優先隊列算法

中圖分類號：TP39? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A

Design of A Personalized PageRant Algorithm Based on A Given Target Node

YI Li？覮

（Nanjing Fiberhome Xingkong Communication Development Co.，Ltd.，Nanjing，Jiangsu 210019，China）

Abstract：When the importance of the graph network node was measured，the personalized PageRank value of the node to the other target nodes was calculated based on the given source node，and the important target node was launched，which has low computational efficiency and large storage capacity. Based on this，this paper proposes a personalized PageRank algorithm （TPPR） based on a given target node. This algorithm combines the local update and priority queue algorithm to derive important information by calculating the personalized PageRank value from all source nodes to a given target node. The source node is more accurate than the traditional algorithm，and the running time is greatly reduced.

Key words：personalized PageRank;target node;local update algorithm;priority queue algorithm

PageRank是衡量圖網絡節點重要性的指標之一，個性化PageRank算法（以下簡稱PPR）作為普通PageRank算法的擴展，通常直接用于依據用戶偏好對其進行個性化的結果推薦，并及時反饋與用戶搜索密切相關的結果信息[1]。PPR算法自Page等[2]提出以來，已被廣泛應用于個性化搜索[3]、用戶影響力排名[4]、網址鏈接預測[5]等各種數據集可表示為圖結構的搜索場景中。

從相關研究來看，在計算PPR值時多采用蒙特卡羅或冪迭代算法。例如，A.Benczur和K.Csalogany[6]提出采用蒙特卡羅法計算從單個源節點到目標節點的PPR值，但由于存在大量的目標節點，計算成本較高，并且對于單個目標節點 而言，這種方法都需要計算N次，大大降低了計算效率。Fogaras[7]等研究發現采用冪迭代算法計算PPR值時，僅針對n個節點，至少也需要 的存儲空間，并且在實際應用中，用戶的偏好可能為圖中任意節點的組合，因此圖中至少需要包括 個任意節點子集。以往的PPR算法都是研究基于給定單個源節點來確定鏈接圖中節點的重要性或權威值，反映與用戶偏好相關的查詢結果，缺乏對于給定目標節點，計算出所有源節點到該目標節點的個性化PPR值的相關研究工作，也無法基于某個給定目標節點逆向反推對其關注或感興趣的用戶。另外，傳統算法需要在查詢期間依據用戶的偏好信息進行實時運算，在占用大量存儲空間的同時，運算效率也嚴重降低。

據此，提出了基于給定目標節點v的PPR算法（以下簡稱TPPR）：給定有向或無向圖G = （V，E）中的目標節點v，計算從所有源節點u∈V到目標節點v的PPR值π（u，v），如果邊代表興趣或支持，這個算法即表示為尋找所有對目標節點v感興趣或支持的源節點u。這個算法也可被廣泛應用于實際案例，例如重要客戶挖掘、重點人員推薦等。此外，本算法模型也可在綜合評價和信任系統中應用。

1? ?傳統PPR算法

個性化PageRank算法繼承了經典PageRank算法的思想，利用數據模型（圖）鏈接結構來遞歸計算各節點權重，模擬用戶通過點擊鏈接隨機訪問圖中節點的行為，即基于隨機游走模型計算穩定狀態下各節點得到的隨機訪問概率[8]。給定一個有向或無向圖G = （V，E），在圖G中，V表示所有網絡節點的集合，E表示網絡節點間的所有邊，假設G為非加權圖，定義節點u的入度為IN（u） = {w：（w，u）∈E}，出度為OUT（u） = {w：（u，w）∈E}。對于u，v∈V傳統PPR算法的目標是計算從給定源節點到其余所有目標節點的PPR值。用戶從源節點u開始隨機游走，以概率α隨機選擇下一個訪問節點，或者跳轉到任意一個節點以（1-α）的概率開始新一輪的隨機游走。經過多輪游走之后，每個節點被訪問到的概率也會收斂趨于穩定，所以從源節點u到目標節點v的PPR值可以解釋為在隨機游走過程中停止在節點v的穩定概率，即π（u，v） = P[XL = v]。在穩定狀態下，用戶所偏好的那些節點和相關的節點總能夠獲得較高的訪問概率。傳統個性化PageRank的隨機游走模型可形式化地表示為：

r = （1 - α）Mr + av? ? ? ? （1）

其中，M為圖G對應的鄰接矩陣，v為用戶的偏好向量，v = 1，反映圖中每個節點針對給定偏好向量的重要性，r為M的特征向量。

2? ?TPPR算法設計

TPPR算法不同于傳統PPR算法，它是為了計算所有源節點u到給定目標節點v的PPR值。給定目標節點v，該算法在執行過程中使用本地更新算法與優先隊列算法進行改進，使得其在不需要訪問所有節點的情況下，計算出其所有源節點u的PPR值π（u，v）的近似估計值，并且滿足給定的誤差閾值范圍。TPPR算法設計流程圖如圖1所示。

2.1? ?本地更新算法

根據PPR算法的隨機游走模型可以推出本地更新算法：假設源節點具有一定的“概率質量”，然后從該源節點開始“概率質量”推送，并迭代進行推送過程，直到滿足設定的誤差閾值時，停止概率推送過程，最終得到每個節點的PPR值。在本地更新過程中，每個節點需要維持兩個屬性：PPR估計量 s（u）和殘余概率p（u），其中s（u）表示該節點收到并且已經推送出去的“概率質量”，p（u）表示該節點上收到但還沒有被推送出去的“概率質量”。本地更新算法只作用于目標節點的相關鄰近區域，而無需訪問整個圖網絡的所有節點。TPPR算法主要采用了逆向推送的本地更新算法，即從給定的目標節點 v出發，對π（u，v）進行逆向推送操作，最終計算出每個源節點u到給定目標節點v的PPR估計值。從u開始的隨機游走是通過立即傳送或通過跳轉到一個隨機鄰節點開始的，所以從u到v的預期概率為非直接傳送次數的概率，即從u的外鄰居節點u∈OUT（u）到達v的平均期望次數的概率。該算法思想主要基于PPR算法的遞推公式：

π（u，v） = （1 - α）■■π（w，v）+

α，u = v0，u≠v? ? ? ? （2）

其中，源節點為u，目標節點為v，w為u的外鄰居節點（u指向w），由于α表示在每個節點終止游走的概率，當u = v時到達給定目標節點，所以在公式中加入α。TPPR算法可以被視為從給定的目標節點v開始的“概率質量”推送算法，算法在逆向推送過程中每個節點維持PPR估計量s（w，v）和殘余概率p（w，v）兩個變量，而每一步逆向推送回溯過程，可以理解為將該節點p（w，v）的α倍殘余概率推送增加至該節點的s（w，v），剩下的1-α倍殘余概率平均的逆向回溯給節點w的每個入鏈節點 u∈IN（w）的p（u，v）。

2.2? ?優先隊列算法設計

在TPPR算法中加入優先隊列算法，隨著節點變化不斷更新節點的概率值時，改進后的算法只需要推送自上次w概率推送以來改變的最大部分，這樣可以大大節省算法的運行時間和存儲空間。TPPR算法主要基于給定目標節點v進行概率逆向推送操作，最終對每個源節點u計算一個PPR估計量s（u），來從低到高估計每個源節點u到給定目標節點v的PPR值π（u，v），并且隨著網絡的動態變化不斷更新。因此，算法的基礎更新步驟為節點w的當前PPR估計量s（w）與其最后一次概率推送之間的差異用殘余概率p（w）表示，將p（w）排序形成優先級隊列Q，以至于可以輕易的找出p（w）中值最大的節點。優先隊列算法的主要思想為只要存在某個節點的優先級高于設定閾值α∈ε，我們就移除具有最大優先級的節點，并將其概率推送回給它的內鄰居節點，隨后迭代執行此逆向推送過程，直到滿足誤差閾值條件時，結束迭代過程并輸出結果。只要某個節點的優先級高于最小閾值，彈出優先級最高的節點，并將其概率進行推送。完整的優先級隊列算法見算法1所示：

算法1：基于給定目標節點的個性化PageRank算法（TPPR算法）

輸入：圖G = （V，E），推送概率α，目標節點v，允許誤差值ε

初始化：s[v] = p[v] = α

q = V中按殘余概率p排序形成的最大優先級隊列

While q.max priority（）>α∈ε，do

w = q.popMaxElement（）

for w的內鄰居節點u（節點u指向節點w）：

Δs = （1 - α）■

若u不在s中：

s[u] = p[u] = 0

結束

s[u] = p[u] + Δs

q.increas Pr iority（u，p[u] + Δs）

結束for循環

p[w] = 0

結束While循環

輸出：概率向量s（π（u，v））（的估計近似值）：對于所有源節點u，節點集合V→[0，1]，此時π（u，v） - s[u] < ε.

圖2描述了優先隊列算法在僅有四個節點包括給定目標節點v的圖中的六次迭代過程。對于源節點u，s是π（u，v）的當前估計值，優先級p是殘余概率。優先隊列算法每次從優先級隊列中取出 p（w）最大值進行逆向推送，直至所有節點都滿足π（u，v） - s[u] < ε，即最終的PPR估計值與PPR實際值之間的偏差不超過閾值，其中填充灰色的節點表示下一步將要執行優先級傳送操作的節點。

3? ?算法效果評估

3.1? ?誤差分析

TPPR算法的一個核心問題是如何選擇合適的優先級閾值來確定是否移除隊列中的節點。首先考慮閾值ε，但這個閾值并不是足夠小來確保所有的誤差都小于ε。最終選擇αε作為合適的閾值，當所有節點的優先級均小于αε時，優先隊列算法運行完成，此時對于所有源節點u∈V，所輸出的PPR估計值向量s滿足π（u，v） - s[u] < ε。

3.2? ?平均運行時間

在最糟糕的情況下，目標節點v具有比其余所有節點的高PPR值，這需要對整個圖進行分析。因此，給定運行時間的有效約束，分別對一般情況和糟糕情況進行分析。首先分析在一般情況下優先級隊列算法的平均運行時間，此時隨機均勻選擇目標節點v。給定一個任意圖G，允許誤差值為ε，推送概率α。令n為圖G中的節點數量，m為邊的數量。v為從圖G所有節點集合V中隨機均勻選擇的目標節點，故優先級隊列算法將預期運行O（■（■ + log（n）））次。

蒙特卡羅方法在失敗概率為δ的情況下，使用Chernoff邊界計算π（u，v）近似值的平均時間復雜度為Θ■log■。如果圖足夠稀疏或足夠小，算法的平均時間復雜度最多為O■■。因此，在計算所有節點的PPR估計近似值時，在每個節點運行優先隊列算法比運行蒙特卡羅方法的效率要高很多。

4? ?實驗案例

采用微博的社交網絡圖做實驗，實驗數據共包含75879個節點，508837條邊，設置節點傳送概率 α∈{0.1，0.2}，附加誤差ε∈{10-4，10-5，10-6}，每次實驗隨機均勻選擇100個目標節點v來運行優先隊列算法。設定節點傳送概率α = 0.1，誤差閾值ε = 10-6。由于具有高全局PageRank值的節點經常相對于其他節點來說更可能成為目標節點，因此按全局PageRank概率選擇100個目標節點 ，運行優先隊列算法，在算法收斂后計算經驗誤差maxu∈Vπ（u，v） - s[u]。圖3中為算法收斂之后經驗誤差占目標誤差比例的分布直方圖，從上圖可以看出，最大的經驗誤差約為0.90ε，這與設定目標誤差ε的界限非常接近，大部分經驗誤差通常超過設定目標誤差ε界限的50%。

經驗誤差占目標誤差的比例

圖3? ?優先隊列算法的經驗誤差

迭代次數

圖4? ?優先隊列算法的迭代次數

迭代次數和/DV（αε）

圖5? ?迭代次數和與DV（αε）的比率分布

當設定傳送概率α = 0.1，誤差閾值ε = 10-5，隨機均勻選擇100個目標節點v，運行優先隊列算法。圖4為優先隊列算法迭代次數，即內部循環中跳轉節點優先級的次數。其中，x軸為指數刻度，垂直線為設置的平均運行次數界限。從圖中來看，在滿足誤差閾值時，大部分節點的迭代次數都小于約束界限。

參數化分析顯示，算法運行時間復雜度最多為O（■）log（■））。為了證明準確性，將迭代次數和Dv（αε）進行比較。當α = 0.1，ε = 10-5，根據公式推算迭代次數和與Dv（αε）的證明比率約為200，但在實驗中平均比率小于4。比率的分布如圖5所示。對于大多數節點，盡管在圖4中迭代次數的絕對數量以指數刻度變化，但從圖5來看算法迭代次數和與Dv（αε）的比率在2范圍內。

表1? ?優先隊列與冪迭代算法運行時間比較

為了體現優先隊列算法的效率，使用冪迭代算法在相同設置下的運行結果作為基準。從表1來看，在設置α = 0.1，隨機均勻選擇100個目標節點條件下，優先隊列算法的運行效率遠高于冪迭代算法。

5? ?結 論

為了解決傳統PPR算法在衡量圖網絡節點重要性時，只考慮基于給定源節點推薦重要目標節點、運算效率低等問題，提出了一種基于給定目標節點的個性化PageRank算法（TPPR）。TPPR算法在傳統PPR算法的基礎上加入本地更新算法和優先隊列算法進行改進，改進后的算法一方面繼承了個性化PageRank算法的思想，在節點關聯搜索中考慮了用戶在查詢、收藏頁面等個性化信息表達中的行為偏好影響，另一方面又實現了基于給定目標節點搜索重要源節點的算法方案設計。TPPR算法具備廣泛的實用性，既可用于實際圖結構搜索場景中發現對目標感興趣甚至支持的用戶，也相較于以往蒙特卡羅、冪迭代算法而言，運算精度與運算效率都具有大幅度提升。

參考文獻

[1]? ? LIBEN-NOWELL D，KLEINBERG J. The link-prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology，2007，58（7）：1019—1031.

[2]? ? PAGE L，BRIN S，MOTWANI R，et al. The PageRank citation ranking：bringing order to the web[R]. State of California，Stanford University，1999.

[3]? ? 孟瑞玲. 個性化PageRank算法在圖書館智能搜索引擎中的實現[J]. 現代情報，2010，30（07）：93—96.

[4]? ? 徐文濤. 社交網絡中用戶影響力及個性化排名相關技術研究[D]. 合肥：安徽大學，2017.

[5]? ? 朱凡微，吳明暉，應晶. 高效個性化PageRank算法綜述[J].中國科技論文，2012，7（01）：7—13.

[6]? ? BENCZUR A，CSALOGANY K，ARLOS T，et al. Spamrank-fully automatic link spam detection work in progress[C]. In Proceedings of the First International Workshop on Adversarial Information Retrieval on the Web，2005.

[7]? ?FOGARAS D，R？魣CZ B. Towards scaling fully personalized pagerank：Algorithms，lower bounds，and experiments [J]. Internet Mathematics，2005，2（3）：333—358.

[8]? ? 劉記云. 基于MapReduce的個性化PageRank算法研究[D].哈爾濱：哈爾濱工程大學，2013.