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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2624204