組合方法在網(wǎng)絡(luò)群體結(jié)構(gòu)劃分中的應(yīng)用.pdf

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

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

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

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

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

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

7、給出群體結(jié)構(gòu)的算法,因此我們將其與LP方法進(jìn)行比較。為此我們?cè)O(shè)計(jì)了第二組測(cè)試網(wǎng)絡(luò),即“擾動(dòng)試驗(yàn)網(wǎng)絡(luò)”,并用四種指標(biāo)對(duì)群體結(jié)構(gòu)的結(jié)果進(jìn)行了評(píng)估,結(jié)果證明我們的方法相對(duì)于CNM方法有更好的表現(xiàn)。第三組可信度評(píng)估測(cè)試基于一組被廣泛應(yīng)用的基準(zhǔn)人工網(wǎng)絡(luò),即“四群組網(wǎng)絡(luò)”。所有三組測(cè)試均表明,LP方法不僅具有理論上的創(chuàng)新性,而且在實(shí)際應(yīng)用中對(duì)于網(wǎng)絡(luò)群體結(jié)構(gòu)的判定具有高度的準(zhǔn)確性。 在第四章中,我們構(gòu)造了一類(lèi)特殊的基因網(wǎng)絡(luò),即GO網(wǎng)絡(luò)。我們研

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