[發明專利]一種同質關系大圖的摘要提取方法及系統

在審

• 申請號: 202110308958.7
• 申請日: 2021-03-23
• 公開（公告）號: CN113139098A
• 公開（公告）日: 2021-07-20
• 發明（設計）人: 劉盛華;程學旗;周厚銓;劉財政;沈華偉
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06N3/04
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國

1.一種同質關系大圖的摘要提取方法，其特征在于，包括：

步驟1、獲取待摘要提取的關系圖數據作為當前圖數據，且該關系圖數據為同質關系大圖，并將該當前圖數據中每個節點均看作超點；

步驟2、根據該當前圖數據的鄰接矩陣，通過局部敏感哈希對該當前圖數據中節點進行分組；

步驟3、從組中隨機選擇多個超點對，分別計算該超點對若合并后和該關系圖數據之間的差距，選擇差距最小的超點對進行合并，得到重構圖數據；

步驟4、輸出該重構圖數據作為摘要提取結果。

2.如權利要求1所述的同質關系大圖的摘要提取方法，其特征在于，該步驟3中得到重構圖數據后，迭代次數加1；判斷當前迭代次數是否達到預設值，若是，則執行步驟4，否則將該重構圖數據作為當前圖數據，再次執行該步驟2。

3.如權利要求1所述的同質關系大圖的摘要提取方法，其特征在于，該步驟3包括：通過下式得到該超點對若合并后和該關系圖數據之間的差距L(M,D)；

L(M,D)＝L(M)+L(D|M)

其中d_i和d_j表示節點i和j的度數，D_k和D_l表示超節點S_k和S_l的度數，A_S為該超點對合并后得到的摘要圖的鄰接矩陣，A'為以該摘要圖重建的圖的鄰接矩陣，A為該關系圖數據的鄰接矩陣，A'(i,j)為該摘要圖重建的圖的鄰接矩陣中節點i到節點j的鄰邊權重，A_S(i,j)為該摘要圖的鄰接矩陣中節點i到節點j的鄰邊權重，A(i,j)為關系圖數據的鄰接矩陣中節點i到節點j的鄰邊權重，LN為編碼正整數長度的函數，LNU為伯努利編碼長度函數，n，m分別為節點數和邊數，w_i為邊的權重，d_i為節點i的度，L(M)為該摘要圖的描述長度，L(D|M)是重建誤差。

4.如權利要求1所述的同質關系大圖的摘要提取方法，其特征在于，該步驟2包括：該當前圖數據中每一個節點會根據其鄰居節點，得到一個哈希值，將哈希值相同的節點分到一組。

5.如權利要求1所述的同質關系大圖的摘要提取方法，其特征在于，該關系圖數據為無權無向圖。

6.一種同質關系大圖的摘要提取系統，其特征在于，包括：

模塊1，用于獲取待摘要提取的關系圖數據作為當前圖數據，且該關系圖數據為同質關系大圖，并將該當前圖數據中每個節點均看作超點；

模塊2，用于根據該當前圖數據的鄰接矩陣，通過局部敏感哈希對該當前圖數據中節點進行分組；

模塊3，用于從組中隨機選擇多個超點對，分別計算該超點對若合并后和該關系圖數據之間的差距，選擇差距最小的超點對進行合并，得到重構圖數據；

模塊4，用于輸出該重構圖數據作為摘要提取結果。

7.如權利要求6所述的同質關系大圖的摘要提取系統，其特征在于，該模塊3中得到重構圖數據后，迭代次數加1；判斷當前迭代次數是否達到預設值，若是，則調用該模塊4，否則將該重構圖數據作為當前圖數據，再次調用該模塊2。