圖查詢的應用越來越廣泛,其中近似子圖匹配是核心技術之一.但是大規(guī)模圖數(shù)據(jù)中噪音的存在對近似子圖匹配精確度影響較大,為進一步提高近似子圖匹配算法的魯棒性和實時性,提出一種基于卡方統(tǒng)計的近似子圖匹配改進算法.在算法預處理階段,利用統(tǒng)一鄰居隨機游走距離和高斯影響函數(shù)將目標圖劃分,使得劃分后的子圖在拓撲結構和標簽屬性之間達到最佳平衡.在算法匹配階段,使用卡方統(tǒng)計量捕獲的統(tǒng)計顯著性來表征近似子圖匹配結構相似度,再結合權重系數(shù)α調(diào)整結構相似度和標簽相似度所占比重,其中統(tǒng)計顯著性模型能夠充分考慮背景結構和頂點鄰域中的標簽分布,有效處理部分標簽和結構失配,從而得到最佳匹配子圖.真實數(shù)據(jù)集中的實驗結果表明,該算法效果較好,運算效率較高,可以應用于Top-k近似子圖匹配.

【文章頁數(shù)】：7 頁

【文章目錄】：
1 引言
2 知識背景
3 IMVELSET算法
    3.1 預處理
        3.1.1 圖分區(qū)算法
        3.1.2 創(chuàng)建索引列表
    3.2 統(tǒng)計顯著性計算
        3.2.1 節(jié)點對的構建
        3.2.2 統(tǒng)計顯著性計算
            (1)標簽元組的產(chǎn)生
            (2)標簽重疊度的計算
            (3)期望標簽重疊度
            (4)卡方值的計算
    3.3 近似匹配結果的產(chǎn)生
4 實驗結果及分析
    4.1 實驗準備
    4.2 精確度和運算效率指標的評測實驗及分析
    4.3 參數(shù)的影響
5 結束語



本文編號：3816327