[發明專利]一種基于特征圖的非精確子圖匹配方法

在審

• 申請號: 201710128034.2
• 申請日: 2017-03-06
• 公開（公告）號: CN106997377A
• 公開（公告）日: 2017-08-01
• 發明（設計）人: 馬廷淮;于思洋;唐美麗;曹杰
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 江蘇愛信律師事務所32241
• 代理人: 唐小紅

1.一種基于特征圖的非精確子圖匹配方法，其特征在于，包括以下步驟：

步驟1)，根據結點標簽得到查詢圖中每個點關于數據圖的候選點集；

步驟2)，根據步驟1)對查詢圖中的每個點及其匹配候選集建立關于特征圖的索引；

步驟3)，根據步驟2)計算每個點的特征圖向量R；

步驟4)，根據步驟3)，計算每個點與它的候選點集中的點兩兩之間的匹配開銷，通過迭代求得匹配映射，迭代的結束條件是兩次匹配之間的差異小于規定的閾值。

2.如權利要求1所述的方法，其特征在于，步驟1)查找查詢圖Q中每個點v關于數據圖G的候選匹配點集C，其中v的候選匹配點集C是數據圖G中與v標簽相同的點組成的集合。

3.如權利要求1所述的方法，其特征在于，步驟2)將2-4個點組成的完全連接圖作為特征圖，每個點在這些完全連接圖中15種不同的位置，計算查詢圖Q中的每個點v以及它在數據圖G上的匹配候選集中的每一個點u在這15個位置出現的次數作為索引保存。

4.如權利要求1所述的方法，其特征在于，步驟3)建立特征圖向量，根據公式計算查詢圖Q中的點v與它的匹配候選集中的某一點u在每個位置i處的差異值，其中Q_fi表示查詢圖Q中的點v在i位置出現的次數，G_fi表示v的匹配候選集中的一點u在i位置出現的次數。

5.如權利要求1所述的方法，其特征在于，步驟4)根據公式計算Q中的點v與它的匹配候選集中的某一點u的匹配開銷，選擇候選集中差異值最小的點作為初始匹配映射，公式中α_i表示第i個位置在所有的位置中所占重要程度的權重，是一個常量；根據公式計算第i+1次迭代中Q中的點v與它的匹配候選集中的某一點u的匹配開銷，其中cost(v,u)ⁱ表示第i次迭代的匹配開銷，cost(v',φ(v'))ⁱ表示v的鄰居結點v’第i次迭代時最小的匹配開銷；選擇候選集中差異值最小的點作為該次迭代的匹配映射，直到兩次匹配之間的差異小于規定的閾值停止迭代，得到最終的匹配結果。