[發明專利]基于單源SimRank精確解的好友推薦方法

有效

• 申請號: 202010536506.X
• 申請日: 2020-06-12
• 公開（公告）號: CN111506833B
• 公開（公告）日: 2023-05-02
• 發明（設計）人: 魏哲巍;王涵之;袁野;杜小勇;文繼榮
• 申請（專利權）人: 中國人民大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06F18/22
• 代理公司: 北京興智翔達知識產權代理有限公司 11768
• 代理人: 張玉梅

1.一種基于單源SimRank精確解的好友推薦方法，其特征在于，包括：

將目標用戶、用戶及用戶間的關系轉換為圖結構G，其中，所述圖結構G中包括與所述用戶對應的節點以及與所述用戶間的關系對應的邊，所述目標用戶為所述圖結構的源節點v_i，所述圖結構G包括n個節點；

在圖結構G中，計算源節點v_i關于圖上所有節點的個性化佩奇排名，構成個性化佩奇排名向量其中，是n維向量，的第k維存儲的數為從源節點v_i出發的隨機游走最終停止在節點v_k的概率，v_k為圖結構中的任一節點，所述隨機游走在每步游走時都以的概率停止，以的概率隨機走向當前節點的任意入鄰居節點；

計算圖結構G上所有節點的不再相遇概率，形成不再相遇概率矩陣所述不再相遇概率矩陣對角線上的第k個元素存儲的數值為節點v_k的不再相遇概率

根據n維向量以及不再相遇概率矩陣計算關于源節點v_i的單源SimRank相似度，得到n維向量重復執行L輪SimRank相似度的計算并對n維向量進行更新，得到更新L輪后的n維向量其中，c為衰減系數，c∈[0,1]，ε為SimRank計算結果的絕對誤差；

找到n維向量所有維中值最大的t維所對應的t個節點，將與所述t個節點對應的t個用戶作為結果推薦給目標用戶。

2.如權利要求1所述的好友推薦方法，其特征在于，所述在圖結構G中，計算源節點v_i關于圖上所有節點的個性化佩奇排名，構成n維向量包括:

根據源節點v_i到節點v_k的出鄰居節點的個性化佩奇排名向量，計算源節點v_i到節點v_k的個性化佩奇排名向量，其中，節點v_k為圖結構G中的任一節點。

3.根據權利要求2所述的好友推薦方法，其特征在于，所述根據源節點v_i到節點v_k的出鄰居節點的個性化佩奇排名向量，計算源節點v_i到節點v_k的個性化佩奇排名向量包括：

獲取圖結構G的概率轉移矩陣P，其中，P為n×n維的矩陣，第j行第i列處記錄的值為從節點v_i沿入邊一步轉移至節點v_j的概率；

根據公式一對進行更新，并對向量進行存儲，所述公式一包括：

其中，l為中間變量，l＝0,1,…,L；對均為n維向量，0≤i≤n-1，及初始化為為除了第i維為1其余維均為0的n維向量，

重復執行L次根據公式一對進行更新的過程，獲得更新后的n維向量

4.根據權利要求3所述的好友推薦方法，其特征在于，所述根據n維向量以及不再相遇概率矩陣計算關于源節點v_i的單源SimRank相似度，得到n維向量重復執行L輪SimRank相似度的計算并對n維向量進行更新，得到更新L輪后的n維向量包括：

當進行第一輪計算時，根據以下公式計算SimRank相似度：

當進行第二輪到第L輪的計算時，根據公式二對n維向量進行更新，重復更新過程直至第L輪的計算，得到更新L輪后的n維向量所述公式二為：

其中，為所述不再相遇概率矩陣，l為中間變量，l＝0,1,…,L；對為n維向量。