[發(fā)明專利]一種計算大圖節(jié)點鄰近度的TopPPR方法

在審

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

1.一種計算大圖節(jié)點鄰近度的TopPPR方法，其特征在于包括以下步驟：

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

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

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

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

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

2.如權利要求1所述的一種計算大圖節(jié)點鄰近度的TopPPR方法，其特征在于：所述步驟2)中，對當前候選集進行前向搜索，并對當前Top-k節(jié)點集V_k和候選集C進行更新的方法，包括以下步驟：

2.1)確定進行前向搜索的截止閾值

前向搜索截止閾值的初始值的計算公式為：

式中，m為給定圖的邊數(shù)，n是給定圖的節(jié)點數(shù)；

2.2)根據前向搜索截止閾值以及給定源點s對當前候選集C執(zhí)行前向搜索，對于候選集中的每一個節(jié)點u，得到其前向殘余值r^f(s,u)和前向已確定值π^f(s,u)，

2.3)根據各個節(jié)點的前向殘余值r^f(s,u)和前向已確定值π^f(s,u)，對Top-k節(jié)點集V_k和候選集C進行更新。

3.如權利要求1所述的一種計算大圖節(jié)點鄰近度的TopPPR方法，其特征在于：所述步驟3)中，采用CandidateUpdate算法執(zhí)行隨機游走采樣，并對Top-k節(jié)點集V_k以及候選集C進行更新的方法，包括以下步驟：

3.1)確定進行隨機游走采樣的次數(shù)n_r；

3.2)根據步驟2)中所有非零的前向殘余值r^f(s,t)構建Alias結構；

3.3)以的概率從構建的Alias結構中隨機采樣一個點u，從點u出發(fā)以α的停止概率執(zhí)行隨機游走，其中，為所有前向殘余量之和，即：

3.4)假設該隨機游走停止在節(jié)點v，則在批量后向搜索中形成的倒排表r^b中找到所有使得殘余量r^b(v,t)不為0的點t，并對t的PPR的估計值進行更新；

3.5)重復步驟3.2)～3.4)，直到完成n_r次隨機游走采樣，n_r次隨機游走采樣結束后，對候選集C中每個節(jié)點的PPR的估計值的置信區(qū)間β(s,t)進行更新；

3.6)根據各個節(jié)點t的PPR的估計值和置信區(qū)間β(s,t)，對各個節(jié)點t的PPR的精確值的范圍進行估計，并根據估計結果對當前Top-k節(jié)點集V_k以及候選集C進行更新。

4.如權利要求1所述的一種計算大圖節(jié)點鄰近度的TopPPR方法，其特征在于：所述步驟3.1)中，隨機采樣次數(shù)n_r的初始值的計算公式為：

式中，m為給定圖的邊數(shù)，n是給定圖的節(jié)點數(shù)。