歷史圖上的PageRank算法設計與實現

摘要： 近些年來,對於靜態圖的研究越來越全面、深入，已經形成了完善的理論體系。但是，如果考慮到生活中的一些應用問題，如社交網絡中不斷變化的關係等，使用靜態圖表示此類時刻都在變化的關係似乎顯得有些乏力。而歷史圖可以用以表示動態變化。PageRank算法是用于衡量網頁重要程度的算法，而網絡中不斷有網站新建或刪除，這樣的網絡用歷史圖來表示顯得相當貼切，因此我們考慮在歷史圖上利用CSR(Compressed Sparse Row)結構實現PageRank,使得程序能夠給出在幾個目標時間的各網站的評分，進而能夠提供網站評分的變化情況，給出網站影響力趨勢的預測。在Wekipedia提供的網頁互相連接的Hyperlink networks數據集上將其性能與在鍊表上實現PageRank算法作比較，結果顯示其性能大大優於使用鍊表結構，並且隨著數據規模和目標時間規模的增大，其優勢將會越來越明顯。

關鍵詞： PageRank；CSR(Compressed Sparse Row)結構；歷史圖 

1 引言

1.1 課題背景及研究的目的和意義

在這個時代，大數據是信息化發展到一定階段的產物。大數據不僅僅是數量上的大，在其背後隱藏著各個行業、領域錯綜複雜的關係，而這樣的關係往往蘊含著商業價值與科研價值[1]。「圖」是用來表示關係的一種很好的數據結構，它能夠有效且直觀地描述現實生活中各個事物之間的複雜關係以及各個事物本身所具有的一些性質。在現實生活中所存在的對象可以抽象為圖中的頂點，對象和對象之間的某種或者多種關係可以抽象為頂點與頂點之間的單邊或者多邊關係。例如在社交網絡中，用戶與用戶之間的好友關係等。

對於傳統的圖數據來說，它是靜態的，只能表示一個單一時刻的數據。但是在真實世界中，對於每時每刻都在變化的生命體及其組成來說，靜態圖註定無法表示，Przytycka等人認為在未來的工作中從靜態網絡分析提升到動態網絡分析是必不可少的[2]。同理，面對隨時隨地都在變化的網際網路，每時每刻都有頁面的不斷加入和退出。因此我們需要一個更好的結構來表示該類情況。

1.2 國內外在該研究方向的現狀

傳統的PageRank 推薦算法需要全圖迭代到收斂，因此其時間複雜度非常高，嚴重影響了推薦的效率。曹軍深入分析了PageRank的關鍵技術，並對其存在的商業問題進行了思考[3]。為了減少算法的耗時，常家偉等人[4]在PageRank算法的迭代過程中加入可控制迭代次數的參數b和一個用於修剪結果向量的閾值α。然後針對主題相關性的問題中，使用了歸一化的鄰接矩陣的特徵值與特徵向量來評估節點之間的距離，從而產生最終的推薦列表，而列表中的對象主題相關性則會較高些。對於APP搜索來說，雖然按照關鍵詞搜索出來的應用主題相關性比較高，但是質量參差不齊。因此李春生等人[5]在PageRank算法基礎上引入保持時間因子，使用戶保存時間越短的 APP 逐漸懸沉下去，保存時間長的 APP 能快速浮上來。在Francisco Pedroche等人[6]的研究中，PageRank被認為是馬爾科夫鏈（1階）的靜止狀態，它利用先前狀態的知識來轉換系統的狀態。他們利用「個性化向量」來讓PageRank可以偏向某個節點。而且他們將PageRank和多路復用網絡結合起來，定義了Multiplex PageRank。

對於傳統的靜態圖完善的理論體系結構來說，歷史圖仍在發展中。如果時間回退3-5年，鮮有相關論文產出。近幾年，越來越多的關注被集中在歷史圖相關方面的研究。

在文獻[7]中，歷史圖被描述為一系列的靜態圖序列。由於面向大規模動態圖的可達查詢研究較少，且尚存在所以壓縮困難以及圖結構待優化等問題，丁琳琳等人[8]提出了一種支持大規模數據的基於改進哈夫曼編碼的可達查詢處理方法。該方法首先對預處理圖進行結構上的兩次壓縮，得到雙壓縮圖；其次，基於雙壓縮圖提出一種前綴label索引，該索引能夠有效表達節點間的可達關係。最後，提出雙壓縮圖的演進和可達查詢處理及優化算法。面向結構變化的動態圖匹配問題最早在 2009年由 Wang 和 Chen 提出 , 他們構建鄰節點樹(NNT)[9]並依此對匹配候選集進行過濾,從而有效減少假陽性匹配結果的產生。 這之後的代表性算法包括IncIsoMatch [10]、SJ-Tree[11]等,它們對子圖匹配的執行效率進一步提升提供了不同看法。文獻[12]指出：給定一個網絡圖，計算給定兩點之間距離是一個重要的問題。文獻介紹了最先進的基於空間相干和基於頂點重要性的方法的綜合比較。並使用具有多達兩千萬個頂點的各種真實道路網絡，分別計算了兩種技術的預處理時間，空間消耗和查詢效率，以此來評估兩種技術。

2 PageRank算法

這個簡化的排名函數有個小問題。考慮存在只有鏈入而無鏈出的節點，那麼，在迭代時，這個循環會不斷積累權重，而從來不發出權重。對於這樣沒有出度的網頁，設置其對所有網頁都有出度。

PageRank迭代計算過程可以表示為算法一

算法1 PageRank算法

輸入： Graph G

輸出： PageRank Value

1.Initialize:float array PR[]

2.for i=1 up to max_interation do

3. change = 0

4. for node ∈ G.nodes() do

5. PR(node) = ∑_(v∈G.nodes)?(PR(v))/Nv

6. PR(node) += (1-c)/N

7. change += |〖PR〗_old-〖PR〗_new| /*累計該輪與上輪差值*/

8. end for

9. if change < threshold then

10. break

11. end if

12. end for

然而PageRank卻忽視了主題性和相關性。例如「蘋果」一次對於不同主題就蘊含不同的意思。因此就產生了個性化的PageRank[14]與主題敏感的PageRank[15]來彌補這些問題。如果將PageRank和IF-TDF結合起來[16]能夠基於文檔內容與用戶查詢的相似性對文檔進行排名。同時，PageRank也可以應用到電力系統[17]和軍事通信系統中 [18] 。

3 歷史圖

歷史圖數據，又可以稱為臨時圖數據(temporal graph)、動態圖數據(dynamic graph)。其頂點可表示某個實體對象，例如網頁、通信雙方等。其邊可表示為對象的關係。圖的邊或者點上存在時間戳，表示邊或者點出現或消失的時間。

歷史圖結構會隨時間的變化而變化，其動態性主要表現為點和邊的不確定性。

歷史圖數據由諸多個Δ構成，每個Δ可以看做一個四元組(v1,v2,operation,timestamp)，分別表示節點1、節點2、操作類型(增\減)和時間戳，一下算法用到的四元組數據就是如此結構。

在做歷史圖相關的計算時，為了避免目標時間距離開始時間過長，我們在線下保存一個整體中部的快照(如圖1)，用以表示該時刻的圖結構,如果查詢時間大於snapshot的時間，那麼我們直接讀取snapshot的內容即可獲得整個時間線半程時的狀態。

4 CSR結構

4.1 結構介紹

CSR結構是一種用兩個數組表示圖數據的數據結構。一個數組（點數組）記錄每個點的鄰居在另一個數組（邊數組）中的位置，邊數組就用於存放鄰居的編號。如此就可以根據兩個數組中的內容還原圖中的所有數據。

4.2 結構特點與優勢

在空間方面，鍊表的每個元素包含兩個部分，一個部分是存儲的數據，另一個部分是指向下一個結點地址的指針，因此用於表示圖的時候需要多佔用m個指針所需要的空間(m表示邊的數目)。而使用CSR結構只需要m+n個int型的空間即可表示同樣的圖(n表示點的數目)。因此，CSR結構更加省空間。

在時間方面，由於數組的元素在內存空間中是連續存放，而鍊表存放的空間可以是連續的，也可以是不連續的，因此在遍歷數據獲取圖信息的時候，CSR結構會比鍊表更快。同時，在處理邊的刪除操作時，鍊表需要進行查找、刪除、重新指向的操作，比較費時。

5 使用CSR結構實現PageRank

5.1 LinkedList Method

使用最直觀的鍊表維護一個圖，對每個delta操作，如果是加邊，則到對應的點指向的鍊表處加上新鄰居節點，如果是減邊，則在該點的鄰居鍊表中找到對應鄰居，刪除節點後連接兩端。在遇到需要計算PageRank的時間點時，根據當前的圖，可以獲取所需要的所有信息（節點數目、終止點數目、節點鄰居等），然後調用PageRank函數進行計算。

在算法2-1中，首先獲取歷史圖的四元組v(Line2~3)，對於增/減操作進行不同的處理(Line7~11)，如果碰到目標時間則將目標時間的所有操作完成後進行計算PageRank值的操作(3~6)

算法2-1 鍊表方法

輸入：Historical graph data v[4],target time array t[]

輸出： PageRank Value in every target time

1. while True do

2. reload v /*讀取四元組數據*/

3. node1,node2,ope,time←v[0],v[1],v[2],v[3]

4. if time is one of target times then

5. calPR() /*計算PageRank值*/

6. end if

7. if ope=1 then

8. addNode(node1,node2) /*添邊*/

9. else

10. deleteNode(node1,node2) /*減邊*/

11. end if

12.end while

5.2 Serial Method

對於CSR結構，最直觀的想法是按照時間順序進行計算。如圖2所示，在snapshot處存在一個CSR結構來保存快照（CSR-A，如圖2-1），同時將區域A的所有delta按照入射節點排序後生成另一個CSR結構（CSR-B，如圖2-2）。相比CSR-A，CSR-B中還存儲的增減操作。計算PageRank時，對於點A，從CSR-A中獲取鄰居（B、C、D），計算PageRank。然後訪問CSR-B，補充區域A的操作帶來的改變，如果CSR-B中B指向A的邊被刪除，就說明之前我們多累加了一個值，那麼這時候減去即可。以此類推其他點。

在算法3-1中首先判斷查詢時間是否集中在時間軸後半部分，是則利用是先處理好的數據生成CSR-A(Line2~5)。之後不斷將v添加到ope_array中(Line14)。如果time是目標時間則將ope_array按被指向節點(node2)進行排序，然後生成CSR-B。之後即可根據CSR-A和CSR-B進行PageRank的計算。

算法3-1 線性法PageRank

輸入：Historical graph data v[4],half historical graph file h_hg_file,target time array t[]

輸出： PageRank Value in every target time

1. initialize:int array ope_array[][4] /*四元組載體*/

2. if first target time >= half_time then

3. h_hg_file.rdbuf()

4. create CSR-A

5. end if

6. while True do

7. reload v

8. node1,node2,ope,time←v[0],v[1],v[2],v[3]

9. if time is one of target time then

10. sort(ope_array) by node2

11. create CSR-B

12. calPR(CSR-A,CSR-B)

13. end if

14. ope_array.append(v)

15. end while

在算法3-2中按照與算法2-2一樣的方法初始化PR[](Line1)，之後開始迭代，對於每個點，收集其在CSR-A中的鄰居，對PageRank值進行累加。再根據該點在CSR-B中的相關操作進行PR值的更新（Line5~6），如果是減邊操作則要扣除之前多加上的值，而如果是加邊操作則要加上對應的值。當某輪PR值與上一輪的差值小於設定閾值時結束迭代。

算法3-2 鍊表方法calPR

輸入：CSR-A,CSR-B

輸出： PageRank Value in the target time

1. initialize:float array PR[]

2. for i=0 up to max_interation do

3. change = 0

4. for node in nodes do

5. accumulate rank in CSR-A

6. update rank according to ope in CSR-B

7. rank += damping_value

8. change += |PR[node] - rank|

9. update PR[node] with rank

10. end for

11. if change < threshold then

12. break

13. end if

14.end for

15.return PR

5.3 Parallel Method

維護一個鄰居集合來表示某個點出現過的鄰居，同時維持一個bitset<query_count>結構來表示每個目標時間該鄰居是否存在，所以如果需要表示所有邊，就需要一個長度為邊長，元素為bitset的數組bitset<query_count> nei_exist[edge_count]。假若在第二個目標時間中，CSR結構中邊數組的第index個邊存在，那麼nei_exist[index][1] = 1，反之則為0。同時維護兩個二維數組node_exist,以此來記錄每個目標時刻中節點存在狀態和出度的信息。比如在第二個目標時間中這樣掃一遍數據之後就知道所有的信息。不同的計算模塊憑藉時間去遍歷每個點的所有出現過的鄰居，看看該時間對應的標誌位上是否為1，為1表示該鄰居該時刻存在，否則不存在。然後就可以計算每個點的PageRank值，以此達到並行的效果。

在算法4-1中，如果目標時間都集中在前半部分，那麼我們只需讀snapshot數據，否則我們需要讀取全部數據(Line2~5)，這些文檔都按照被指向節點排序過。之後根據存在v中的Δ數據來更新nei_exist，同時逐步建立CSR結構(Line7~12)。之後根據每個target time與nei_exist中相應的狀態進行PageRank並行計算(Line13)。

算法4-1 並行法PageRank

輸入：Historical graph data v[4],target time array t[]

輸出： PageRank Value in every target time

1. initialize:bitset array nei_exist[]

2. if last target time < half_time then

3. read front part of the historical file

4. else

5. read whole part of the historical file

6. end if

7. while True do

8. reload v

9. node2,node1,ope,time←v[0],v[1],v[2],v[3]

10. update nei_exist

11. Build CSR

12.end while

13.calPR(nei_exist,all target time) in Parallel way

5.4 算法總結

Serial Method中使用的CSR結構則是利用兩個數組來實現的，數組的物理存儲是連續的，空間佔用也較鍊表來得小，但是我們需要給出數組的長度，以至於其不會浪費空間也不會造成溢出。訪問數組中的數據會快於鍊表。在整合構建CSR前需要對已有數據進行排序，時間複雜度為O(nlogn),之後計算PageRank值時訪問數據只需要在CSR中訪問即可，時間複雜度為O(1)。

Parallel Method中僅需要掃描一遍按時間及被指向結點排好序的數據，之後按照操作類型填入該邊該時刻是否存在即可，該步驟時間複雜度為O(n)，a代表每個點平均。在計算某時刻PageRank值時候訪問CSR結構，獲取數據的時間複雜度都為O(1)，即可計算。

6 實驗

6.1 實驗設置

實驗數據來自KONECT，內容紀錄的是網頁互相連接的Hyperlink networks，實驗中不同大小的數據集都源自該數據集。

數據集中每行數據都是一個四元組(v1,v2,+/-,t)，表示在t時間增加或者刪除v1指向v2的邊。

表1展示了實驗參數的設置，表2展示了每個數據集的特徵。

實驗在以下環境進行：

CPU：16 Intel(R) Xeon(R) CPU E5-2620 v4 @ 2.10GHz，總核數：8

內存：231022144 kB，約220GB

作業系統：Linux

6.2 實驗1：PageRank迭代輪次實驗

6.2.1 實驗說明

我們知道PageRank值需要通過多次迭代才能達到收斂，我們意在探尋不同大小的圖的收斂輪次之間存在的一些關係以及同一個數據集迭代的輪次和計算收斂的閾值之間的變換關係。

我們對於每個數據集，控制其計算閾值，記錄不同閾值下的迭代輪次，以閾值為橫軸，迭代輪次為縱軸作圖。實驗結果如圖3-1所示。

6.2.2 實驗分析

從圖中可以看出，隨著閾值的增大，迭代輪次全部表現為下降趨勢，即閾值越小，所需迭代輪次越大；閾值越大，所需迭代輪次越小。

另外，普遍來說，數據集越大，對於相同的閾值所需的迭代次數越大，但是也存在不同數據集在相同閾值下迭代輪次相同或者小的數據集迭代輪次大於大的數據集的情況。

我們可以得出普遍的結論：閾值越大，數據集越大，所需的迭代輪次也就越大。

6.3 實驗2：多參數的性能測試

6.3.1 實驗說明

實驗測試上述三個方法隨著查詢量增大而發生的改變。其中可變的參數包含查詢位置、查詢跨度。查詢位置的前後分別代表著查詢集中在時間軸的前半部分和後半部分，這樣表示兩種情況，分別是查詢均勻分布在時間軸前半部分和後半部分。

6.3.2 實驗數據圖

6.3.3 實驗分析

由圖3-2可以看出一般來說計算的查詢時間集中在後半部分的時候計算時間會比集中在前半部分的多，因為需要讀取snapshot數據的原因。

另外，無論數據大小、查詢位置是什麼參數，計算時間會隨著問詢量的增大而增大，而且，根據圖中的線條來看，查詢時間和查詢的數量是呈線性關係。

整體來看，使用其他兩個使用CSR結構的方法會比使用鍊表的來得快些。其中LinkedList Method大大快於鍊表，而Parallel Method在準備數據過程中可能有所耗時，但是後續計算可以並行進行，也會對效率有所提高。

6.4 實驗3：單次問詢性能測試

6.4.1 實驗說明

之前的測試是在不同跨度，不同問詢量的情況下進行測試的。而我們測試的時間是諸多個問詢量總共的計算時間，我們也只能得到計算每個問詢的平均時間，而無法獲知這些在時間戳軸上不同位置的問詢所需時間的不同。

為了更加直觀的獲知數據集大小和查詢時間的關係，我們針對不同數據集，只問詢其最大時間戳處的PageRank值，以此來獲得他們之間的關係。實驗結果如圖3-3-1所示。

另外，為了探究整個過程的時間主要耗費在什麼地方，實驗統計了三個方法在不同數據集下準備數據時間與總時間的比（總時間包括準備數據時間和計算時間）。實驗詳情如圖3-3-2所示。

6.4.2 實驗分析

從實驗圖3-3-1中可以看出隨著數據集的不斷增大，使用鍊表來解決問題的時間將會急劇增加，而使用CSR結構來解決問題的Serial Method、Parallel Method則表現出平穩的態勢，二者性能大大優於使用鍊表的方法。

從實驗圖3-3-2中可以看出，鍊表方法的大部分時間都花費在準備數據上，也就是對圖結構的維護操作中。在準備數據上，LinkedList Method花費了總時間的90%左右，而Serial Method也花費了75%左右，Parallel Method花費40%左右。由此我們可以得出，計算部分的時間並不是總耗時的決定因素，如何能高效地維護更新數據才是提高效率的關鍵。

結束語

本文在歷史圖的數據上進行PageRank問題的相關計算，介紹了歷史圖的基本特徵和PageRank的基本思路。在研究主要解決思路時，考慮到歷史圖的各種性質（如頻繁增刪）和處理效率，若使用鍊表結構，在數據量龐大的情況下其查詢所耗費的時間將會很大，因此我們使用CSR結構作為主要的數據結構。在此基礎上借鑑串行計算和並行計算的思想產生了兩個不同的方法，並分析了他們各自的特點。

實驗表明，使用CSR結構解決歷史圖上PageRank問題的性能確實會優於使用鍊表結構，而且效果明顯。

目前，在單機情況下，對於處理多個問詢Parallel Method的效率低於Serial Method的效率。在接下來的工作中會考慮使用分布式數據處理系統來對Parallel Method進行實驗優化，嘗試提高其計算效率。

參考文獻

[1]WU J P,LIN S,XU K,et al.Advances in Evolvable New Generation Internet Architecture[J].Chinese Journal of Computer,2012,35(06):1094-1108.

吳建平,林嵩,徐恪等.可演進的新一代網際網路體系結構研究進展[J].計算機學報,2012,35(06):1094-1108.

[2]Przytycka T M, Singh M , Slonim D K.Toward the dynamic interactome:It's about time[J].Briefings in Bioinformatics,2010,11(1):15–29.

[3]CAO J.Analysis of Google's PageRank techno-

logy[J].Journal of Information,2002(10):15-18.

曹軍.Google的PageRank技術剖析[J].情報雜誌2002(10):15-18.

[4]Chang J W,DAI D H.Personalized Recommend-

ation Algorithm Based on PageRank and Spectral Method[J].Computer Science,2018,45(S2):398-401.

常家偉,戴牡紅.基於PageRank和譜方法的個性化推薦算法[J].計算機科學,2018,45(S2):398-401.

[5]LI C S,LIU X G,JIAO H T et al.An Improved PageRank Algorithm Based on APP Search System[J].Computer and Modernization, 2018(07):24-27+38.

李春生,劉小剛,焦海濤,張可佳.基於APP搜索系統的PageRank改進算法[J].計算機與現代化,2018(07):24-27+38.

[6]Francisco Pedroche,Esther García,Miguel Romance,et al.On the spectrum of two-layer approach and Multiplex PageRank[J]. Journal of Computational and Applied Mathematics,2018,344.

[7]Harary F,Gupta G.Dynamic graph models[J]. Mathematical and Computer Modelling, 1997, 25(7):79-87.

[8]DING L L,LI Z D,JI W T, et al.Reachability Query of Large Scale Dynamic Graph Based on Improved Huffman Coding[J]. Acta Electronica Sinica,2017,45(02):359-367.

丁琳琳,李正道,紀婉婷,宋寶燕.基於改進哈夫曼編碼的大規模動態圖可達查詢方法[J].電子學報2017,45(02):359-367.

[9]WANG C,CHEN L.Continuous Subgraph Pattern Search over Graph Streams[C]// International Conference on Data Engineering. IEEE, 2009.

[10] FAN W , LI J , LUO J , et al.Incremental graph pattern matching[C]//Acm Sigmod International Conference on Management of Data. ACM, 2011.

[11]Choudhury S, Holder L, Chin G, et al.Proc. of the Workshop on Dynamic Networks Management and Mining[C]// International Conference on Management of Data. SIGMOD/PODS'13, 2013.

[12]WU L K,XIAO X K,DENG D X, et al.Shortest Path and Distance Queries on Road Networks:An Experimental Evaluation[J].Proceeding of the VLDB Endowment, 2012,5(5):406-417.

[13] Page L,Brin S,Motwani R,et al. The PageRank Citation Ranking: Bringing Order to the Web[J]. Stanford Digital Libraries Working Paper,1998, 9(1):1-14.

[14]WEI Z W,HE X D,X X K,et al. TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs[C].// International Conference on Management of Data.SIGMOD,2018.

[15]HAVELIWALA,T.H .Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(4):784-796.

[16] ROUL R.K., SAHOO J.K., ARORA K. Query-Optimized PageRank: A Novel Approach[M]. Computational Intelligence in Data Mining. Advances in Intelligent Systems and Computing. Singapore:Springer,2019:673-683

[17]LI C C,KANG Z J,YU H G, et al. Identification Method of Key Nodes in Power System Based on Improved PageRank Algorithm[J]. Transactions of China Electrotechnical Society,2019,34(09):168-175.

李昌超, 康忠健, 於洪國, et al. 基於PageRank改進算法的電力系統關鍵節點識別[J].電工技術學報, 2019, 34(09):168-175.

[18]LIU Z Y,LI Q F,CENG C, et al.An Optimization Method of PageRank Based on Spark and its Application Research[J].Journal of CAEIT, 2018(4):399-405.

劉振宇, 李欽富, 曾操, et al.基於Spark的PageRank算法優化及其軍事應用研究[J]. 中國電子科學研究院學報, 2018(4):399-405 

(責編：劉揚、趙光霞)