復(fù)雜網(wǎng)絡(luò)動(dòng)態(tài)模式挖掘若干算法研究.pdf

1、復(fù)雜網(wǎng)絡(luò)的挖掘研究擁有廣泛的應(yīng)用領(lǐng)域，例如生物網(wǎng)絡(luò)、化學(xué)網(wǎng)絡(luò)、Internet、合作網(wǎng)和社會網(wǎng)絡(luò)等。挖掘動(dòng)態(tài)網(wǎng)絡(luò)模式已經(jīng)引起了極大的關(guān)注，這是因?yàn)楝F(xiàn)實(shí)世界中大多數(shù)的復(fù)雜系統(tǒng)都是動(dòng)態(tài)演化的，可以用動(dòng)態(tài)可變的網(wǎng)絡(luò)來描述，其蘊(yùn)含的動(dòng)態(tài)模式無法用靜態(tài)網(wǎng)絡(luò)準(zhǔn)確描述。已有的頻繁子圖模式、聚類和社區(qū)結(jié)構(gòu)挖掘等問題的研究成果，大都足基于靜態(tài)網(wǎng)絡(luò)的，僅能反映動(dòng)態(tài)網(wǎng)絡(luò)中一個(gè)子圖內(nèi)的模式，并不能很好地揭示時(shí)間和空間區(qū)域內(nèi)所蘊(yùn)含的演化模式與演化規(guī)律。挖掘動(dòng)態(tài)網(wǎng)

2、絡(luò)中隱藏的動(dòng)態(tài)模式為我們帶來了全新的挑戰(zhàn)。本文對多種動(dòng)態(tài)演化模式挖掘的若干問題和算法進(jìn)行了深入探索，力圖從微觀角度揭示復(fù)雜網(wǎng)絡(luò)在時(shí)空區(qū)域內(nèi)的演化規(guī)律，主要研究工作如下：
　　 (1)關(guān)于動(dòng)態(tài)網(wǎng)絡(luò)的挖掘，目前主要集中在挖掘無權(quán)圖的拓?fù)浣Y(jié)構(gòu)，較少涉及有權(quán)圖的挖掘，然而動(dòng)態(tài)有權(quán)圖在真實(shí)網(wǎng)絡(luò)中是大量存在的，權(quán)值的演化也是網(wǎng)絡(luò)演化中不可分割的一部分。針對動(dòng)態(tài)有權(quán)圖，提出了一種基于相關(guān)子模式的δ-STC模型，并設(shè)計(jì)了一種聯(lián)合聚類(Biclu

3、stering)算法δ-STC，挖掘在一定時(shí)間區(qū)間內(nèi)邊的權(quán)值演化趨勢線性相關(guān)的時(shí)空區(qū)域。算法以后綴樹為索引結(jié)構(gòu)，避免了窮舉各種模式，從而快速提取全部聚類結(jié)果。合成數(shù)據(jù)與真實(shí)基因調(diào)控網(wǎng)絡(luò)數(shù)據(jù)的實(shí)驗(yàn)證明了算法的有效性和可行性。
　　 (2)對動(dòng)態(tài)有權(quán)圖，挖掘權(quán)值變化非線性相關(guān)的趨辨Motif。趨勢Motif是一種有向子圖，反映拓?fù)浣Y(jié)構(gòu)與權(quán)值共同作用時(shí)在一定時(shí)間區(qū)間上的演化模式。引入廣義信息論中二次互信息作為相似性函數(shù)，結(jié)合滑動(dòng)窗口技

4、術(shù)，建立了一種權(quán)值向量非線性相關(guān)模型。在此基礎(chǔ)上提出了復(fù)雜網(wǎng)絡(luò)趨勢Motif挖掘算法MI-TMotif。實(shí)驗(yàn)結(jié)果顯示MI-TMotif算法具有良好的運(yùn)行性能，成功挖掘出非線性相關(guān)的趨勢Motif。
　　 (3)研究動(dòng)態(tài)無權(quán)網(wǎng)絡(luò)微觀演化模式的挖掘問題，即從邊演化的角度，挖掘在時(shí)間維上反復(fù)出現(xiàn)的子圖序列和對應(yīng)的演化動(dòng)作序列。提出了挖掘算法EPMiner，以隨機(jī)過程的狀態(tài)轉(zhuǎn)移描述演化過程，以演化時(shí)子圖拓?fù)浣Y(jié)構(gòu)的變化描述演化模式，提取其

5、中的頻繁模式，以揭示演化動(dòng)作與頻繁子圖拓?fù)浣Y(jié)構(gòu)之間的關(guān)聯(lián)關(guān)系。通過挖掘合成數(shù)據(jù)與真實(shí)數(shù)據(jù)，驗(yàn)證了算法的有效性，所得到的演化模式顯示，此類模式能夠提供豐富的動(dòng)態(tài)演化信息。
　　 (4)已有的頻繁子圖挖掘方法，通常是挖掘時(shí)間上同步的頻繁子圖，或者忽略時(shí)間因素，不能移動(dòng)時(shí)間標(biāo)記進(jìn)行對齊，即不能識別時(shí)間異步的頻繁子圖。為揭示更加復(fù)雜的演化模式，對動(dòng)態(tài)無權(quán)圖，挖掘在時(shí)間維上的頻繁演化Motif，即由同步同構(gòu)和異步同構(gòu)的頻繁子圖所構(gòu)成的演化