【摘要】：頻繁子圖挖掘算法作為圖論研究和算法設(shè)計中的重要問題之一,其旨在尋找圖中頻繁出現(xiàn)的子圖結(jié)構(gòu)。頻繁子圖挖掘已在許多領(lǐng)域得到了廣泛的應(yīng)用,例如在社交網(wǎng)絡(luò)、生物醫(yī)學、信息網(wǎng)絡(luò)等。隨著近些年大數(shù)據(jù)時代的到來,數(shù)據(jù)規(guī)模不斷增加,挖掘數(shù)據(jù)中的有意義的信息變得極為重要,由于頻繁子圖挖掘算法能挖掘出數(shù)據(jù)中頻繁出現(xiàn)的子圖結(jié)構(gòu),對研究和生產(chǎn)帶來了巨大效益。目前由于圖數(shù)據(jù)的頻繁變化,傳統(tǒng)基于靜態(tài)圖的頻繁子圖挖掘算法已不再適用,因此,針對動態(tài)圖的頻繁子圖挖掘算法應(yīng)運而生。本文深入研究了各種頻繁子圖挖掘算法,發(fā)現(xiàn)目前現(xiàn)存的頻繁子圖挖掘算法普遍面向靜態(tài)圖。這些算法需要對數(shù)據(jù)庫進行多次掃描,對于運行時間以及運行空間的要求不高應(yīng)用環(huán)境,算法尚可應(yīng)用。但對于大規(guī)模動態(tài)圖,算法在時間復雜度和空間復雜度上變得不再適用。針對于此,本文針對動態(tài)圖上穩(wěn)定頻繁子圖挖掘問題,提出一種基于模式增長的穩(wěn)定頻繁子圖挖掘算法。算法引入滑動窗口技術(shù),在滑動窗口中保存每一時刻達到的圖結(jié)構(gòu),當窗口中存滿圖結(jié)構(gòu)時,對窗口中現(xiàn)存的圖結(jié)構(gòu)進行頻繁子圖挖掘。算法將對窗口中的圖結(jié)構(gòu)產(chǎn)生一張DS表,根據(jù)DS表對其構(gòu)建一個FP-tree,然后挖掘出所有的頻繁項集。對于不連通的頻繁項集修剪問題,本文提出一種基于頂點的頻繁項集修剪算法,修剪掉不連通的頻繁項集并得到頻繁子圖。對于頻繁子圖穩(wěn)定性判斷問題,本文提出一種基于連通密度的圖穩(wěn)定性判斷方法。方法將圖的穩(wěn)定性判斷方法嵌入到頻繁子圖挖掘的剪枝過程中,在判斷圖的穩(wěn)定性時使用連通密度變化量判斷圖的匹配程度。由于若在各個窗口中挖掘出頻繁子圖是同一子圖,其連通密度不會發(fā)生變化,由此得到動態(tài)圖集中在短時間內(nèi)穩(wěn)定不變的頻繁子圖。通過實驗與其他算法進行對比,證明本文提出的穩(wěn)定頻繁子圖算法的有效性。
【學位授予單位】：遼寧大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：TP311.13;O157.5

【參考文獻】

相關(guān)期刊論文 前7條

1 李亮;陳莉;李華;王珊珊;張敏超;;一種改進的頻繁子圖挖掘算法[J];計算機與應(yīng)用化學;2014年02期

2 于戈;谷峪;鮑玉斌;王志剛;;云計算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù)[J];計算機學報;2011年10期

3 楊路明;劉立新;毛伊敏;謝東;;數(shù)據(jù)流中基于滑動窗口的最大頻繁項集挖掘算法[J];計算機應(yīng)用研究;2010年02期

4 李繼騰;駱志剛;丁凡;田文穎;趙琦;;最大頻繁子圖挖掘算法研究[J];計算機工程與科學;2009年12期

5 鄒兆年;李建中;高宏;張碩;;從不確定圖中挖掘頻繁子圖模式[J];軟件學報;2009年11期

6 唐懿芳;穆志純;張師超;鐘達夫;;挖掘數(shù)據(jù)流頻繁模式的相關(guān)技術(shù)和算法研究綜述[J];計算機工程與應(yīng)用;2009年26期

7 劉學軍;徐宏炳;董逸生;錢江波;王永利;;基于滑動窗口的數(shù)據(jù)流閉合頻繁模式的挖掘[J];計算機研究與發(fā)展;2006年10期

相關(guān)博士學位論文 前2條

1 楊雅君;動態(tài)圖數(shù)據(jù)挖掘與查詢算法的研究[D];哈爾濱工業(yè)大學;2013年

2 曹永昌;圖的穩(wěn)定性的相關(guān)研究[D];中國科學技術(shù)大學;2009年

相關(guān)碩士學位論文 前1條

1 齊彩霞;基于圖編輯距離的圖匹配算法研究[D];西安建筑科技大學;2013年

，

本文編號：2624204