面向不確定圖的子圖相似性全匹配技術(shù)的研究.pdf

1、近年來(lái)，由于統(tǒng)計(jì)誤差或噪聲因素的存在，不確定圖模型吸引了越來(lái)越多的研究者的注意。不確定圖主要應(yīng)用于對(duì)生物網(wǎng)絡(luò)，社交網(wǎng)絡(luò)的建模中。另一方面，作為圖上的基本查詢之一，子圖的相似性全匹配查詢廣泛應(yīng)用于模式識(shí)別、查找用戶群、預(yù)測(cè)蛋白質(zhì)結(jié)構(gòu)等問(wèn)題中。所謂子圖的相似性全匹配查詢，即為給定一個(gè)查詢圖，查找其在一個(gè)大的數(shù)據(jù)圖中的所有的相似性匹配。研究者們?cè)O(shè)計(jì)并實(shí)現(xiàn)了大量的算法來(lái)查找確定圖上的子圖相似性全匹配，然而，對(duì)于不確定圖上的子圖相似性全匹配查詢，

2、并未得到足夠多的重視且遇到了很大的挑戰(zhàn)。
　　針對(duì)上述問(wèn)題，本文對(duì)面向不確定圖的子圖相似性全匹配問(wèn)題進(jìn)行研究。
　　首先，本文考慮查詢圖為確定圖、數(shù)據(jù)圖為不確定圖的情況，提出了不確定圖上確定圖的子圖相似性全匹配查詢，并針對(duì)此問(wèn)題提出了基于生成樹匹配的算法。此外，本文提出了一些優(yōu)化算法以進(jìn)一步提高算法的執(zhí)行效率，例如根據(jù)頂點(diǎn)的標(biāo)簽屬性及鄰居節(jié)點(diǎn)為數(shù)據(jù)圖中的頂點(diǎn)建立索引，基于排列組合的思想對(duì)不確定圖到確定圖之間相似性的計(jì)算模型進(jìn)

3、行轉(zhuǎn)化等等。本文通過(guò)大量實(shí)驗(yàn)驗(yàn)證了所提算法及優(yōu)化算法的有效性。
　　其次，考慮到查詢圖為不確定圖、數(shù)據(jù)圖為確定圖的情況，本文定義了確定圖上不確定圖的子圖相似性全匹配查詢，并提出了有效的算法。此外，在上個(gè)章節(jié)算法的基礎(chǔ)上，本文提出了新的計(jì)算子圖之間相似性的方法，并在此基礎(chǔ)上利用概率限值對(duì)上述過(guò)程進(jìn)行剪枝。大量實(shí)驗(yàn)證明了該算法的有效性。
　　最后，本文考慮查詢圖及數(shù)據(jù)圖均為不確定圖的情況，定義了不確定圖上不確定圖的子圖相似性全匹

4、配問(wèn)題。在總結(jié)上述兩個(gè)算法的基礎(chǔ)上，本文定義了新的計(jì)算兩個(gè)不確定圖之間相似性的模型，并提出了動(dòng)態(tài)產(chǎn)生子結(jié)構(gòu)，利用這些子結(jié)構(gòu)進(jìn)行剪枝的優(yōu)化方法。實(shí)驗(yàn)評(píng)估了本文所提算法的高效性。
　　總之，本文從實(shí)際應(yīng)用中面向不確定圖的子圖相似性全匹配的典型特征和挑戰(zhàn)出發(fā)，針對(duì)不確定圖及子圖相似性匹配的關(guān)鍵技術(shù)展開研究，如基于生成樹的匹配方式、可能世界模型概念等，提供有效的面向不確定圖的子圖相似性全匹配查詢處理方法。本文的研究工作為相關(guān)課題的開展鋪平