[發明專利]一種基于社區結構的子圖匹配方法及裝置

有效

• 申請號: 201810836811.3
• 申請日: 2018-07-26
• 公開（公告）號: CN109063089B
• 公開（公告）日: 2021-04-23
• 發明（設計）人: 王朝坤;樓昀愷
• 申請（專利權）人: 清華大學
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 北京中強智尚知識產權代理有限公司 11448
• 代理人: 黃耀威

本發明公開一種基于社區結構的子圖匹配方法及裝置，方法包括：導入包含目標模式的文件，分析目標模式結構，找出目標模式中互相匹配等價的子圖；根據網絡圖數據生成以社區作為結點的超圖，計算每個社區中各結點與本社區的鄰接社區間的邊數；在網絡圖各社區內部利用預設子圖匹配算法找出各社區的與目標模式結構匹配的子圖，獲得第一匹配結果；在網絡圖中，基于網絡圖每個社區中各結點與本社區的各鄰接社區間的邊數和找出的目標模式中互相匹配等價的子圖找出跨社區的與目標模式匹配的子圖，獲得第二匹配結果；將第一、二匹配結果匯總獲得最終子圖匹配結果。可提高子圖匹配速度，減少時間開銷。

技術領域

本發明實施例涉及計算機技術領域，具體涉及一種基于社區結構的子圖匹配方法及裝置。

背景技術

隨著圖數據在各領域的廣泛應用，對圖數據處理的相關算法的需求也與日俱增。其中，子圖匹配算法作為圖上的一個經典算法，如何進行高效的子圖匹配成為了一個重要的問題。子圖匹配指的是由用戶指定目標模式，通過子圖匹配算法在圖中找到所有與目標模式同構的子圖的過程。子圖匹配的應用包括找滿足特定條件的單個結點、找存在特定關系的若干結點等，如在社交網絡中找到所有互相認識的三個人組成的結構。

Ullmann算法和vf2算法是經典的子圖匹配方法。Neo4j是常用的圖數據庫系統，它對于子圖匹配沒有專門的實現，而是通過進行路徑匹配達到子圖匹配的效果。

Ullmann算法、vf2算法和Neo4j上使用的子圖匹配方法在實際計算中速度均較慢，當數據量較大時，算法的時間開銷很大，不能滿足實際應用的需求。而且，這些算法沒有充分利用圖的社區結構，有較大的改進空間。

鑒于此，如何進行子圖匹配，以提高子圖匹配的計算速度成為目前需要解決的技術問題。

發明內容

由于現有方法存在上述問題，本發明實施例提出一種應用于社交網絡基于社區結構的子圖匹配方法及裝置。

第一方面，本發明實施例提出一種應用于社交網絡基于社區結構的子圖匹配方法，包括：

導入包含代表三個互相認識的人的目標模式的文件，基于所導入的文件，分析目標模式的結構，找出目標模式中互相匹配等價的子圖；

根據社交網絡生成以社區作為結點的超圖，計算每個社區中各結點與本社區的鄰接社區中的結點存在的邊數；

在所述社交網絡中各社區內部，利用預設子圖匹配算法，分別找出各社區內所有互相認識的三個人構成的子圖，獲得社區內子圖匹配結果；

在所述社交網絡中所有社區之間，利用預設子圖匹配算法，在所述超圖上對目標模式進行結點可重復的子圖匹配，將得到的分配方案存儲在預設表中，當所述預設表內的元素數量大于預設閾值時，對于所述預設表中的每個分配方案s基于所計算的每個社區中各結點與本社區的各鄰接社區間的邊數和所找出的目標模式中互相匹配等價的子圖進行處理，判斷s中被分配到所述社交網絡中各社區的目標模式的結點數量是否大于該社區中的結點數量，判斷s是否可以通過匹配等價關系轉換成索引值更小的分配方案，以及對于s中被分配到相同社區的目標模式中的結點，兩兩計算目標模式中它們在除本社區之外的其它各社區中的公共一跳鄰居數來進行剪枝，找出跨社區的所有互相認識的三個人構成的子圖，獲得社區間子圖匹配結果；

將所述社區內子圖匹配結果和社區間子圖匹配結果進行匯總，獲得目標模式與所述社交網絡的子圖匹配結果，即獲得所述社交網絡中所有互相認識的三個人。

可選地，所述導入包含目標模式的文件，基于所導入的文件，分析目標模式的結構，找出目標模式中互相匹配等價的子圖，包括：

導入包含目標模式的文件，解析所述目標模式中的結點和邊及相關屬性；

基于解析出的所述目標模式中的結點和邊及相關屬性，分析目標模式的結構，找出目標模式中互相匹配等價的子圖。