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

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

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

3、出了一種稱為偽樹估計(jì)的的代價(jià)估計(jì)方法?；谏鲜龉ぷ?，本文設(shè)計(jì)了一個(gè)精確子圖匹配算法Tps(Three-Phase-Searching)。實(shí)驗(yàn)結(jié)果表明:Tps算法不僅具有顯著的高效性，同時(shí)優(yōu)化的頂點(diǎn)搜索順序?qū)D過濾過程和驗(yàn)證過程同樣有效。另外，本文在對(duì)精確與非精確匹配兩個(gè)領(lǐng)域的重要算法進(jìn)行分析的基礎(chǔ)上，提出了一個(gè)高效的候選集過濾算法HLMA。實(shí)驗(yàn)證明，該算法既能滿足盡量縮小候選集的過濾要求，又能兼顧過濾的時(shí)間效率。
　　本文所描述的

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