高效子圖匹配算法研究.pdf

1、圖作為一種數(shù)據(jù)結構能夠簡潔有力地刻畫出普遍事物間的聯(lián)系，因此基于圖的數(shù)據(jù)挖掘與管理技術無論在學術研究還是工業(yè)應用上都享有重要的地位。這其中最基本的任務是如何在圖數(shù)據(jù)集中找到給定的查詢圖，也就是子圖匹配問題。對于正在蓬勃發(fā)展的圖數(shù)據(jù)庫，生物信息學和社會網(wǎng)絡分析等領域而言，一個高效的子圖匹配算法的重要性不言而喻。子圖匹配的數(shù)學基礎是圖論中的經(jīng)典問題子圖同構，一個著名的NP問題?？上攵?，設計高效的子圖匹配算法面臨著相當巨大大的挑戰(zhàn)。目前，子

2、圖匹配算法的研究工作主要有兩個問題。其一是針對一張邊數(shù)較多的圖如何進行有效的過濾，其二是如何選擇頂點搜索順序來加快子圖同構搜索的速度。特別是后者是近年來子圖匹配研究的焦點。
　　針對上述情況，本文提出了一個多段圖模型(MGSM)用于指導頂點搜索順序的選擇。根據(jù)這個模型得到優(yōu)化搜索順序的兩個關鍵點:特征選擇和代價（導出子圖）估計。其中，第一個關鍵點與過濾技術緊密相關，以此出發(fā)可以對以往算法的過濾技術進行改進。針對第二個關鍵點，本文提

3、出了一種稱為偽樹估計的的代價估計方法。基于上述工作，本文設計了一個精確子圖匹配算法Tps(Three-Phase-Searching)。實驗結果表明:Tps算法不僅具有顯著的高效性，同時優(yōu)化的頂點搜索順序對圖過濾過程和驗證過程同樣有效。另外，本文在對精確與非精確匹配兩個領域的重要算法進行分析的基礎上，提出了一個高效的候選集過濾算法HLMA。實驗證明，該算法既能滿足盡量縮小候選集的過濾要求，又能兼顧過濾的時間效率。
　　本文所描述的

4、工作具有一定的創(chuàng)新性。其中，在與目前公認的最快圖匹配算法TurboISO所進行的對比實驗中，Tps算法具有明顯的執(zhí)行效率優(yōu)勢。更重要的是Tps算法的效率優(yōu)勢來自于更合理的理論基礎，即本文所提出的MSGM模型可以指出何為最優(yōu)的頂點搜索順序。由此導出的兩大關鍵點可以從理論上解釋目前若干主要算法的相似相異之處，從而得出與相關對比試驗結果相一致的經(jīng)驗結論。在此基礎上提出的偽樹估計法跳出了前人算法的藩籬，是Tps算法優(yōu)異性能的根基所在?？偠灾?，