基于主結(jié)構(gòu)的圖相似查詢算法研究.pdf

1、隨著現(xiàn)代化信息技術(shù)的迅猛發(fā)展，圖己被廣泛應(yīng)用于很多領(lǐng)域，如生物化學、社會網(wǎng)絡(luò)、模式識別、語義網(wǎng)等。目前，圖查詢內(nèi)容主要包括子圖查詢、超圖查詢、圖的相似性查詢等。本文重點研究圖的相似性查詢問題。
　　在無線傳感器網(wǎng)絡(luò)事件檢測中，傳感器節(jié)點的數(shù)據(jù)具有時空相關(guān)性，若將節(jié)點的數(shù)據(jù)視為頂點，數(shù)據(jù)之間的相關(guān)性看作邊，就可以對事件進行圖建模。以累積的事件圖集建立數(shù)據(jù)庫，傳感器網(wǎng)絡(luò)的復雜事件檢測就可視為集合類圖數(shù)據(jù)的相似查詢問題。目前，圖相似性度

2、量方法主要有最大公共子圖(MCS)和圖編輯距離(GED)兩種，然而它們由于受圖規(guī)模因素影響較大，并不能有效適用于此類圖數(shù)據(jù)的相似查詢，本文提出了一種基于主結(jié)構(gòu)的圖相似性度量手段，主結(jié)構(gòu)代表了圖的主要特征。提出一種基于主結(jié)構(gòu)的圖相似查詢算法，算法在定義圖的基本結(jié)構(gòu)的基礎(chǔ)上，提出主結(jié)構(gòu)的概念，通過對圖及其剩余圖提取主結(jié)構(gòu)將圖轉(zhuǎn)化為主結(jié)構(gòu)序列，由此，圖的相似性查詢問題被轉(zhuǎn)化為序列之間的相似性查詢。
　　論文提出主結(jié)構(gòu)三種度量方式，基于剩

3、余圖的連通分量、剩余圖的連通度以及剩余圖的規(guī)模。針對主結(jié)構(gòu)序列相似性比較，提出三種序列匹配算法，基于權(quán)重的最長公共子序列，基于權(quán)重的序列編輯距離與基于權(quán)重的層次匹配。實驗表明，相對無權(quán)值的序列匹配方式，本文提出的帶權(quán)重的序列匹配算法較好地體現(xiàn)了序列的相似性。另外，針對主結(jié)構(gòu)序列的層次匹配方式，為序列數(shù)據(jù)庫建立了索引結(jié)構(gòu)，減少了查詢響應(yīng)時間。
　　實驗表明，針對事件檢測圖建模的數(shù)據(jù)，本文提出的基于主結(jié)構(gòu)的圖相似性查詢算法，與基于GE