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

在審

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

1.一種大規模時序圖頂點相似度計算方法，其特征在于，其包括如下步驟：

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

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

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

2.如權利要求1所述的計算方法，其特征在于，在步驟S1中，所述時序圖表示為G_T＝(V,E,T)，其中V表示社交網絡中的頂點集合，E表示的是網絡中時序邊的集合，T表示的各個頂點聯系時刻的集合。

3.如權利要求1所述的計算方法，其特征在于，在步驟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直到生成索引數量達到預期數量。

4.如權利要求1所述的計算方法，其特征在于，在步驟S2中，使用Bootstrap抽樣方法估計索引樹中每層節點時間差的期望就是估計索引樹中不同level中節點的時間差的期望進行估計；對索引樹中level＝i層節點時間差的期望記為t_i。

5.如權利要求1所述的計算方法，其特征在于，在步驟S2中，所述使用Monte Coral方法計算目標頂點與其他頂點的相似度包括：對于目標時序圖G_T＝(V,E,T)，建立了r個索引；對于給定目標頂點u，每個索引的葉節點上找到節點u，之后記錄與節點u在同一顆樹上的其他葉節點，并記錄該節點與目標節點到達最近的公共祖先節點的路徑長度。

6.如權利要求5所述的計算方法，其特征在于，所述最近的公共祖先節點的路徑長度為頂點u和v在路徑長度為i是首次相遇，記為first(p_u,p_v)＝i，根據公式(1)近似計算頂點相似度，其中，p_u＝(u₁,u₂,…,u_t)，p_v＝(v₁,v₂,…,v_t)，1≤i≤k，