組合方法在網絡群體結構劃分中的應用.pdf

1、自然科學、社會學和技術領域里的許多復雜系統(tǒng)都可以用網絡來表示,因而近年來關于網絡的研究引起了各個學科學者們的極大興趣?，F(xiàn)實網絡(real-world networks)在統(tǒng)計意義上的一些共有結構特性得到了廣泛而深入的研究。群體結構即是這些性質中的一種,它也是本篇博士論文的主要研究對象。 群體結構反映的是網絡中一些點集的如下特征：點的集合的內部連邊十分密集,而集合與集合之間的連邊較為稀疏。這也成為關于群體結構的一個基本的定義。群體

2、結構的研究對于生物、科技和社會網絡的結構認知均具有十分重要的意義；不僅如此,網絡群體結構的挖掘還有利于對網絡中的個體功能特征進行探索,因而具有重要的理論價值和廣闊的應用前景。雖然關于群體結構的量化定義至今尚未在學術界達成共識,但是在上述基本定義的基礎上,學者們開展了大量的工作。自2002年Girvan和Newman在《美國科學院院刊》(《PNAS》)上發(fā)表了一篇開創(chuàng)性的文章以來,六年間,僅是專門研究群體結構劃分方法的文章即有十余篇刊登在

3、《美國科學院院刊》和《自然》(《Nature》)雜志上；包括這些方法在內,至今已知的劃分方法達到四十余種；此外,應用這些方法對各學科領域網絡的群體結構進行研究的文章更是難以計數(shù)。然而,在目前已知的方法中,除了一類基于指標優(yōu)化的方法(以CNM方法為代表)之外,其它方法均無法在脫離外部參數(shù)和人為干預的情況下得到自然的群體結構。這也促使我們以研發(fā)新方法為基礎開展工作。 本篇論文由三個部分組成：在第一部分(第一章和第二章),我們提出了-

4、種新的群體結構劃分方法；第二部分(第三章和第四章)主要給出了該劃分方法的應用；應用又大致分為兩個方面：一是進行劃分方法性能測試與比較,主要通過應用各種方法(含本方法)于已知結構的現(xiàn)實網絡和人工網絡來實現(xiàn),二是網絡群體結構挖掘,即直接針對具體網絡進行群體結構分析。第三部分(第五章)探討如何進行群體結構的比較和評估。這三個部分的研究內容也正是當前群體結構劃分領域的三方面主要研究內容。 在第一章,我們回顧了群體結構劃分問題的發(fā)展歷程,

5、介紹了群體結構的不同定義,并分類綜述了近六年來部分有代表性的群體結構劃分方法。 在第二章里,我們提出了一種群體結構劃分的新方法,即LP方法,該方法基于組合優(yōu)化中的線性規(guī)劃理論。這是(截止相應成果發(fā)表時)在該領域中,第一種將線性規(guī)劃應用于網絡群體結構劃分的方法,也是第一種能夠不依賴于外來參數(shù)和人為干涉,獨立地給出單層群體結構的方法(CNM方法給出多層群體結構)。我們的模型最終可表述為基于單個控制參數(shù)的一組線性規(guī)劃問題。我們證明了該

6、方法關于控制參數(shù)的收斂性,并確定了參數(shù)的上界,從而也證明了該方法在實際應用中的可行性?；诶碚摲治?我們還討論了在實際運用中如何提高LP方法的效率。在第三章中,依照目前通行的評估方法,我們用三組測試證明了LP方法具有比當前的主流算法更好的品質。在第一組關于若干著名的現(xiàn)實基準網絡的試驗里,相對于GN算法(被認為是分析現(xiàn)實網絡最為有效的方法之一)和計算機科學領域的圖劃分算法,我們的方法均得到了更優(yōu)的結果。CNM方法是除LP方法外唯一能自然地

7、給出群體結構的算法,因此我們將其與LP方法進行比較。為此我們設計了第二組測試網絡,即“擾動試驗網絡”,并用四種指標對群體結構的結果進行了評估,結果證明我們的方法相對于CNM方法有更好的表現(xiàn)。第三組可信度評估測試基于一組被廣泛應用的基準人工網絡,即“四群組網絡”。所有三組測試均表明,LP方法不僅具有理論上的創(chuàng)新性,而且在實際應用中對于網絡群體結構的判定具有高度的準確性。 在第四章中,我們構造了一類特殊的基因網絡,即GO網絡。我們研

8、究了LP方法和CNM方法對斑馬魚(Zebrafish)GO基因網絡的功能模塊的探知能力。我們討論了得到的基因群體結構的生物學特性,并揭示了群體結構劃分方法對于基因功能認知的重要意義。 在第五章中,我們首先介紹了現(xiàn)有的各種比較(對于同一個集合的)多個劃分的量化指標,以及“單點轉移距離”指標的已知結果。出于實際需要,我們提出了“子集轉移距離”這種新指標,隨后用組合分析的方法,分四個區(qū)間完整地確定了該指標的上界,并構造了達到上界的特例