[發明專利]一種計算大圖節點鄰近度的TopPPR方法

在審

• 申請號: 201810563316.X
• 申請日: 2018-06-04
• 公開（公告）號: CN108776816A
• 公開（公告）日: 2018-11-09
• 發明（設計）人: 魏哲巍;何曉東;肖小奎;王思博;商爍;文繼榮
• 申請（專利權）人: 中國人民大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京紀凱知識產權代理有限公司 11245
• 代理人: 徐寧;孫楠

本發明涉及一種計算大圖節點鄰近度的TopPPR方法，其特征在于包括以下步驟：1)確定Top?k節點集和候選集的初始值；2)對當前候選集執行前向搜索，并根據前向搜索結果對當前Top?k節點集和候選集進行更新；3)以前向搜索得到的所有非零的前向殘余值為基礎，執行n_r次隨機游走采樣，并對當前Top?k節點集和候選集進行更新；4)對步驟3)中的候選集執行批量后向搜索，根據后向搜索結果對當前Top?k節點集和候選集進行更新；5)對Top?k節點集中的節點數目進行判斷，當滿足閾值條件時，停止迭代，否則重復步驟2)～4)，直到滿足閾值條件，得到最終結果。本發明可廣泛應用于大圖節點的top?k查詢領域。

技術領域

本發明涉及一種大圖節點鄰近度計算方法，特別是關于一種計算大圖節點鄰近度的TopPPR方法。

背景技術

PPR(Personalized PageRank)是一種經典的大圖鄰近度的度量標準，它衡量了有向圖中所有節點與某一給定節點的相關度大小。PPR的相關研究中，主要關心三類 PPR查詢：

①點到點查詢：計算有向圖中源點s到一固定點v的PPR值；

②單源查詢：計算有向圖中源點s到圖中所有點的PPR值；

③Top-k查詢：找到有向圖中從源點s出發最大的k個PPR值對應的點集。在上面 這幾類查詢里，Top-k PPR查詢尤其重要。

目前已有的解決Top-k PPR查詢問題的算法有著兩大局限性。第一是這些方法應用在大圖上面都有著不可接受的空間和時間占用，或者對Top-k PPR的返回結果沒有 準確率(precision)的保證，這意味著如果想要準確的Top-k PPR結果，也許會漏掉 一些。其次，大多數的算法需要對有向圖進行一個預處理，這樣就使得這些方法無法 應用到頻繁更新的圖上(比如Twitter、Weibo這樣的社交網絡圖)。

發明內容

針對上述問題，本發明的目的是提供一種計算大圖節點鄰近度的TopPPR方法，它擁有極高的效率使其可以應用在大圖上，同時對準確度還有很強的理論保證。只需初 始給定一個準確度參數ρ∈(0,1]，TopPPR就會以1-1/n的可能性返回準確度至少為ρ 的Top-kPPR結果。

為實現上述目的，本發明采取以下技術方案：一種計算大圖節點鄰近度的TopPPR方法，其特征在于包括以下步驟：

1)根據給定圖的點集V確定Top-k節點集V_k和候選集C的初始值；

2)根據預先確定的前向搜索截止閾值以及給定源點對當前候選集C執行前向搜索， 并根據得到的各個節點的前向殘余值r^f(s,u)和前向已確定值π^f(s,u)，對當前Top-k節點集V_k和候選集C進行更新；

3)以前向搜索得到的所有非零的前向殘余值為基礎，采用CandidateUpdate算法執行n_r次隨機游走采樣，并根據隨機游走采樣結果對步驟2)中Top-k節點集V_k和候 選集C進行更新；

4)根據預先確定的后向搜索截止閾值和給定終點對步驟3)中的候選集C執行批量后向搜索，根據批量后向搜索結果建立關于后向殘余量和已確定量的倒排表r^b和π^b， 并對當前Top-k節點集V_k以及候選集C進行更新；

5)對步驟4)得到的Top-k節點集V_k中的節點數目進行判斷，當滿足閾值條件時，停止迭代，否則重復步驟2)～4)，直到滿足閾值條件，此時得到的Top-k節點集V_k即 為最終結果。