（計(jì)算機(jī)軟件與理論專業(yè)論文）基于演化算法的連通子圖挖掘方法研究.pdf

中國(guó)科學(xué)技術(shù)人學(xué)碩士學(xué)位論文摘要 摘要 隨著數(shù)據(jù)挖掘研究的深入，越來(lái)越多的問(wèn)題呈現(xiàn)在我們面前，也提出了更高 的要求。當(dāng)前，復(fù)雜類型數(shù)據(jù)的挖掘需求上升，專家學(xué)者開(kāi)始關(guān)注這方面的新應(yīng) 用和理論研究，并試圖利用結(jié)構(gòu)化數(shù)據(jù)挖掘方面的經(jīng)驗(yàn)和方法論來(lái)幫助解決新問(wèn) 題。而連通子圖挖掘問(wèn)題就是本文所致力研究的問(wèn)題。 本文主要研究了連通子圖挖掘問(wèn)題和多信息連通子圖挖掘問(wèn)題。連通子 圖發(fā)現(xiàn)問(wèn)題是在一個(gè)很大的圖中尋找一個(gè)較小的子圖來(lái)表現(xiàn)幾個(gè)給定節(jié)點(diǎn)在圖 中的關(guān)系的問(wèn)題。多信息連通子圖挖掘問(wèn)題是在一個(gè)邊有多種類型的圖中尋找連 通幾個(gè)特定結(jié)點(diǎn)的，能夠滿足問(wèn)題約束的連通子圖的問(wèn)題。本文的主要工作和特 色如下： 1 本文提出了一個(gè)新的解決- 連通子圖挖掘問(wèn)題的方法。首先分析了問(wèn)題 并定義了一個(gè)評(píng)價(jià)函數(shù)來(lái)評(píng)價(jià)一個(gè)子圖表現(xiàn)個(gè)給定節(jié)點(diǎn)之間關(guān)系的好壞。同 時(shí)設(shè)計(jì)了一個(gè)特殊的u t m 編碼來(lái)表示一個(gè)確定結(jié)點(diǎn)數(shù)的圖的拓?fù)浣Y(jié)構(gòu)。使用 u t m 編碼能夠避免在進(jìn)化過(guò)程中多余的編碼步驟，能夠減小算法的時(shí)間和空間 消耗。在u t m 編碼和評(píng)價(jià)函數(shù)的基礎(chǔ)上，設(shè)計(jì)了一個(gè)演化算法來(lái)對(duì)圖的拓?fù)浣Y(jié) 構(gòu)進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果顯示該算法能夠有效地在不同類型的網(wǎng)絡(luò)上發(fā)現(xiàn)連通子 圖。 2 在連通子圖挖掘問(wèn)題之后，本文針對(duì)多信息連通子圖發(fā)現(xiàn)問(wèn)題的特 點(diǎn)，提出了一個(gè)通用的進(jìn)化算法。設(shè)計(jì)了一種表示多信息子圖拓?fù)浣Y(jié)構(gòu)的特殊編 碼多信息子圖編碼m s c 。使用m s c 編碼能夠很好的表示多信息連通子圖， 這個(gè)編碼能夠在進(jìn)化過(guò)程中能夠減少時(shí)間和空i 旬的消耗。同時(shí)在真實(shí)數(shù)據(jù)上的實(shí) 驗(yàn)結(jié)果顯示該算法是有效的。 3 在前面兩個(gè)算法的基礎(chǔ)上，將連通子圖挖掘問(wèn)題與對(duì)象層次的搜索問(wèn)題 相結(jié)合，能夠解決對(duì)象層次的查詢項(xiàng)擴(kuò)展問(wèn)題。對(duì)于算法的兩個(gè)部分使用了不同 的快速優(yōu)化策略。對(duì)于候選子圖算法，計(jì)算量最大的部分可以提前預(yù)處理并且存 儲(chǔ)下來(lái)，在算法的過(guò)程中只需要執(zhí)行簡(jiǎn)單的計(jì)算，無(wú)須多次遍歷原始圖。對(duì)于進(jìn) 化算法，使用不同的算子和參數(shù)設(shè)置能夠使算法收斂更快，也能更好的避免算法 陷入局部最優(yōu)解。 關(guān)鍵詞：圖挖掘，連通子圖，演化算法，對(duì)象層次的搜索 中國(guó)科學(xué)技術(shù)大學(xué)碩壬學(xué)位論文 a b s t r a c t w i t ht h ep r o g r e s so fd a t am i n i n gt e c h n i q u e s ，m o r ea n dm o r eq u e s t i o n sh a v e b e e n p r e s e n t e d t h ed e m a n do fm i n i n go nc o m p l e xd a t ai sr i s i n gn o w e x p e r t sh a v ep a i d a t t e n t i o nt ot h e s ef i e l d sa n dt r i e dt os o l v et h ep r o b l e m sb yv i r t u eo ft h ee x p e r i e n c eo f s t r u c t u r e dd a t am i n i n g i nt h i sp a p e r , w ed ot h er e s e a r c ho nc o n n e c t i o ns u b g r a p h d i s c o v e r yp r o b l e m t h i si sm a i n l yf o c u so i lt h ep r o b l e mo fn c o n n e c t i o ns u b g r a p hm i n i n ga n dt h e p r o b l e mo fm u l t i i n f o r m a t i o ns u b g r a p hm i n i n g n c o n n e c t i o ns u b g r a p hd i s c o v e r y p r o b l e mi sa i mt of i n das m a l ls u b g r a p hi nal a r g eg r a p ht or e p r e s e n tt h ec o n n e c t i o n r e l a t i o n s h i pa m o n gs e v e r a lg i v e n n o d e s m u l t i i n f o r m a t i o nc o n n e c t i o ns u b g r a p h m i n i n gp r o b l e mi s t of i n dac o n n e c t i o ns u b g r a p ha m o n gs e v e r a lg i v e nn o d e si na g r a p hw h i c hc o n t a i n sd i f f e r e n tk i n d so fe d g e s t h em a j o rt a s ka n di n n o v a t i o na r e ： 1 i nt h i sp a p e r , w ep r o v i d ean o v e ls o l u t i o non c o n n e c t i o ns u b g r a p hd i s c o v e r y p r o b l e m a tf i r s t ，w ea n a l y z et h i sp r o b l e ma n dd e s i g naf l i n c t i o n t om e a s u r et h e g o o d n e s so f t h ea b i l i t yo fas u b g r a p hc a p t u r et h er e l a t i o n s h i pa m o n gng i v e nn o d e s w ea l s od e s i g nas p e c i a lu t mc o d et or e p r e s e n tt h et o p o l o g yo fag r a p ho fc e r t a i n n u m b e ro fn o d e s u s i n gt h eu t mc o d ec a l lp r e v e n tt h er e d u n d a n te n c o d e - p r o c e s s d u r i n gt h ee v o l u t i o na n dc a n r e d u c et h et i m ec o s ta n ds p a c ec o s t b a s e do nt h eu t m c o d ea n dt h ee v a l u a t ef u n c t i o n ，w eu s ea ne v o l u t i o na l g o r i t h mt oe v o l v et h et o p o l o g y o ft h es u b g r a p h t h er e s u l t so ft h ee x p e r i m e n ts h o wt h a tt h ea l g o r i t h mc a nf i n d c o n n e c t i o ns u b g r a p ho nd i f f e r e n tt y p e so f n e t w o r k s 2 a f t e rt h en c o n n e c t i o ns u b g r a p hd i s c o v e r y p r o b l e m ，a c c o r d i n gt ot h es p e c i a l p r o p e r t i e so ft h em u l t i i n f o r m a t i o nc o n n e c t i o ns u b g r a p hm i n i n gp r o b l e mw ep r o v i d e ac o m m o ne v o l u t i o na l g o r i t h mt os o l v et h ep r o b l e m w ed e s i g na n o t h e rs p e c i a lc o d e ， m u l t i i n f o r m a t i o ns u b g r a p hc o d e ，m s ct or e p r e s e n t t h e t o p o l o g y o ft h e m u l t i i n f o m a a t i o ns u b g r a p h u s i n gt h em s cc o d ec a nr e p r e s e n tt h et o p o l o g yo ft h e g r a p ha n dc a n a l s og a v et h et i m ea n ds p a c ec o s td u r i n gt h ee v o l u t i o nt h er e s u l t so f t h ee x p e r i m e n to nt h er e a ln e t w o r ks h o wt h a tt h ea l g o r i t h mi se f f e c t i v e 3 ，b a s e do nt h et w oa l g o r i t h m sm e n t i o n e di np r e v i o u ss e c t i o n ，w ec o m b i n et h e c o n n e c t i o ns u b g r a p hm i n i n gp r o b l e mw i t ht h eo b j e c tl e v e ls e a r c hp r o b e mt o g e t h e r a n dw ec a ns o l v et h ep r o b l e mo fm u l t i - o b j e c te x p a n s i o n t oo p t i m i z et h ea l g o r i t h m ， w e u s i n gd i f f e r e n ts t r a t e g yo nd i f f e r e n ts t e po f t h ea l g o r i t h m k e y w o r d s ：g r a p hm i n i n g ，c o n n e c t i o ns u b g r a p h ，e v o l u t i o na l g o r i t h m ，o b j e c tl e v e l s e a r c h 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)位論文相關(guān)聲明 本人聲明所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下進(jìn)行研究 工作所取得的成果。除已特別加以標(biāo)注和致謝的地方外，論文中 不包含任何他人已經(jīng)發(fā)表或撰寫過(guò)的研究成果。與我一同工作的 同志對(duì)本研究所做的貢獻(xiàn)均已在論文中作了明確的說(shuō)明。 本人授權(quán)中國(guó)科學(xué)技術(shù)大學(xué)擁有學(xué)位論文的部分使用權(quán)， 即：學(xué)校有權(quán)按有關(guān)規(guī)定向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印 件和電子版，允許論文被查閱或借閱，可以將學(xué)位論文編入有關(guān) 數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、 匯編學(xué)位論文。 保密的學(xué)位論文在解密后也遵守此規(guī)定。 作者簽名： 鞠弛 z 秒p 7 牽月1 日 中國(guó)科學(xué)技術(shù)大學(xué)碩j ：學(xué)位論文第l 章緒論 1 1 選題背景 1 1 1 子圖挖掘 第1 章緒論 自從2 0 世紀(jì)9 0 年代以來(lái)，數(shù)據(jù)挖掘的研究己經(jīng)取得了巨大的進(jìn)展，而且相 關(guān)技術(shù)正在被各應(yīng)用領(lǐng)域的專家所關(guān)注。在商業(yè)領(lǐng)域，市場(chǎng)分析能幫助企業(yè)家掌 握市場(chǎng)動(dòng)態(tài)和用戶需求。及時(shí)準(zhǔn)確地描述和概括市場(chǎng)行為是成功的市場(chǎng)分析的關(guān) 鍵?！百?gòu)物籃”分析就是借助于關(guān)聯(lián)規(guī)則挖掘技術(shù)進(jìn)行市場(chǎng)分析的最經(jīng)典的案例。 在虛擬網(wǎng)絡(luò)環(huán)境中，分析用戶行為的變化是非常困難的。借助于數(shù)據(jù)挖掘技術(shù)， 如網(wǎng)絡(luò)開(kāi)志挖掘等，可以在一定程度上幫助網(wǎng)絡(luò)管理員對(duì)網(wǎng)站進(jìn)行管理。在) 。訌l 數(shù)據(jù)索引方面，同樣可以利用頻繁模式挖掘技術(shù)發(fā)現(xiàn)x m l 查詢模式樹(shù)，而這些 模式樹(shù)可以用來(lái)索引x i v l l 數(shù)據(jù)，并提高x m l 數(shù)據(jù)的查詢效率。 以上所述的相關(guān)數(shù)據(jù)挖掘方法，都是建立在簡(jiǎn)單結(jié)構(gòu)或簡(jiǎn)單關(guān)系的數(shù)據(jù)集上 的。在絕大多數(shù)應(yīng)用環(huán)境中，對(duì)象之間或?qū)ο髢?nèi)部的關(guān)系是錯(cuò)綜復(fù)雜的，它們很 難用簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)表述。這就為數(shù)據(jù)挖掘研究提出了新的課題，即挖掘復(fù)雜的 予圖結(jié)構(gòu)數(shù)據(jù)。圖結(jié)構(gòu)是最通用的數(shù)據(jù)結(jié)構(gòu)類型，它可以描述世界萬(wàn)物之間錯(cuò)綜 復(fù)雜的聯(lián)系。在社會(huì)網(wǎng)絡(luò)分析中，人與人之間、人與物之間的聯(lián)系是復(fù)雜的。通 過(guò)抽象方法，可以將整個(gè)社會(huì)變成個(gè)網(wǎng)絡(luò)拓?fù)鋱D，其中每個(gè)人可以是圖中的節(jié) 點(diǎn)，而人與入之間的聯(lián)系則可以看作為圖中的邊。對(duì)社會(huì)人群的分析，自然就可 以轉(zhuǎn)化為對(duì)社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)的挖掘。在生物技術(shù)領(lǐng)域，生物學(xué)家發(fā)現(xiàn)蛋白質(zhì)基因結(jié) 構(gòu)配位實(shí)驗(yàn)是費(fèi)時(shí)費(fèi)力費(fèi)錢的工作。他們希望引入數(shù)據(jù)挖掘技術(shù)，以減輕結(jié)構(gòu)匹 配實(shí)驗(yàn)的代價(jià)。蛋白質(zhì)結(jié)構(gòu)可以被描述為圖結(jié)構(gòu)，其中的原子是圖中的頂點(diǎn)，而 原子問(wèn)的價(jià)位則是圖中對(duì)應(yīng)的邊。通過(guò)對(duì)蛋白質(zhì)結(jié)構(gòu)圖集的挖掘，可以預(yù)先發(fā)現(xiàn) 蛋白質(zhì)結(jié)構(gòu)之間的內(nèi)在關(guān)系或共享模式。這些共享模式可以反過(guò)來(lái)指導(dǎo)基因配位 實(shí)驗(yàn)，降低實(shí)驗(yàn)的代價(jià)。正是由于這些應(yīng)用的緊迫要求，子圖結(jié)構(gòu)數(shù)據(jù)挖掘的研 究成為目前數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要研究方向。 目前子圖挖掘的工作可以分為兩個(gè)方面：頻繁子圖挖掘和特定拓?fù)渥訄D挖 掘。 1 1 2 復(fù)雜網(wǎng)絡(luò)及社會(huì)網(wǎng)絡(luò) 上世紀(jì)興起的復(fù)雜性科學(xué)及其復(fù)雜性研究，在世紀(jì)之交已經(jīng)引起了國(guó)內(nèi)外的 普遍關(guān)注和廣泛重視。正以銳不可擋之勢(shì)向著眾多學(xué)科和領(lǐng)域，包括自然科學(xué)、 中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第l 章締論 社會(huì)科學(xué)和人文科學(xué)進(jìn)行廣泛的交叉和融合。正如當(dāng)代最富有影響的思想家之一 一史蒂芬霍金( s t e p h e nh a k i n g ) 在2 0 0 0 年所指出的：“我認(rèn)為，下個(gè)世紀(jì)將是 復(fù)雜性的世界( il h i n kt h en e x tc e n t u r yw i l lb et h ec e n t u r yo f e o m p l e x i t y ) ”。從科學(xué) 發(fā)展史來(lái)看，牛頓力學(xué)問(wèn)世以來(lái)，還原論的研究方法主宰了現(xiàn)代科學(xué)中的眾多領(lǐng) 域。該法把系統(tǒng)分解為大量的基本單元，認(rèn)為這些單元的行為及其相互作用遵從 普遍而簡(jiǎn)單的自然法則。該方法雖然取得了巨大的成功，但是它同樣存在極大的 局限性，因?yàn)樗鼉H僅適用于“簡(jiǎn)單系統(tǒng)”，而無(wú)法或根本不適于自然界中大量存 在的“復(fù)雜系統(tǒng)”。大量客觀事實(shí)和科學(xué)論證表明：不能用還原論來(lái)處理復(fù)雜系 統(tǒng)，簡(jiǎn)單地說(shuō)就是1 加1 并不等于2 ；不能用單元的個(gè)體性質(zhì)來(lái)預(yù)言復(fù)雜系統(tǒng)整 體的豐富的行為。隨著2 0 世紀(jì)科學(xué)的巨大進(jìn)步，復(fù)雜性研究正越來(lái)越被人們所 認(rèn)識(shí)，但是它的奧秘還沒(méi)有被完全揭開(kāi)。預(yù)期2 l 世紀(jì)將是復(fù)雜性的世紀(jì)，復(fù)雜性 科學(xué)將成為新世紀(jì)的主導(dǎo)科學(xué)之一，涉及到非常廣泛的學(xué)科，特別是物理科學(xué)、 生命科學(xué)、信息科學(xué)和社會(huì)、經(jīng)濟(jì)科學(xué)等主要領(lǐng)域。當(dāng)前國(guó)際上迅猛發(fā)展的態(tài)勢(shì) 和迫切需要，使它成為新世紀(jì)科學(xué)研究的前沿之一，有著廣闊的應(yīng)用潛力。 由于復(fù)雜性問(wèn)題研究與網(wǎng)絡(luò)的復(fù)雜性關(guān)系有密切聯(lián)系，所以近年來(lái)它們之間 的交叉研究引起了人們的高度重視。我們知道，從數(shù)學(xué)上能夠用一個(gè)圖來(lái)表示一 個(gè)網(wǎng)絡(luò)，復(fù)雜網(wǎng)絡(luò)的理論研究始于2 0 世紀(jì)6 0 年代由著名數(shù)學(xué)家e r d 0 8 和r e n y i 提出的e l l 隨機(jī)圖模型。在此后的近4 0 年暈。該模型一直是研究復(fù)雜網(wǎng)絡(luò)的基本 模型。但是，近年柬復(fù)雜動(dòng)力學(xué)網(wǎng)絡(luò)的研究已經(jīng)突破了該模型，取得了可喜的進(jìn) 展，受到了不同學(xué)科的廣泛關(guān)注。進(jìn)展的主要原因之一是，以還原論和整體論相 結(jié)合為重要特色的復(fù)雜性科學(xué)的興起，促使人們開(kāi)始關(guān)注復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)及 其產(chǎn)生機(jī)理。隨著計(jì)算能力的日益強(qiáng)大，以及學(xué)科之間的相互交叉和不斷融合的 必然趨勢(shì)，目前已經(jīng)開(kāi)始對(duì)復(fù)雜性科學(xué)進(jìn)行交叉研究，從生物體中的大腦到各種 新陳代謝網(wǎng)絡(luò)，從i n t e r n e t 到萬(wàn)維網(wǎng)( w w w ) ，從全球衛(wèi)星通訊網(wǎng)絡(luò)到全球交 通網(wǎng)絡(luò)，從大規(guī)模集成電路到大型電力網(wǎng)絡(luò)，從科研合作網(wǎng)絡(luò)到各種經(jīng)濟(jì)、政治、 社會(huì)關(guān)系網(wǎng)絡(luò)等，可以說(shuō)，人們已經(jīng)生活在一個(gè)充滿著各種各樣的復(fù)雜網(wǎng)絡(luò)的世 界中。近幾年來(lái)，復(fù)雜網(wǎng)絡(luò)的研究j 下滲透到從物理學(xué)到生物學(xué)的眾多不同的學(xué)科， 對(duì)復(fù)雜網(wǎng)絡(luò)的定性特征與定量規(guī)律的深入探索、科學(xué)理解以及可能的應(yīng)用，已成 為網(wǎng)絡(luò)時(shí)代復(fù)雜性科學(xué)研究中一個(gè)極其重要的挑戰(zhàn)性課題。 1 1 3 演化算法 演化算法是美國(guó)m i c h i g a n 大學(xué)的j h h o l l a n d 教授予1 9 7 5 年首先提出的 1 9 】。其基本思想基于d a r w i n 的進(jìn)化論和m e n d e l 的遺傳學(xué)說(shuō)，根據(jù)適者生存、 優(yōu)勝劣汰的進(jìn)化原則，對(duì)可能包含解的種群反復(fù)使用遺傳進(jìn)化的基本操作不斷坐 中國(guó)科學(xué)技術(shù)火學(xué)碩士學(xué)位論文 第l 章締論 成新的種群，使物種不斷進(jìn)化。作為一種全局搜索的工具，演化算法具有簡(jiǎn)單、 通用、自組織性、自適應(yīng)性和本質(zhì)并行性等特性，特別適合處理那些用傳統(tǒng)搜索 方法難以有效解決、甚至無(wú)法解決的問(wèn)題。因此近年來(lái)，基于演化算法的研究成 果在許多領(lǐng)域得到了廣泛的應(yīng)用 一 在對(duì)演化算法的研究上，大致有三種類似的方法：遺傳算法( g e n e t i c a l g o r i t h m ) 及其變種遺傳編程( g e n e t i cp r o g r a m m i n g ) 和學(xué)習(xí)分類器系統(tǒng) ( l e a r n i n g c l a s s i f i e r s y s t e m ) 、演化策略( e v o l u t i o ns t r a t e g y ) 和演化編程 ( e v o l u t i o n a r yp r o g r a m m i n g ) 。本文所研究的演化決策樹(shù)主要是遺傳算法在決策樹(shù) 方法中的應(yīng)用。下面簡(jiǎn)單介紹遺傳算法的相關(guān)內(nèi)容。 標(biāo)準(zhǔn)遺傳算法求解優(yōu)化問(wèn)題的算法框架描述如下： ( 1 ) 醚祝生成一個(gè)韌始種群 ( 2 ) 確定每個(gè)體的適應(yīng)度； ( 3 ) 按選擇機(jī)翩選出父體： ( 4 ) r e p e a t 以概率p c 雜交； 以概率p m 變異： 詩(shī)算令缽逶壹 按選擇機(jī)翻選出父體 u n t i l 終出條件 遺傳算法是一種群體型操作，該操作以種群中的所有個(gè)體為對(duì)象。選擇 ( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和變異( m u t a t i o n ) 是遺傳算法的三個(gè)主要操作 算子，它們構(gòu)成了遺傳操作，使遺傳算法具有了其它傳統(tǒng)方法所沒(méi)有的特性。 遺傳算法中包含了如下5 個(gè)基本要素 2 0 ，2 1 1 ： 參數(shù)編碼 有二進(jìn)制編碼、實(shí)數(shù)編碼和結(jié)構(gòu)化編碼等多種形式。 初始種群的設(shè)定 遺傳算法種群中的個(gè)體一般是隨機(jī)產(chǎn)生的。 適應(yīng)度函數(shù)的設(shè)計(jì) 適應(yīng)度函數(shù)評(píng)估是選擇操作的依據(jù)，適應(yīng)度函數(shù)的設(shè)計(jì)將直接影響到遺傳算 法的性能。一般在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)，會(huì)考慮到算法的關(guān)鍵指標(biāo)，如分類器的分 類準(zhǔn)確度等。 遺傳操作設(shè)計(jì) 標(biāo)準(zhǔn)的遺傳算法的遺傳操作包括以下三個(gè)基本遺傳算子：選擇、交叉和變異。 遺傳算法中，交叉算子因其全局搜索能力而作為主要算予，變異算子因其局 生國(guó)科學(xué)技術(shù)叁堂塑! ：學(xué)位論文第l 章緒論 部搜索能力而作為輔助算子。遺傳算法通過(guò)這一對(duì)相互配合又相互競(jìng)爭(zhēng)的操作而 使其具備兼顧全局和局部的均衡搜索能力。如何有效的配合適用交叉和變異操 作，是目前遺傳算法的一個(gè)重要研究?jī)?nèi)容。 控制參數(shù)設(shè)定 主要是指種群大小、演化代數(shù)和遺傳操作的概率等。 1 ，2 本文研究工作和內(nèi)容安排 1 2 1 研究工作 本文著重研究了連通子圖挖掘問(wèn)題。主要針對(duì)- 連通子圖挖掘問(wèn)題和多信 息連通子圖挖掘問(wèn)題分別提出了各自的適用算法。為了提高算法的性能，進(jìn)一步 提出了快速的連通子圖挖掘算法。本文的主要研究?jī)?nèi)容如下： ( 一) 本文提出了一個(gè)新的解決- 連通子圖挖掘問(wèn)題的方法。首先分析了問(wèn)題 并定義了一個(gè)評(píng)價(jià)函數(shù)來(lái)評(píng)價(jià)一個(gè)子圖表現(xiàn)個(gè)給定節(jié)點(diǎn)之間關(guān)系的 好壞。同時(shí)設(shè)計(jì)了一個(gè)特殊的u t m 編碼來(lái)表示一個(gè)確定結(jié)點(diǎn)數(shù)的圖的 拓?fù)浣Y(jié)構(gòu)。使用u t m 編碼能夠避免在進(jìn)化過(guò)程中多余的編碼步驟，能 夠減小算法的時(shí)間和空間消耗。在u t m 編碼和評(píng)價(jià)函數(shù)的基礎(chǔ)上，設(shè) 計(jì)了一個(gè)演化算法來(lái)對(duì)圖的拓?fù)浣Y(jié)構(gòu)進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果顯示該算法能 夠有效地在不同類型的網(wǎng)絡(luò)上發(fā)現(xiàn)連通子圖。 ( 二) 針對(duì)多信息連通子圖發(fā)現(xiàn)問(wèn)題。提出了一個(gè)通用的進(jìn)化算法。設(shè)計(jì)了一 種表示多信息子圖拓?fù)浣Y(jié)構(gòu)的特殊編碼多信息子圖編碼m s c 。使 用m s c 編碼能夠很好的表示多信息連通子圖這個(gè)編碼能夠在進(jìn)化過(guò) 程中能夠減少時(shí)間和空間的消耗。我們的算法就通過(guò)改變多信息子圖編 碼來(lái)對(duì)多信息子圖的拓?fù)浣Y(jié)構(gòu)進(jìn)行不斷優(yōu)化，最終得到我們需要的多信 息子圖。同時(shí)在真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果顯示該算法是有效的 ( 三) 在前面兩個(gè)算法的基礎(chǔ)上，將連通子圖挖掘問(wèn)題與對(duì)象層次的搜索問(wèn)題 相結(jié)合，能夠解決對(duì)象層次的查詢項(xiàng)擴(kuò)展問(wèn)題。對(duì)于算法的兩個(gè)部分使 用了不同的快速優(yōu)化策略。對(duì)于候選子圖算法，計(jì)算量最大的部分可以 提前預(yù)處理并且存儲(chǔ)下來(lái)，在算法的過(guò)程中只需要執(zhí)行簡(jiǎn)單的計(jì)算，無(wú) 須多次遍歷原始圖。對(duì)于進(jìn)化算法，使用不同的算子和參數(shù)設(shè)置能夠使 算法收斂更快，也能更好的避免算法陷入局部最優(yōu)解。 1 2 2 內(nèi)容安排 本文一共分為六章，每一章的內(nèi)容如下 中圈科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第1 章緒論 第一章：引言。介紹了本文研究工作的相關(guān)的背景，包括子圖挖掘、復(fù) 雜網(wǎng)絡(luò)和演化算法。 第二章：連通子圖挖掘問(wèn)題。分別介紹了n 連通子圖挖掘問(wèn)題和多信息 連通子圖挖掘問(wèn)題。接著介紹了與連通子圖挖掘問(wèn)題相關(guān)的工作，包括 現(xiàn)有的連通子圖挖掘問(wèn)題的研究工作揖及相關(guān)的子圖挖掘和數(shù)據(jù)挖掘 相關(guān)工作。 第三章：n 連通子圖挖掘問(wèn)題。詳細(xì)分析了n 連通子圖挖掘問(wèn)題的定義 以及特定，針對(duì)這些特點(diǎn)提出了問(wèn)題結(jié)果的評(píng)價(jià)方法，并且提出了u t m 編碼和算法。算法分為兩步，第一步生成候選子圖，第二步用進(jìn)化算法 得到結(jié)果子圈。最后在兩個(gè)實(shí)際的社會(huì)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)。 第四章：多信息連通子圖挖掘問(wèn)題。分析了在多信息條件下的連通子圖 問(wèn)題所面臨的新問(wèn)題。然后針對(duì)問(wèn)題特點(diǎn)提出了m s c 編碼和進(jìn)化算法。 通過(guò)在現(xiàn)實(shí)數(shù)據(jù)上的實(shí)驗(yàn)證明了算法的有效性 第五章：連通子圖挖掘與對(duì)象層次的搜索。針對(duì)對(duì)象層次搜索問(wèn)題的特 點(diǎn)，提出利用多信息連通子圖挖掘算法能夠解決對(duì)象層次的多個(gè)對(duì)象的 查詢項(xiàng)擴(kuò)展問(wèn)題。分別分析了算法兩部分的性能特點(diǎn)，先針對(duì)候選予圖 生成算法的性能提出使用部分計(jì)算預(yù)處理的方法進(jìn)行優(yōu)化，然后優(yōu)化了 進(jìn)化算法的算子和參數(shù)設(shè)置，最終得到一個(gè)完整的快速的連通子圖挖掘 算法。 第六章：結(jié)論以及工作展望。總結(jié)了全文，并對(duì)進(jìn)一步的工作進(jìn)行了說(shuō) 明。 ! 里壁掌墊術(shù)搏塑士學(xué)位論文 第2 章連通于圈挖掘問(wèn)題 第2 章連通子圖挖掘問(wèn)題 2 1 連通子圖挖掘問(wèn)題 2 1 1n 連通子圖挖掘問(wèn)題 如今，越來(lái)越多的用大型的網(wǎng)絡(luò)或者圖來(lái)表示的數(shù)據(jù)集得到使用，在網(wǎng)絡(luò)中 尋找一些特殊的結(jié)構(gòu)變得重要并且必要。例如，從人際關(guān)系建模的社會(huì)網(wǎng)絡(luò)中， 我們能找到阿蘭圖靈和莎朗斯通之間的關(guān)系嗎? 阿蘭圖靈是一個(gè)已經(jīng)過(guò)世的著 名科學(xué)家，而莎朗斯通是一位當(dāng)今著名的女演員，他們生活在不同的時(shí)代并且他 們的工作領(lǐng)域是完全不同的。他們之間有什么有趣的關(guān)系嗎? 一個(gè)可行的辦法是首先建立一個(gè)人際關(guān)系網(wǎng)絡(luò)，其中每個(gè)結(jié)點(diǎn)代表一個(gè)入， 每條邊代表兩個(gè)人之間的關(guān)系，每條邊上的權(quán)重代表兩個(gè)人關(guān)系的強(qiáng)弱。用這個(gè) 網(wǎng)絡(luò)我們能夠通過(guò)發(fā)現(xiàn)連接幾個(gè)結(jié)點(diǎn)的子圖來(lái)找出任意幾個(gè)人之間的關(guān)系。所以 這個(gè)子圖應(yīng)該大小合適，并且子圖中的結(jié)點(diǎn)應(yīng)該足夠重要。在這樣的情況下，我 們可以說(shuō)這個(gè)子圖能很好的表現(xiàn)幾個(gè)人之間的關(guān)系。 這個(gè)問(wèn)題的一個(gè)特殊情況就是2 關(guān)鍵結(jié)點(diǎn)連通孑圖發(fā)現(xiàn)問(wèn)題( 2 c s d p ) ，這個(gè) 問(wèn)題已經(jīng)被c f a l i u t s o s 1 等人首先研究。并且如他們?cè)谖墨I(xiàn) 1 】中指出的，有很 少的研究工作直接關(guān)注c s d p 問(wèn)題。c f a l i u t s o s 等人提出了一個(gè)有效的算法來(lái)解 決2 - c s d p ，這個(gè)方法是一個(gè)基于電路分流理論的算法。圖2 1 顯示的是他們算 法的一個(gè)結(jié)果。 圖2 - 1 阿蘭圖靈和莎朗斯通之間的關(guān)系 但是，如果我們希望知道更多人之間的關(guān)系，比如阿蘭圖靈、莎朗斯通和麥 克喬丹之間的關(guān)系，該怎么辦呢? 在這樣的情況下，基于電路分流的方法不再適 用，我們稱這種更復(fù)雜的問(wèn)題叫做月連通子圖問(wèn)題。其中凡是大于2 的數(shù)。這個(gè) 問(wèn)題的形式化定義如下： n 連通子圖發(fā)現(xiàn)問(wèn)題( n - c s d p ) 輸入：一個(gè)無(wú)向邊加權(quán)圖g ，g 中的個(gè)結(jié)點(diǎn)和一個(gè)整數(shù)上限。 輸出：一個(gè)連通子圖凰包含v i ，1 2 ，最多有卜結(jié)點(diǎn)并且能很好地表 喹田科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第2 章連通子圈挖掘問(wèn)壁 現(xiàn)之間的關(guān)系 對(duì)于n - c s d p ，基于電路模擬的方法不再適用，原因是在給定兩個(gè)結(jié)點(diǎn)時(shí)， 我們可以讓一個(gè)結(jié)點(diǎn)作為電路中的正極，一個(gè)作為負(fù)極。但是當(dāng)給定結(jié)點(diǎn)多于兩 個(gè)時(shí)，我們無(wú)法確定第三個(gè)結(jié)點(diǎn)應(yīng)該是正極還是負(fù)極，在這種情況下電路模擬的 方法不再合理。所以我們需要尋找一個(gè)能夠找到表示多個(gè)給定結(jié)點(diǎn)之間關(guān)系子圖 的方法。 連通子圖發(fā)現(xiàn)有很廣泛的應(yīng)用，例如可以用來(lái)發(fā)現(xiàn)因特網(wǎng)上可能泄漏一些 信息( 比如文檔，r a p 3 或者電影) 的網(wǎng)站。類似的，也可以用來(lái)控帝g 傳染病控制。 在其他領(lǐng)域，比如語(yǔ)義搜索和信息檢索以及其他網(wǎng)絡(luò)，例如蛋白質(zhì)網(wǎng)絡(luò)，語(yǔ)言網(wǎng) 絡(luò)和化學(xué)反應(yīng)網(wǎng)絡(luò)，連通子圖能夠找到一些有用的特殊信息。因此尋找這些網(wǎng) 絡(luò)中的特殊子結(jié)構(gòu)的特殊方法也越來(lái)越重要。 在本文中，我們提出了一個(gè)新的解決n - c s d p 的方法。我們首先分析了問(wèn)題 并定義了一個(gè)評(píng)價(jià)函數(shù)來(lái)評(píng)價(jià)一個(gè)子圖表現(xiàn)個(gè)給定節(jié)點(diǎn)之瞄關(guān)系的好壞。同 時(shí)我們?cè)O(shè)計(jì)了一個(gè)特殊的u t m 編碼來(lái)表示一個(gè)確定結(jié)點(diǎn)數(shù)的圖的拓?fù)浣Y(jié)構(gòu)。在 u t m 編碼和評(píng)價(jià)函數(shù)的基礎(chǔ)上，我們?cè)O(shè)計(jì)了個(gè)演化算法來(lái)對(duì)圖的拓?fù)浣Y(jié)構(gòu)進(jìn) 行優(yōu)化。我們的實(shí)驗(yàn)結(jié)果顯示我們的算法能夠有效地在不同類型的網(wǎng)絡(luò)上發(fā)現(xiàn)連 通子圖。 2 1 2 多信息連通子圖挖掘問(wèn)題 在數(shù)據(jù)挖掘領(lǐng)域，針對(duì)圖結(jié)構(gòu)數(shù)據(jù)的挖掘已成為人們關(guān)注的熱點(diǎn)研究問(wèn)題。 已有的圖挖掘算法主要關(guān)注圖的連通性，即圖中結(jié)點(diǎn)之間的關(guān)系一般是單一的， 只考慮是否有邊相連。然而現(xiàn)實(shí)世界中，兩個(gè)實(shí)體之間的關(guān)系是多重的，即一條 邊具有多個(gè)含義，表示實(shí)體之間同時(shí)具有多種不同形式的關(guān)系。本文將結(jié)點(diǎn)之間 存在不同種類關(guān)系的圖稱為多信息圖( m u l t i - i n f o r m a t i o ng r a p h ) 。多信息圖中 邊具有不同的類型，從麗增加了圖所蘊(yùn)含的信息量。需要注意到，多信息圖與多 重圖是不同的，多重圖中同樣的結(jié)點(diǎn)之間可以有多條邊，但是這些邊是沒(méi)有類型 沒(méi)有區(qū)別的。而在多信息圖中，不同類型的邊是有區(qū)別的，不可以當(dāng)作同一種關(guān) 系對(duì)待。 本文中，我們將考慮邊帶有權(quán)值的多信息圖，并從圖中挖掘連接其中若干指 定結(jié)點(diǎn)并滿足特定約束的子圖。我們稱作該問(wèn)題為多信息連通子圖挖掘 ( c o n n e c t i o nm u l t i i n f o r m a t i o ng r a p h ) 。 我們?cè)谝郧暗墓ぷ髦刑岢隽艘环N連通子圖挖掘算法，該問(wèn)題只是多信息連通 圖挖掘問(wèn)題的一種簡(jiǎn)單情形。當(dāng)多信息連通圖問(wèn)題中的邊只有一種類型，而約束 僅有對(duì)結(jié)果子圖的結(jié)點(diǎn)數(shù)上限的限制時(shí)，問(wèn)題將簡(jiǎn)化成為連通子圖挖掘問(wèn)題。原 塑科學(xué)技術(shù)大學(xué)碩七學(xué)位論文第2 章連通了幽挖掘問(wèn)題 來(lái)的算法不能解決般情形的多信息連通子圖挖掘問(wèn)題，因?yàn)樵瓉?lái)的算法只考慮 邊類型單一的情況。 實(shí)際中許多的數(shù)據(jù)都可以用圖來(lái)表示，并且圖中的關(guān)系存在不同類型，多信 息連通圖挖掘有很多的應(yīng)用。正如【l 】的作者所說(shuō)：“av e r yp r o m i s i n gr e s e a r c h d i r e c t i o ni se x t e n d i n gt h ec o n c e p t sa n da l g o r i t h m st o m u l t i g r a p h s ”。例如在傳統(tǒng)的 搜索引擎中，網(wǎng)頁(yè)是搜索的基本元素，網(wǎng)頁(yè)之間的關(guān)系只是簡(jiǎn)單的鏈接關(guān)系。而 在新一代的搜索引擎會(huì)以對(duì)象作為搜索的基本元素，對(duì)象之間的關(guān)系會(huì)有許多 的類型，比如在后面的實(shí)驗(yàn)中的科學(xué)家文獻(xiàn)網(wǎng)絡(luò)中，科學(xué)家之間的關(guān)系有合作關(guān) 系和引用關(guān)系兩種。我們可以利用多信息連通予圖挖掘的方法來(lái)進(jìn)行搜索內(nèi)容的 定位和擴(kuò)展，幫助讀者更快速的獲得信息。同樣，在人際關(guān)系網(wǎng)絡(luò)中，每個(gè)人作 為結(jié)點(diǎn)，結(jié)點(diǎn)之間的邊可以同時(shí)考慮入與人之間的多種聯(lián)系方式，如電話聯(lián)系、 電子郵件聯(lián)系等等不同的方式。在由公路地鐵等交通工具構(gòu)成的城市交通網(wǎng)絡(luò) 中，我們可以通過(guò)分析網(wǎng)絡(luò)的結(jié)構(gòu)來(lái)優(yōu)化城市交通。在化學(xué)反應(yīng)網(wǎng)絡(luò)中，反應(yīng)的 類型可以是不同的，我們針對(duì)性地給出一些限制就能發(fā)現(xiàn)一些可能有意義的反應(yīng) 結(jié)構(gòu)子網(wǎng)。 2 2 相關(guān)工作 2 2 1 連通子圖挖掘 首先提出并且研究連通子圖挖掘問(wèn)題的是c f a l i u t s o s 等人【l 】。c f a i l u t s o s 等人提出了一個(gè)基于類似電路分流的方法來(lái)尋找兩個(gè)給定結(jié)點(diǎn)之自j 的連通子圖， 也就是2 連通子圖問(wèn)題【1 。當(dāng)給定的結(jié)點(diǎn)數(shù)大于兩個(gè)時(shí)，基于電路原理的方法 就不再適用。基于電路分流的方法是將網(wǎng)絡(luò)中的邊看作電阻器，兩個(gè)給定結(jié)點(diǎn)看 作正極和負(fù)極，然后用一個(gè)函數(shù)來(lái)評(píng)價(jià)連通子圖的優(yōu)異性。這個(gè)方法只能用于兩 個(gè)給定結(jié)點(diǎn)的連通子圖問(wèn)題， 因?yàn)殡娐分兄挥袃蓚€(gè)極，電流要么來(lái)自j 下極，要 么來(lái)自負(fù)極，如果有第三個(gè)給定結(jié)點(diǎn)，我們無(wú)法決定將其看作正極還是負(fù)極。假 如我們找到每對(duì)節(jié)點(diǎn)之間的2 連通子圖來(lái)試圖找到n 連通子圖，這樣將可能會(huì)得 到些無(wú)用的結(jié)點(diǎn)，也有可能會(huì)丟失一些重要的結(jié)點(diǎn)。例如，假設(shè)給定圖2 2 ， 結(jié)點(diǎn)1 、2 和3 是給定的結(jié)點(diǎn)。如果我們對(duì)每一對(duì)結(jié)點(diǎn)使用前面的2 連通子圖發(fā) 現(xiàn)的方法，我們將得到一個(gè)結(jié)果子圖，這個(gè)子圖不包含結(jié)點(diǎn)7 。因?yàn)榻Y(jié)點(diǎn)7 周圍 的邊的權(quán)重較小而且結(jié)點(diǎn)7 度較大，這樣經(jīng)過(guò)計(jì)算得到經(jīng)過(guò)結(jié)點(diǎn)7 的電流就較小i 但是很明顯結(jié)點(diǎn)7 對(duì)于表現(xiàn)三個(gè)給定結(jié)點(diǎn)之間的關(guān)系很重要，應(yīng)該是我們需要的 結(jié)果的一部分。所以這個(gè)方法不能用來(lái)解決多連通子圖問(wèn)題。 史星科學(xué)技術(shù)火學(xué)碩士學(xué)位論文第2 章連通了幽挖掘問(wèn)題 圖2 - 2 用c f a l i u t s o s s 的算法尋找結(jié)點(diǎn)1 、2 、3 之間連通子圖例子 ( a ) 科學(xué)家合作網(wǎng)絡(luò)的結(jié)( b ) 演員合作州絡(luò)的結(jié) 果子圖果子圖 圈2 - 3s v a s t 的等人的方法使用在兩個(gè)真實(shí)網(wǎng)絡(luò)上得到的結(jié)果紅色結(jié)點(diǎn)代表算法選 出的相關(guān)結(jié)果結(jié)點(diǎn) 在 7 】中，s v a s t 等人提出了一個(gè)方法來(lái)提取給定結(jié)點(diǎn)之間相關(guān)結(jié)點(diǎn)結(jié)合的 方法。作者給出了一個(gè)挖掘幾個(gè)結(jié)點(diǎn)之間的相關(guān)結(jié)點(diǎn)集合的算法。他們的方法是 將無(wú)向圖的結(jié)點(diǎn)投射到一個(gè)歐拉空間中，然后基于圖上的隨機(jī)游走模型，用投射 空間中兩個(gè)結(jié)點(diǎn)間的歐拉距離衡量?jī)蓚€(gè)結(jié)點(diǎn)間的關(guān)系。他們的方法能夠找出幾個(gè) 結(jié)點(diǎn)之間的相關(guān)結(jié)點(diǎn)集合，但是不能保證連通。圖2 - 3 給出了這個(gè)方法在我們實(shí) 驗(yàn)所用的真實(shí)網(wǎng)絡(luò)上得到的結(jié)果，可以很明顯的看出，兩個(gè)結(jié)果子圖都不連通。， 同時(shí)這個(gè)方法時(shí)間復(fù)雜度也較高，對(duì)于連通子圖問(wèn)題，時(shí)蒯復(fù)雜度達(dá)到了 0 ( n 1 g 1 2 ) 。如果給定的網(wǎng)絡(luò)尺寸很大，算法的運(yùn)行時(shí)間將是不可接受的。 在 1 2 】中，w h m i l n o r 等人研究了在r d f 圖中同樣利用基于電路的方法來(lái) 發(fā)現(xiàn)信息予圖。實(shí)際上，他們的方法也只能用于給定兩個(gè)結(jié)點(diǎn)的情況，不適合j j ， 連通子圖問(wèn)題。 文獻(xiàn) 1 4 】中，h t o n g 等討論了一種連通子圖問(wèn)題的解決方法。他們的方法 中國(guó)科學(xué)技術(shù)= 學(xué)碩士學(xué)位論文第2 章連通予幽挖掘問(wèn)題 研究工作是基于文獻(xiàn)【1 】的。在文獻(xiàn)【1 中，作者給出了基于電路分流的方法來(lái)尋 找兩個(gè)結(jié)點(diǎn)之間的連通子圖，這是一個(gè)快速有效的方法，但是當(dāng)問(wèn)題變成多個(gè)結(jié) 點(diǎn)或者多信息圖時(shí)，這個(gè)方法就不再適用。在【1 4 】中作者先對(duì)每個(gè)結(jié)點(diǎn)跟每個(gè)給 定結(jié)點(diǎn)之間的關(guān)系進(jìn)行打分，然后再綜合這些打分得到一個(gè)結(jié)點(diǎn)對(duì)所有給定點(diǎn)的 關(guān)系得分，最后得到一個(gè)子圖的總分。他們問(wèn)題的約束為：至多有口個(gè)結(jié)點(diǎn)， 總分最大，包含所有給定點(diǎn)。他們的方法也能夠有效的解決多個(gè)結(jié)點(diǎn)的連通子圖 挖掘問(wèn)題，但是 1 4 中的方法針對(duì)的是無(wú)向的有權(quán)的連通圖，不存在多種意義的 邊，除了文章中提到的對(duì)連通性的約束，不能加入其他的約束條件。所以他們的 方法不能夠解決不同約束的多信息連通圖挖掘問(wèn)題。 經(jīng)過(guò)我們的調(diào)研，沒(méi)發(fā)現(xiàn)直接關(guān)于多信息連通圖挖掘問(wèn)題的相關(guān)工作。 2 2 2 其他相關(guān)工作 2 2 2 2 頻繁子圖挖掘 圖數(shù)據(jù)廣泛存在于我們的生活中，如化學(xué)、生物、國(guó)防等領(lǐng)域都大量使用到 了圖數(shù)據(jù)，因此，對(duì)基于圖的頻繁子圖挖掘算法的研究是非常必要的?；趫D的 數(shù)據(jù)挖掘提出時(shí)間并不長(zhǎng)，但是由于圖論作為數(shù)學(xué)的一個(gè)研究領(lǐng)域已經(jīng)有很長(zhǎng)的 研究歷史，因而頻繁子圖挖掘的發(fā)展很快，并被廣泛地應(yīng)用到許多領(lǐng)域中，如在 化學(xué)領(lǐng)域中，通過(guò)頻繁子圖挖掘算法找出構(gòu)成有毒物質(zhì)的分子結(jié)構(gòu)，以及通過(guò)對(duì) 網(wǎng)站瀏覽日志的挖掘， 分析出最頻繁的瀏覽模式等。1 9 8 7 年，yt a k a h a s h i 等人 2 2 1 介紹了一個(gè)生 物應(yīng)用領(lǐng)域的問(wèn)題，并進(jìn)一步提出了解決這個(gè)問(wèn)題的相關(guān)算法。通過(guò)挖掘化合物 結(jié)構(gòu)集中最大的共享結(jié)構(gòu)，以獲得化合物的特性關(guān)系，并指導(dǎo)生物實(shí)驗(yàn)。1 9 9 2 年，& j b a y a d a 等人 2 3 】提出了在生物化合物數(shù)據(jù)庫(kù)中挖掘共享子圖的問(wèn)題，并 給出了相應(yīng)的子圖挖掘算法。但該算法是屬于近似挖掘的范疇，且不考慮挖掘時(shí) 間和空間的代價(jià)。這也是圖挖掘研究初期比較樸素的挖掘方法。 在此之后，越來(lái)越多的研究者關(guān)注頻繁子圖挖掘問(wèn)題，不斷提出新的更好的 算法，其中比較著名的有f s g 、g s p a n 和f f s m 等。 2 0 0 1 年，m k u r a m o c h i 等人 2 4 】提出了一個(gè)頻繁予圖模式挖掘算法f s g 。 隨后在2 0 0 4 年，他們 】又提出了一個(gè)新的子圖挖掘問(wèn)題，即在1 個(gè)稀疏的超大 規(guī)模的圖中( 包含數(shù)以十萬(wàn)計(jì)的頂點(diǎn)和邊的圖) ，挖掘不相鄰的子圖模式。 2 0 0 2 年，x y a n 等人【2 5 提出了一個(gè)新穎的深度優(yōu)先搜索圖空間的方法，并 在此基礎(chǔ)上給出了頻繁子圖挖掘算法g s p a n 。g s p a n 算法與f s g 算法不同，它沒(méi) 有采用a p r i o r i 思想，而是利用邊模式增長(zhǎng)的方式深度優(yōu)先挖掘頻繁子圖。隨后 中國(guó)科學(xué)技術(shù)人學(xué)碩士掌位論文 第2 索連通子幽挖掘問(wèn)題 在2 0 0 3 年，他們【2 6 在g s p a n 算法的基礎(chǔ)上，迸步提出了挖掘頻繁閉合予圖 的算法c l o s e g r a p h ，頻繁閉合子圖集是頻繁子圖集的壓縮表達(dá)方式。 2 0 0 3 年，j h u m 等入【2 7 】提出了一個(gè)新的子圖擴(kuò)展策略，并在此基礎(chǔ)上形 成了頻繁子圖挖掘算法f f s m 。隨后在2 0 0 4 年，他們【2 8 】在f f s m 算法的基礎(chǔ)上j 更進(jìn)一步提出了最大頻繁子圖挖掘算法s p i n 。 由于問(wèn)題的定義不同，頻繁子圖挖掘的算法并不能解決連通子圖挖掘問(wèn)題。 2 2 2 2 社團(tuán)挖掘 圖中或者網(wǎng)絡(luò)中的社 牙1 ( c o m m u n i t ys t r u c t u r e ) 2 9 3 5 1 是指網(wǎng)絡(luò)中的連接緊密 的一部分頂點(diǎn)。實(shí)際網(wǎng)絡(luò)中的社團(tuán)挖掘一直是研究熱點(diǎn)，并且在實(shí)際應(yīng)用中取得 了許多成果。比如在w w w 網(wǎng)絡(luò)中的發(fā)現(xiàn)了專題集群( t h e m a t i cc l u s t 剛的存在； 在生物化學(xué)和神經(jīng)網(wǎng)絡(luò)中，社團(tuán)挖掘幫助我們發(fā)現(xiàn)了網(wǎng)絡(luò)中的功能團(tuán)體 ( f u n c t i o n a lg r o u p s ) 。 現(xiàn)階段社團(tuán)的定義大概有兩種： 自引用類型的定義：基本的社團(tuán)的定義是c l i q u e 。一個(gè)c l i q u e 是一個(gè)包 含兩個(gè)以上節(jié)點(diǎn)的子圖，予圖圖中任意兩個(gè)節(jié)點(diǎn)之間都有邊連接。換句 話說(shuō)就是一個(gè)完全圖。這是一個(gè)很強(qiáng)的定義。在現(xiàn)實(shí)的稀疏網(wǎng)絡(luò)中很少 有較大的團(tuán)體滿足這個(gè)定義。n - c l i q u e ，n - c l a n s 和n - c l u b s 都是放松了約 束的類似定義。如果允許距離更長(zhǎng)，也就是子圖圖中任意兩個(gè)節(jié)點(diǎn)之間 距離不大于n ，這樣的子圖被稱作n c l i q u e 。n c l a m 和n _ c l u b s 是n - c l i q u e 經(jīng)過(guò)一些細(xì)微變化后的定義。 比較類型的定義：上面的定義團(tuán)體都是只涉及了團(tuán)體內(nèi)部結(jié)點(diǎn)的互相關(guān) 系。另一個(gè)不同的方法是比較引向內(nèi)部和引向外部，這是由于對(duì)于一個(gè) 團(tuán)體來(lái)說(shuō)，第一感覺(jué)是內(nèi)部聯(lián)系比外部聯(lián)系更加緊密。一個(gè)寬松的定義 是團(tuán)體內(nèi)部聯(lián)系的邊總數(shù)大于從同外部聯(lián)系的邊總數(shù)。這個(gè)定義是比較 常用的定義。 常用的社團(tuán)發(fā)現(xiàn)算法時(shí)間復(fù)雜度都很高，比如o ( n 3 ) 或者指數(shù)階形式，這些 算法大多數(shù)都只針對(duì)幾十個(gè)到上千個(gè)節(jié)點(diǎn)的圖中的團(tuán)體，當(dāng)網(wǎng)絡(luò)規(guī)模變大。這些 方法的計(jì)算復(fù)雜度都隨指數(shù)冪增加。舉個(gè)簡(jiǎn)單的例子，在社會(huì)網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)研究 方面的資深專家n e w m a n 曾提出的一個(gè)快速社團(tuán)發(fā)現(xiàn)算法，對(duì)5 萬(wàn)個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò) 進(jìn)行計(jì)算需要4 0 多分鐘，而其他更慢的方法則需要幾個(gè)月甚至幾年時(shí)間爿能完 成一次在同樣規(guī)模的網(wǎng)絡(luò)上的完備的社團(tuán)發(fā)現(xiàn)計(jì)算。 當(dāng)連通幾個(gè)給定結(jié)點(diǎn)的子圖構(gòu)成一個(gè)社團(tuán)時(shí)，社團(tuán)發(fā)現(xiàn)的算法能夠找到連通 子圖。但是當(dāng)這幾個(gè)結(jié)點(diǎn)屬于不同社團(tuán)時(shí)，社團(tuán)發(fā)現(xiàn)的算法不能夠解決連通子圖 宇國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文第2 章連通予圈挖掘問(wèn)題 挖掘問(wèn)題。 2 2 2 3 其他工作 連通子圖問(wèn)題與生存網(wǎng)絡(luò)問(wèn)題比較相似。生存網(wǎng)絡(luò)上的工作是研究當(dāng)網(wǎng)絡(luò)中 的某些節(jié)點(diǎn)消失時(shí)，網(wǎng)絡(luò)的連通能力。生存網(wǎng)絡(luò) 4 的工作同樣也不能用來(lái)解決n 連通子圖問(wèn)題。例如，圖2 4 中的結(jié)點(diǎn)2 和結(jié)點(diǎn)4 具有相同的生存能力，當(dāng)刪除 任一個(gè)結(jié)點(diǎn)都會(huì)造成不連通。但是n 連通子圖問(wèn)題不僅僅考慮圖的連通性，還需 要考慮邊的權(quán)值以及結(jié)點(diǎn)度等信息。對(duì)于某些情況，結(jié)點(diǎn)l 和結(jié)點(diǎn)2 具有不同的 重要性。 圖2 - 4 一個(gè)生存網(wǎng)絡(luò)例子 其他相關(guān)的工作有多重關(guān)系數(shù)據(jù)挖掘 1 7 ，1 8 復(fù)雜網(wǎng)絡(luò)上的一些工作【2 ，8 ，9 ， 1 3 ，2 9 ，3 2 ，3 3 。但是這些工作與本文的問(wèn)題沒(méi)有很直接的關(guān)系。多重?cái)?shù)據(jù)挖掘方 法有歸納邏輯方法、多重關(guān)系聚類、概率關(guān)系模型和多重關(guān)系分類，這些方法都 不能用于解決多信息連通子圖的挖掘問(wèn)題。同時(shí)復(fù)雜網(wǎng)絡(luò)的一些研究對(duì)于我們 對(duì)算法的優(yōu)化和設(shè)計(jì)有定的啟發(fā)和引導(dǎo)作用。 卿學(xué)技術(shù)大學(xué)碩士學(xué)位論文第3 章連通予圖挖掘 第3 章連通子圖挖掘 連通子圖發(fā)現(xiàn)問(wèn)題是在一個(gè)很大的圖中尋找一個(gè)較小的子圖來(lái)表現(xiàn)幾個(gè) 給定節(jié)點(diǎn)在圖中的關(guān)系的問(wèn)題。本章介紹并提出了一種拓?fù)溲莼倪B通子圖挖掘 算法。我們首先給出一些定義。再分析了衡量結(jié)果子圖優(yōu)異性的限制條件。我們 的算法分為兩步，第一步使用一個(gè)候選子圖生成算法來(lái)減小計(jì)算的規(guī)模，第二步 使用基于u r m 編碼的演化算法得到最終的結(jié)果。在科學(xué)家合作網(wǎng)絡(luò)和演員網(wǎng)絡(luò) 上的實(shí)驗(yàn)證明我們的算法是有效的。 3 1 ，連通子圖挖掘問(wèn)題分析 本節(jié)給出了一些重要的定義，這些定義對(duì)于后面的問(wèn)題分析比較重要。然后 我們分析了如何衡量一個(gè)結(jié)果子圖優(yōu)異性。分析了問(wèn)題所面臨的限制條件。 3 ，2 1 一些重要的定義 首先我們先給出本章節(jié)的一些重要定義。 定義l ：關(guān)鍵結(jié)點(diǎn)。在連通子圖挖掘問(wèn)題中，w 個(gè)預(yù)先給定的需要尋找其問(wèn) 連通子圖的結(jié)點(diǎn)1 ，l ，垤，v n 就稱作關(guān)鍵結(jié)點(diǎn)。我們需要找到一個(gè)連通子圖來(lái)連通 的這 ，個(gè)結(jié)點(diǎn)的問(wèn)題就稱作連通子圖問(wèn)題，簡(jiǎn)稱n - c s d p ( n c o n n e c t i o n s u b g r a p hd i s c o v e r yp r o b l e m ) 。 在社會(huì)網(wǎng)絡(luò)中，如我們前面討論的，在不同的情況下名人的作用是不同的， 如在文章 1 】中，度小的結(jié)點(diǎn)就更受歡迎。但是事實(shí)上在社會(huì)網(wǎng)絡(luò)中，一個(gè)人是 否有名取決于同誰(shuí)比較。所以我們給出了如下的定義： 定義2 ：明星結(jié)點(diǎn)度大于所有關(guān)鍵結(jié)點(diǎn)的度的結(jié)點(diǎn)就稱作明星結(jié)點(diǎn)。 3 2 2 如何評(píng)價(jià)一個(gè)子圖的好壞 我們需要找到的是一個(gè)足夠好的表現(xiàn)給定關(guān)鍵結(jié)點(diǎn)之間關(guān)系的連通予圖。所 以一個(gè)重要的問(wèn)題是如何評(píng)價(jià)一個(gè)子圖的好壞。考慮到我們前面討論到的情況， 結(jié)果子圖應(yīng)當(dāng)滿足以下的限制條件： 1 ) 子圖必須很好的連通。很明顯，結(jié)果子圖必須連同。但是很好的連通是 什么慈思呢? 這里它是指結(jié)果子圖不僅僅是一個(gè)連通圖，在去掉所有的關(guān)鍵結(jié)點(diǎn) 之后仍然是連通的，任何一個(gè)結(jié)點(diǎn)和一個(gè)關(guān)鍵結(jié)點(diǎn)之間都有一條不通過(guò)別的關(guān)鍵 結(jié)點(diǎn)的路徑。在這樣的情況下，結(jié)果子圖的拓?fù)浣Y(jié)構(gòu)就能很好的表現(xiàn)n 個(gè)給定關(guān) 鍵結(jié)點(diǎn)之間可能存在的關(guān)系。例如假設(shè)我們的結(jié)果子圖是下圖2 1 中的g 。結(jié)點(diǎn) 宇國(guó)科學(xué)技術(shù)火學(xué)蜞士學(xué)位論文 第3 章連通子幽挖掘 1 、2 和3 是關(guān)鍵結(jié)點(diǎn)。g 是一個(gè)連通圖，但是結(jié)點(diǎn)4 沒(méi)有不經(jīng)過(guò)關(guān)鍵結(jié)點(diǎn)l 或 者關(guān)鍵結(jié)點(diǎn)2 的路徑連通關(guān)鍵結(jié)點(diǎn)3 ，同樣結(jié)點(diǎn)5 和關(guān)鍵結(jié)點(diǎn)2 ，結(jié)點(diǎn)6 和關(guān)鍵 結(jié)點(diǎn)l 之問(wèn)沒(méi)有這樣的路徑。從圖中看得出，結(jié)點(diǎn)4 的連通只表現(xiàn)了關(guān)鍵結(jié)點(diǎn)1 和關(guān)鍵結(jié)點(diǎn)2 之間的關(guān)系，與關(guān)鍵結(jié)點(diǎn)3 無(wú)關(guān)。在我們的3 c s d p 問(wèn)題中這樣的 結(jié)果是不滿足我們的要求的，所以結(jié)果子圖必須很好的連通。