網(wǎng)絡(luò)圖的motif發(fā)現(xiàn)算法研究的中期報(bào)告

網(wǎng)絡(luò)圖的motif發(fā)現(xiàn)算法研究的中期報(bào)告一、引言網(wǎng)絡(luò)圖中的motif是指由若干個(gè)相互關(guān)聯(lián)的節(jié)點(diǎn)和相互關(guān)聯(lián)的邊構(gòu)成的子結(jié)構(gòu)。因此，研究網(wǎng)絡(luò)圖中的motif對(duì)于理解網(wǎng)絡(luò)結(jié)構(gòu)及其功能十分重要。一方面，motif可以作為網(wǎng)絡(luò)的基本單元，展示局部網(wǎng)絡(luò)特征。另一方面，motif也可以反映出網(wǎng)絡(luò)的功能和動(dòng)態(tài)演化過程。因此，網(wǎng)絡(luò)圖的motif發(fā)現(xiàn)算法是網(wǎng)絡(luò)科學(xué)領(lǐng)域的重要研究方向。目前，已經(jīng)有很多motif發(fā)現(xiàn)算法被提出。但是，這些算法主要集中在基于隨機(jī)模型的算法和基于圖挖掘的算法。其中，基于隨機(jī)模型的算法通常用于確定網(wǎng)絡(luò)圖中的motif是否是顯著的，但是對(duì)于給定網(wǎng)絡(luò)圖而言，這種方法只能找到已知的motif，不能找到新的motif結(jié)構(gòu)或者未知的重要motif。而基于圖挖掘的算法則主要是從局部的結(jié)構(gòu)出發(fā)，發(fā)現(xiàn)可能是motif的子結(jié)構(gòu)，并不斷合并和篩選，最后得到整個(gè)圖中的motif結(jié)構(gòu)。在研究網(wǎng)絡(luò)圖motif發(fā)現(xiàn)算法的過程中，本文主要關(guān)注兩個(gè)方向：一是統(tǒng)計(jì)模型，包括馬爾可夫隨機(jī)場(chǎng)和概率圖模型；另一個(gè)是圖挖掘技術(shù)，包括子圖同構(gòu)和譜聚類等。本文將對(duì)這些算法進(jìn)行介紹和分析，從而使我們能夠更好地理解網(wǎng)絡(luò)圖motif發(fā)現(xiàn)算法的研究現(xiàn)狀和未來的發(fā)展方向。二、馬爾可夫隨機(jī)場(chǎng)馬爾可夫隨機(jī)場(chǎng)是一種廣泛應(yīng)用于概率圖模型的方法，用于表示大量變量之間的依賴關(guān)系。在網(wǎng)絡(luò)圖motif發(fā)現(xiàn)算法中，一般將數(shù)據(jù)看作是一個(gè)圖，圖節(jié)點(diǎn)表示變量，節(jié)點(diǎn)之間的連接表示變量之間的依賴關(guān)系，而馬爾可夫隨機(jī)場(chǎng)則用于從網(wǎng)絡(luò)圖中解析出motif結(jié)構(gòu)。馬爾可夫隨機(jī)場(chǎng)中的某些子結(jié)構(gòu)可以被視為motif，比如二元關(guān)系、三元鏈等等。但是，馬爾科夫隨機(jī)場(chǎng)本身并沒有直接利用motif結(jié)構(gòu)的特點(diǎn)。因此，將馬爾可夫隨機(jī)場(chǎng)和具有motif特點(diǎn)的概率圖模型結(jié)合起來已經(jīng)成為一個(gè)熱門的研究方向。三、概率圖模型與馬爾可夫隨機(jī)場(chǎng)不同，概率圖模型直接建模motif結(jié)構(gòu)，從而更加直觀。在概率圖模型中，節(jié)點(diǎn)代表了隨機(jī)變量，邊表示了變量之間的依賴結(jié)構(gòu)。具體來說，基于概率圖模型的motif發(fā)現(xiàn)算法主要有基于概率圖模型的子圖匹配算法和基于模型學(xué)習(xí)的概率圖模型?；诟怕蕡D模型的子圖匹配算法主要是將網(wǎng)絡(luò)圖劃分成為多個(gè)小區(qū)域，并在每個(gè)小區(qū)域中識(shí)別出子結(jié)構(gòu)。該算法在尋找小的結(jié)構(gòu)的同時(shí)逐步擴(kuò)大到大的結(jié)構(gòu)，最終得出完整的motif結(jié)構(gòu)。這種方法的優(yōu)點(diǎn)是固定時(shí)間復(fù)雜度，但其缺點(diǎn)是容易受到初始劃分的影響，同時(shí)需要手動(dòng)設(shè)置參數(shù)。基于模型學(xué)習(xí)的概率圖模型則采用最大似然方法擬合出圖中的概率圖模型，其中motif結(jié)構(gòu)為這種模型的特征之一。這種方法可以適應(yīng)多種網(wǎng)絡(luò)結(jié)構(gòu)，并且比基于子圖匹配的算法具有更好的準(zhǔn)確性。四、圖挖掘技術(shù)圖挖掘技術(shù)通常采用的是從圖的局部結(jié)構(gòu)出發(fā)，逐步擴(kuò)大，最后尋找整個(gè)圖中的motif結(jié)構(gòu)。其中，最常用的方法是子圖同構(gòu)和譜聚類。子圖同構(gòu)是在不考慮節(jié)點(diǎn)和邊的順序的情況下判斷兩個(gè)圖中是否存在相同的圖結(jié)構(gòu)。該方法的優(yōu)勢(shì)是具有較高的準(zhǔn)確性和簡(jiǎn)單性，同時(shí)也可以適應(yīng)多種類型的motif。但是，這種方法的缺點(diǎn)是需要消耗大量的計(jì)算資源，對(duì)于大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)不太適用。譜聚類則是根據(jù)子圖相似度的譜分解將圖劃分成為若干個(gè)子圖，其中每個(gè)子圖都代表了網(wǎng)絡(luò)圖的一部分結(jié)構(gòu)。譜聚類方法可以很好地處理大規(guī)模圖，但是其對(duì)于不同的初始條件和參數(shù)設(shè)置可能得到不同的結(jié)果。綜上所述，當(dāng)前研究網(wǎng)絡(luò)圖motif發(fā)現(xiàn)