[發明專利]一種匹配圖挖掘方法及設備

有效

• 申請號: 201710109050.7
• 申請日: 2017-02-27
• 公開（公告）號: CN108509452B
• 公開（公告）日: 2022-04-12
• 發明（設計）人: 謝淼
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F16/50
• 分類號: G06F16/50
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 郝傳鑫;熊永強

本發明實施例公開了一種匹配圖挖掘方法及設備，該方法包括：根據預先獲取的離線索引和第一查詢圖生成交互感知索引，該交互感知索引包含代表所有第一片段的節點且該交互感知索引為一張索引圖；若一個片段包含于該第一查詢圖且該片段為該離線索引中的節點所代表的頻繁片段或者判定非頻繁片段，則該片段為該第一片段；代表每個片段的節點用于描述該片段的特征；根據預設的多個匹配范式中的一個匹配范式從該交互感知索引中挖掘該第一查詢圖的匹配圖。采用本發明實施例，建立的交互感知索引能夠滿足不同匹配范式對應的查詢圖的挖掘要求。

技術領域

本發明涉及計算機技術領域，尤其涉及一種匹配圖挖掘方法及設備。

背景技術

隨著在線系統數據量的激增，越來越多的關聯信息呈現出海量圖數據形態，例如，軟件剽竊檢測中的系統調用關系圖、數據流圖、生物信息圖、蛋白質相互作用(英文：Protein-Protein Interaction，簡稱：PPI)網絡、知識網絡、人員合作關系網、專利引用網絡及社會網絡等。如何對圖信息進行精準且快速地挖掘成為近年來急需解決關鍵問題之一。圖(模式)匹配是一種圖信息查詢方法，已經廣泛用于各種圖數據庫的查詢中。一般而言，用戶首先需要從實際應用中抽象出一組對圖數據中節點關系與屬性的約束，這種約束通常表達為一個查詢圖，其中包含帶有標簽屬性的節點及節點之間的關系。然后利用該查詢圖，對圖數據庫中的信息進行查詢，圖數據庫是一個由多個獨立的連通圖組成的集合，獲取圖數據庫中所有能夠子圖匹配于查詢圖的匹配圖，即每張匹配圖中至少存在一個子圖完全“滿足”查詢圖中給定的約束。挖掘匹配圖時用到的子圖匹配范式用于衡量一個圖是否“滿足”查詢圖中給定約束。

對于不同的圖匹配范式而言，衡量是否“滿足”查詢圖中給定約束的標準也不同。常見的圖模式匹配范式有子圖同構匹配、相似子圖匹配和泛化子圖匹配等。子圖同構匹配方法要求所匹配得到的匹配圖(也稱“結果圖”)必須嚴格滿足所有給定的約束，即結果圖包括查詢圖的所有的節點與邊的映射關系；相似子圖匹配通過一個用戶給定的參數Φ來控制約束的程度，允許匹配圖中有最多Φ個邊或節點與查詢圖不匹配；子圖同構匹配與相似圖匹配所需的查詢圖都為無權圖而泛化子圖匹配的查詢圖是有權圖，該有權圖包含權重信息來指示節點間最大的距離約束，刻畫了節點間約束最大所允許的最長路徑距離。查詢圖不同會導致挖掘出的匹配圖不同，如果建立一個索引使得該索引中的各個節點代表的圖能夠滿足不同查詢圖的挖掘要求是本領域的技術人員正在研究的問題。

發明內容

本發明實施例所要解決的技術問題在于，提供一種匹配圖挖掘方法及設備，能夠滿足不同匹配范式對應的查詢圖的挖掘要求。

下面首先對本發明涉及到的相關概念進行介紹：

【圖】本發明關注的圖G＝(V,E,L)是無向圖，其中V為節點集合，為邊集合，L是一個標識函數，映射每個節點u∈V與一個標識集合L(u)∈Σ。標識函數L具體為每個節點賦予了具有實際應用意義的一組標識，例如關鍵詞，博客主題，名稱，專業，公司等。標識集合Σ為所有這種屬性值的全集。定義G(V,E)為上下文簡寫。假設給定的數據圖G為連通圖。

【CAM碼】給定一個圖G，假設M_n×n為G中包含邊的鄰接矩陣，那么G的CAM碼是通過在從頂部到底部，并從最左邊到最右側數值的順序串聯M(包括在對角線上的數值)的下三角區域形成的序列。

【規范標簽】給定兩個圖G和H,(G,H)的規范標簽是一個節點映射函數f:V_G→V_H，使得如果(u,v)∈G.E，那么(f(u),f(v))∈H.E。