網(wǎng)絡(luò)圖的motif發(fā)現(xiàn)算法研究.pdf

1、網(wǎng)絡(luò)圖中的motif是一種連通的導(dǎo)出子圖，并且滿足在原圖中出現(xiàn)的次數(shù)比它在隨機(jī)圖中出現(xiàn)的次數(shù)多很多。這種性質(zhì)可以解釋成這種子圖在原圖中扮演了比在任意的隨機(jī)圖中更加重要的角色。近年來(lái)，關(guān)于motif的研究越來(lái)越多，而motif發(fā)現(xiàn)過(guò)程計(jì)算量極大，所以需要一個(gè)更加快速的motif發(fā)現(xiàn)程序來(lái)提高研究效率。
　　 motif發(fā)現(xiàn)程序的一般步驟是在原圖和它的統(tǒng)計(jì)特征相似的隨機(jī)圖上進(jìn)行子圖普查，然后找到符合一定統(tǒng)計(jì)性質(zhì)的子圖。由于對(duì)子圖進(jìn)行

2、全普查時(shí)又需要處理圖同構(gòu)的問(wèn)題，所以整個(gè)計(jì)算過(guò)程需要大量的計(jì)算時(shí)間。當(dāng)前，在處理圖同構(gòu)問(wèn)題時(shí)，大多數(shù)程序都使用一些正規(guī)標(biāo)號(hào)算法，比如NAUTY。本文發(fā)現(xiàn)，這是motif發(fā)現(xiàn)非常耗時(shí)的一個(gè)重要原因。本文提出了一個(gè)針對(duì)子圖大小小于等于6的網(wǎng)絡(luò)motif發(fā)現(xiàn)算法:NetMODE。為了減少對(duì)NAUTY的調(diào)用，本文使用一個(gè)預(yù)處理的方法，將所有小于等于5個(gè)節(jié)點(diǎn)的圖都儲(chǔ)存在內(nèi)存中，用于圖同構(gòu)的判定。對(duì)于節(jié)點(diǎn)數(shù)為6的情況，本文使用了一個(gè)基于圖重構(gòu)假設(shè)的