[發明專利]一種基于對稱破壞的子圖同構約束求解方法

有效

• 申請號: 201810607429.5
• 申請日: 2018-06-13
• 公開（公告）號: CN108932306B
• 公開（公告）日: 2021-05-25
• 發明（設計）人: 徐周波;梁軒瑜;戴瑀君;寧黎華;楊健;黃文文;劉桂珍;張鵾
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 桂林市持衡專利商標事務所有限公司 45107
• 代理人: 陳躍琳

本發明公開一種基于對稱破壞的子圖同構約束求解方法，其采用約束滿足問題CSP的模型，首先分析模式圖和目標圖的節點、邊等信息構建子圖同構問題的約束滿足問題的模型，添加破壞對稱約束，再根據約束滿足問題的求解方法，對所建立的模型進行求解。破壞對稱技術包括檢測自同構節點和通過Schreier?Sims算法生成對稱破壞約束兩步。由于對稱破壞技術用于解決CSP中的對稱性，通過施賴埃爾一西姆斯算法對置換群的操作生成破壞對稱約束，能夠避免對稱子樹的二次搜索，降低組合復雜性。因此算法執行過程中，有效縮減了搜索空間，提高問題的求解效率，具有良好的實用性。

技術領域

本發明涉及圖數據約束求解技術領域，具體涉及一種基于對稱破壞的子圖同構約束求解方法。

背景技術

隨著大數據時代的到來，來自互聯網及生活中的海量多源異構數據正以前所未有的速度產生并累積，這些數據之間存在著緊密的關聯性，如何對其進行有效地分析和挖掘是目前學術界面臨的嚴峻挑戰和重要機遇。圖作為表示數據之間關系的基本結構，在許多領域有著廣泛應用，生活中的很多問題都可以轉化為一個基于圖的問題，并且使用圖上的相關理論和算法進行解決。其中，圖模式匹配技術是實現圖數據上高效查詢的重要手段，在生物信息、社交網絡等領域有著重要的應用價值。

在實際問題中，對圖數據進行高效、準確的匹配查詢仍然面臨很多難題，尤其是在時間復雜度和空間復雜度上仍然有待提高。為了有效的解決圖匹配問題，很多研究者采用了約束滿足問題(Constraint Satisfaction Problem，CSP)的基本思想，將圖匹配問題直接轉化為一個約束滿足問題的模型，通過對CSP模型的分析和求解達到解決圖匹配問題的目的。約束滿足問題作為人工智能和計算機科學領域中的大量復雜問題的一個通用的求解范例，目的是找到滿足所有約束的各變量的一個或多個賦值。迄今，對CSP算法的研究已經很廣泛深入，且有很多較成熟的有效算法，但是由于約束滿足問題通常都是NP難問題，所以在求解過程中將不可避免的受到組合復雜性的制約。在將子圖同構刻畫成CSP模型時，由于圖的結構特點決定其包含大量對稱結構，而這些對稱結構將會在搜索中引發對稱子樹，在求解過程中，若當前匹配成功，那么所有對稱子樹仍要一一例舉，最終求得的解中，將會產生大量同一種解的不同變體，這樣是浪費時間和空間的。

發明內容

本發明針對現有子圖同構問題求解的過程不可避免的受到組合復雜性的制約的問題，提供一種基于對稱破壞的子圖同構約束求解方法。

為解決上述問題，本發明是通過以下技術方案實現的：

一種基于對稱破壞的子圖同構約束求解方法，具體包括步驟如下：

步驟1、模式圖的自同構節點檢測，即：

步驟1.1、按節點的度，將模式圖的上層分區節點和下層分區節點各劃分到不同的單元中，其中度相同的節點劃分為同一單元；此時上層分區的單元數和下層分區的單元數均為n，具有相同度節點的上層分區單元與對應的下層分區單元具有相同的標記；i∈1，2，…，n；

步驟1.2、當上層分區單元A_i內的節點數量大于1時，將上層分區單元A_i內的每個節點依次與對應下層分區單元B_i內的所有節點進行組合配對，并逐一判斷每組配對的節點是否屬于同一映射集合：

若當前配對的節點屬于同一映射集合時，則對下一組配對的節點進行判斷；

否則，分別將當前配對的節點中，原屬于上層分區單元A_i的節點放入新建的上層分區單元A_n+i中，原屬于下層分區單元B_i的節點放入新建的下層分區單元B_n+i中；