基于主結構的圖相似查詢算法研究.pdf

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

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

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