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

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

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

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