[發明專利]一種大規模時序圖頂點相似度計算方法

在審

• 申請號: 201910012983.3
• 申請日: 2019-01-07
• 公開（公告）號: CN109684520A
• 公開（公告）日: 2019-04-26
• 發明（設計）人: 袁野;王國仁;苗壯;王一舒;馬玉亮
• 申請（專利權）人: 東北大學
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 北京易捷勝知識產權代理事務所(普通合伙) 11613
• 代理人: 韓國勝

本發明涉及一種大規模時序圖頂點相似度計算方法，其包括如下步驟:S1、將社交網絡各個頂點的數據抽象為時序圖；S2、通過隨機游走方法和路徑融合方法建立樹形索引，使用Bootstrap抽樣方法估計索引樹中每層節點時間差的期望，使用Monte Coral方法計算目標頂點與其他頂點的相似度；S3、根據步驟S2計算出的目標頂點與其他頂點相似度，找出與目標定點最相似的k個頂點。本發明的技術方法，使頂點相似度計算的更加準確，用于推薦系統中能夠更加精確的對用戶進行推薦。

技術領域

本發明涉及一種大規模時序圖頂點相似度計算方法，屬于數據庫技術領域。

背景技術

現實生活中的許多場景可以抽象成圖模型，從而進行數據的處理和分析。近年來隨著數據科學的迅猛發展，人們對于數據分析結果的精確具有較高的要求，然而當前對于圖模型的研究大多集中在靜態圖上。靜態圖模型忽略了真實場景中的時間因素，這使得在靜態圖中的數據分析結果不準確。

頂點相似性計算是圖論中的基本問題，廣泛應用于社交網絡、推薦系統等現實應用。以社交網絡為例，可以使用圖結構來表示社交網絡的拓撲結構，圖中頂點表示社交網絡中的用戶，圖中的邊可以表示社交網絡中用戶之間的聯系，在社交網絡中可以根據用戶間的相似性進行朋友推薦等活動，因此計算圖中頂點相似性是一個十分重要的問題。當前的研究大多使用靜態圖對現實場景進行建模，忽略了現實場景中的時間因素，對分析結果造成了很大影響。針對這種情況，應使用時序圖對現實場景進行建模，保留時間因素對現實場景的影響。因此如何高效地處理時序圖中頂點相似性計算是一個亟待解決的問題。

發明內容

(一)要解決的技術問題

為了解決現有技術的上述問題，本發明提供一種大規模時序圖頂點相似度計算方法。

(二)技術方案

為了達到上述目的，本發明采用的主要技術方案包括：

一種大規模時序圖頂點相似度計算方法，包括如下步驟：

S1、將社交網絡各個頂點的數據抽象為時序圖；

S2、通過隨機游走方法和路徑融合方法建立樹形索引，使用Bootstrap抽樣方法估計索引樹中每層節點時間差的期望，使用Monte Coral方法計算目標頂點與其他頂點的相似度；

S3、根據步驟S2計算出的目標頂點與其他頂點相似度，找出與目標定點最相似的k個頂點。

如上所述的計算方法，優選地，在步驟S1中，所述時序圖表示為G_T＝(V,E,T)，其中V表示社交網絡中的頂點集合，E表示的是網絡中時序邊的集合，T表示的各個頂點聯系時刻的集合。

如上所述的計算方法，優選地，在步驟S2中，所述樹形索引的建立包括：

S20101、對所述時序圖G_T＝(V,E,T)中任意頂點u∈V，創建一顆以u為葉節點的單節點樹，并記level(u)＝0；

S20102、對每個葉節點進行反向隨機游走，即對葉節點u進行反向隨機游走，得到時序路徑p_u＝(u,v)，其中v∈Γ_in(u,G)；記level(v)＝level(u)+1，且節點u到達節點v的時間記為t_v(u)；

S20103、判斷任意兩個葉節點生成的時序路徑是否符合路徑融合條件，若符合則進行路徑融合；

否則繼續進行反向隨機游走；直到節點的入鄰節點集為空，或者節點的入鄰節點集合均不符合時序路徑條件，此時停止生成索引；

S20104、重復步驟S20101-S20103直到生成索引數量達到預期數量。