基于社區(qū)結構的快速子圖匹配方法
1.痛點問題
隨著圖在各領域的廣泛應用,對圖上相關高效查詢方法的需求也與日俱增,特別是在社交網絡、金融、電商、安全和航天等眾多領域具有重要作用的子圖匹配查詢。
然而,現(xiàn)有子圖匹配方法在實際使用中速度均較慢,當數(shù)據(jù)量較大時,現(xiàn)有方法的時間開銷巨大,難以滿足具體匹配過程中的時效性需求。同時,這些方法沒有充分利用圖數(shù)據(jù)的本質結構特點進行剪枝,在運行效率上仍有較大的改進空間。
2.解決方案
本技術提出一種基于社區(qū)結構的子圖匹配方法,基于社區(qū)結構在匹配過程中進行剪枝從而加快子圖匹配的速度。流程圖如圖1所示。
圖1 本技術子圖匹配計算流程
首先,本技術識別數(shù)據(jù)圖中的社區(qū)結構,將數(shù)據(jù)圖劃分為若干“內部緊密關聯(lián)、相互之間連接松散”的社區(qū)。接著,基于社區(qū)結構,提出三種優(yōu)化策略對子圖匹配過程進行優(yōu)化,并實現(xiàn)了相關技術。
具體地,這三種優(yōu)化策略包括兩階段破對稱策略、基于社區(qū)路徑的剪枝策略和基于社區(qū)結構的邊界剪枝策略。其中,兩階段破對稱策略利用模式圖中的自同構映射,根據(jù)已得到的若干匹配結果推斷出新的匹配結果,從而減少匹配過程中的計算量;基于社區(qū)路徑的剪枝策略根據(jù)數(shù)據(jù)圖中的跨社區(qū)的路徑構建索引,在匹配過程中提前發(fā)現(xiàn)無法產生匹配結果的匹配嘗試,減少匹配開銷;基于社區(qū)結構的邊界剪枝則考慮各社區(qū)的邊界節(jié)點,即那些和其他社區(qū)的節(jié)點間有邊關聯(lián)的節(jié)點,根據(jù)邊界節(jié)點的鄰居情況進行剪枝,減小搜索空間,加快子圖匹配速度。
基于上述優(yōu)化策略,本技術提出的基于社區(qū)結構的高效子圖匹配方法能根據(jù)給出的數(shù)據(jù)圖和模式圖快速返回子圖匹配結果。該技術可以作為模塊嵌入金融、電商和航天等已有軟件系統(tǒng),也可作為單獨軟件工具并支持二次開發(fā)。
3.合作需求
1)應用場景:在圖數(shù)據(jù)中快速查找滿足某種特定結構的子圖結構,進而作為查詢結果返回或用于后續(xù)深入分析。可用于包括但不限于社交網絡、金融、電商、安全和航天等眾多場景中。
2)資源對接:對圖查詢、圖分析有需求且對其高效性有要求的個人、單位和企業(yè)等。
清華大學
2022-12-05