[發明專利]一種基于蒙特卡洛方法逆向求解PageRank的算法

在審

• 申請號: 201710107210.4
• 申請日: 2017-02-27
• 公開（公告）號: CN107038212A
• 公開（公告）日: 2017-08-11
• 發明（設計）人: 楊溢;賴斯龑;郭夢含;林小拉
• 申請（專利權）人: 中山大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06T1/20
• 代理公司: 廣州粵高專利商標代理有限公司44102
• 代理人: 林麗明

1.一種基于蒙特卡洛方法逆向求解PageRank的算法，其特征在于，包括以下步驟：

S1：對蒙特卡洛算法的參數進行初始化，并讀取待處理圖的信息；

S2：將圖的信息進行處理并儲于GPU的顯存中，利再用GPU多線程計算圖對應的概率轉移數組；

S3：啟動GPU的多線程功能，利用圖對應的概率轉移數組通過蒙特卡洛的方法仿真計算圖的解的每個分量對應的PageRank值，將每個線程求解的PageRank值進行求和，得出最終的結果。

2.根據權利要求1所述的基于蒙特卡洛方法逆向求解PageRank的方法，其特征在于，所述步驟S1的過程如下：

S11：對蒙特卡洛算法的參數進行初始化，包括衰減速率，馬爾科夫鏈的鏈長，馬爾科夫鏈的數量，隨機數的種子以及GPU多線程中每個塊的線程數量；

S12：讀取待處理的圖中的信息，建立空的臨時使用的鄰接表T，空的懸掛點的集合L，每次讀取原始圖中的一條邊，就在鄰接表T中的相應位置增加該邊的相應信息；

S13：檢查每一個頂點是否沒有出邊，如果沒有出邊，就將該點的加入到集合L中，統計L中的元素個數即懸停頂點的個數y。

S14：對頂點重新進行編號，對懸停點優先編號，然后再對其他頂點編號。因此懸停點編號都在前面，其他頂點編號在后；

S15：建立空的壓縮稀疏行的方式使用的數組，權值數組Val，下標數組Col_ind以及索引數組Row_ptr，對每一個頂點，不再分別添加每個懸停點到該點的邊，而是添加一條代表所有懸停頂點到該點的邊，權值為其中α代表衰減速率，N代表頂點數量，y代表懸停頂點的數量，再添加鄰接表中對面的邊，以入邊的形式保存到權值數組Val，下標數組Col_ind，在索引數組Row_ptr中添加對應的索引。

3.根據權利要求2所述的基于蒙特卡洛方法逆向求解PageRank的方法，其特征在于，所述步驟S2的過程如下：

S21：利用GPU，對通過函數將權值數組Val，下標數組Col_ind以及索引數組Row_ptr復制到GPU的顯存中；

S22：建立一個概率數組P，利用GPU加速啟動多線程計算權值數組Val中每個元素對應的概率存儲于概率數組P中，計算方法為該元素在相同頂點的所有入邊的權值之和的比例。

4.根據權利要求3所述的基于蒙特卡洛方法逆向求解PageRank的方法，其特征在于，所述步驟S3的過程如下：

S31：對于需要求解的分量，以剛才初始化的參數啟用對應數量的GPU線程，每個線程將模擬一條馬爾科夫鏈計算期望值；

S32:每個進程中需要模擬D步的馬爾科夫鏈，每一步需要有計算當前對應的狀態對應的期望值累加到總期望值。產生新的隨機數，判斷隨機數是不是小于該狀態下對應的概率數組中的第一個元素，如果是則說明需要跳轉到其中一個懸停頂點，利用以下公式計算跳轉的懸停點的編號：

如果不是，則使用二分的方法尋找剩下元素中需要跳轉的頂點；

S33：重復直至模擬D步的鏈長，通過將所有線程計算的期望值累加，計算得出該點的PageRank值。