圖數(shù)據(jù)管理中最小唯一誘導(dǎo)子圖查詢研究.pdf

1、圖是計(jì)算機(jī)科學(xué)中最重要的數(shù)據(jù)結(jié)構(gòu)之一。圖不僅關(guān)注數(shù)據(jù)對象本身的屬性，還關(guān)注數(shù)據(jù)對象之間的相互作用關(guān)系，可用于描述復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，例如亞馬遜商品網(wǎng)絡(luò)、FACEBOOK社交網(wǎng)絡(luò)以及生物的蛋白質(zhì)網(wǎng)絡(luò)，等等。近年來，圖數(shù)據(jù)得到了學(xué)術(shù)界的廣泛關(guān)注和深入研究，取得了大批研究成果。隨著圖數(shù)據(jù)量的不斷增大，如何有效地回答圖數(shù)據(jù)中的各種查詢是圖數(shù)據(jù)管理研究中最核心的問題。
　　本文提出了一種新的圖查詢需求：給定一個查詢頂點(diǎn)，返回圖中包含該頂點(diǎn)的一個

2、合適的子圖，返回的子圖不能過小以防無法看出該頂點(diǎn)鄰域和其他頂點(diǎn)鄰域的區(qū)別，返回的子圖也不能過大以防用戶被返回的信息淹沒。在這種需求驅(qū)動下，本文提出了圖數(shù)據(jù)中的最小唯一誘導(dǎo)子圖（Mininal Unique Induced Subgraph，簡寫為MUIS）查詢。MUIS查詢是指給定查詢頂點(diǎn)，在單圖或圖集中查詢包含該頂點(diǎn)的頂點(diǎn)數(shù)最少的唯一誘導(dǎo)子圖。MUIS查詢?yōu)閳D數(shù)據(jù)管理提供了新的數(shù)據(jù)訪問和使用手段。MUIS查詢不僅可以挖掘頂點(diǎn)鄰域的特殊

3、結(jié)構(gòu)，還可以用于頂點(diǎn)的可視化展示以及探索頂點(diǎn)的性質(zhì)。
　　本文給出了MUIS的形式化定義、探索了MUIS的性質(zhì)并給出了MUIS的編碼方法。提出了過濾-驗(yàn)證的兩階段MUIS查詢求解框架，在過濾階段通過對誘導(dǎo)子圖空間進(jìn)行搜索和剪枝產(chǎn)生 MUIS候選集，在驗(yàn)證階段使用子圖同構(gòu)算法檢驗(yàn)MUIS候選集中的誘導(dǎo)子圖是否唯一。本文提出了基于查詢點(diǎn)的廣度優(yōu)先分層搜索策略保證盡早求得頂點(diǎn)數(shù)最少的唯一誘導(dǎo)子圖。在單圖中，提出了基于已匹配點(diǎn)的剪枝策略減

4、少子圖同構(gòu)測試次數(shù)。在圖集中，除了使用基于已匹配點(diǎn)的剪枝策略，還加入了利用圖的匹配順序的剪枝策略，進(jìn)一步提高求解效率。在同構(gòu)測試算法上，均采用了基于查詢點(diǎn)的改進(jìn)VF2算法，該算法不僅優(yōu)化了頂點(diǎn)的匹配順序，還優(yōu)化了算法實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，從而提高了同構(gòu)測試效率。
　　在實(shí)驗(yàn)階段，在單圖和圖集中，分別驗(yàn)證了MUIS查詢的基礎(chǔ)算法和改進(jìn)算法的有效性并對比了算法的性能。本文提出了平均同構(gòu)時(shí)間和調(diào)用遞歸函數(shù)次數(shù)兩個性能評價(jià)標(biāo)準(zhǔn)，使用真實(shí)數(shù)據(jù)集和