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

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

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

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

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