單圖中的近似頻繁子圖挖掘算法

竇建凱　林欣　胡文心

摘要：圖數(shù)據(jù)的挖掘工作是數(shù)據(jù)挖掘工作中的重要組成部分，已經(jīng)有許多人在這個領(lǐng)域進行了深入的研究.由于數(shù)據(jù)獲取不可避免噪音數(shù)據(jù)，故在挖掘頻繁圖時考慮近似十分重要.然而許多此前的工作只考慮了子圖間編輯距離（Graph Edit Distance，GED）的絕對值，而沒有考慮子圖間編輯距離與子圖大小的相對關(guān)系.提出了一種在單圖中進行近似頻繁子圖挖掘的新算法，并在計算近似程度時考慮當前子圖的大小.該算法通過對近似頻繁子圖的大小上限進行預測，并通過局部反單調(diào)性進行剪枝，提高了算法的效率.實驗表明，該算法能夠挖掘出傳統(tǒng)算法無法發(fā)現(xiàn)的近似頻繁子圖，且相比對比算法具有更好的時間性能.

關(guān)鍵詞：近似; 圖;頻繁子圖挖掘;剪枝

中圖分類號：TP391.4

文獻標志碼：A

DOI： 10.3969/j.issn.1000-5641. 2019.06.008

0 引言

圖是用來表示數(shù)據(jù)的一種特殊數(shù)據(jù)結(jié)構(gòu)，它不僅可以用來表示實體本身的性質(zhì)，同時還可以用來表示實體之間的關(guān)系.圖的這種特點使得圖在多種領(lǐng)域具有廣泛應用，如生物信息學、網(wǎng)絡分析等.隨著社會和科學的發(fā)展，實體之間的關(guān)系越來越多樣，實體的數(shù)量越來越多，使用圖結(jié)構(gòu)來表示實體間的關(guān)系顯得尤為高效，從圖數(shù)據(jù)中挖掘?qū)嵱玫哪Ｊ揭囡@得越來越重要.

然而圖結(jié)構(gòu)雖然能高效地表示實體間的關(guān)系，但其結(jié)構(gòu)的復雜性使得從圖中識別頻繁的子圖也變得困難.如在挖掘有用子圖的過程中，同構(gòu)圖的識別問題，就被認為是……