復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)探測(cè)和應(yīng)用研究.pdf

1、在現(xiàn)實(shí)中，許多復(fù)雜系統(tǒng)可以表示成復(fù)雜網(wǎng)絡(luò)。其中，節(jié)點(diǎn)表示系統(tǒng)的各種元素，連邊表示元素之間的聯(lián)系。通過(guò)應(yīng)用復(fù)雜網(wǎng)絡(luò)理論，人們能夠更好地理解、預(yù)測(cè)和控制復(fù)雜系統(tǒng)的行為。隨著對(duì)復(fù)雜網(wǎng)絡(luò)的深入研究，人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有社團(tuán)結(jié)構(gòu)，即各個(gè)子圖的內(nèi)部連接比較緊密，而子圖之間的連接比較稀疏。通過(guò)對(duì)社團(tuán)結(jié)構(gòu)的研究，人們能夠更好地了解網(wǎng)絡(luò)結(jié)構(gòu)的特征和功能。目前社團(tuán)結(jié)構(gòu)的研究包括社團(tuán)結(jié)構(gòu)的定義、探測(cè)和應(yīng)用。本文分別對(duì)社團(tuán)結(jié)構(gòu)的探測(cè)和應(yīng)用進(jìn)行了研究，主要

2、貢獻(xiàn)和創(chuàng)新點(diǎn)如下：
　　(1)提出了一種快速的模擬退火優(yōu)化算法，該算法通過(guò)優(yōu)化模塊度來(lái)探測(cè)靜態(tài)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。盡管許多基于模塊度優(yōu)化的社團(tuán)探測(cè)算法被提出，但是它們本質(zhì)上都是基于一種貪婪策略來(lái)優(yōu)化模塊度，因此獲得的模塊度通常都是一種局部最大值?；诖耍疚睦媚M退火算法來(lái)優(yōu)化模塊度。同時(shí)，為了提升模擬退火算法的收斂速度，本文從兩個(gè)方面對(duì)它進(jìn)行優(yōu)化：(i)利用層次聚類(lèi)算法獲取一個(gè)初始社團(tuán)劃分；(ii)在優(yōu)化模塊度的每一步，隨機(jī)從一

3、個(gè)社團(tuán)中提取一個(gè)連通子圖并轉(zhuǎn)移到另外一個(gè)社團(tuán)。實(shí)驗(yàn)結(jié)果表明該算法不僅能夠獲得很高的模塊度，而且與傳統(tǒng)模擬退火算法相比，極大地提升了計(jì)算效率。
　　(2)提出了一種快速的動(dòng)態(tài)社團(tuán)探測(cè)算法，該算法首先利用上一時(shí)刻的社團(tuán)結(jié)構(gòu)和當(dāng)前時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)造一個(gè)小網(wǎng)絡(luò)，然后在小網(wǎng)絡(luò)上探測(cè)當(dāng)前時(shí)刻的社團(tuán)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明與傳統(tǒng)算法相比，該算法極大地提升了社團(tuán)探測(cè)的計(jì)算效率。另外，本文還提出了一種快速的社團(tuán)映射算法，該算法首先將上一時(shí)刻的每個(gè)社團(tuán)分裂

4、成若干個(gè)小模塊，然后使用這些小模塊構(gòu)建一個(gè)小網(wǎng)絡(luò)并在小網(wǎng)絡(luò)上探測(cè)當(dāng)前時(shí)刻的社團(tuán)。由于每個(gè)社團(tuán)都可以看成是若個(gè)小模塊的組合，因此在社團(tuán)映射階段可以通過(guò)統(tǒng)計(jì)兩個(gè)社團(tuán)的共同模塊來(lái)計(jì)算它們的相似度。實(shí)驗(yàn)結(jié)果表明該算法不僅能夠保證社團(tuán)劃分的質(zhì)量，而且還能夠極大地提升社團(tuán)映射階段的計(jì)算效率。
　　(3)提出了一種基于社團(tuán)結(jié)構(gòu)的關(guān)鍵節(jié)點(diǎn)組挖掘算法。對(duì)于許多傳統(tǒng)算法來(lái)說(shuō)，它們通常都是選擇前k個(gè)最重要的節(jié)點(diǎn)或者k個(gè)互不相連的重要節(jié)點(diǎn)作為關(guān)鍵節(jié)點(diǎn)。然

5、而，這些關(guān)鍵節(jié)點(diǎn)可能通常只位于少數(shù)社團(tuán)。由于一個(gè)關(guān)鍵節(jié)點(diǎn)的影響力很難從它所在的社團(tuán)傳播到其它社團(tuán)，因此傳統(tǒng)算法選擇的一組關(guān)鍵節(jié)點(diǎn)的影響力有限。為了最大化一組關(guān)鍵節(jié)點(diǎn)的影響力，本文提出了選擇關(guān)鍵節(jié)點(diǎn)的三個(gè)約束條件：（i）單個(gè)節(jié)點(diǎn)的影響力很強(qiáng)；(ii)它不能與已知的關(guān)鍵節(jié)點(diǎn)相連；（iii）它不能與包含關(guān)鍵節(jié)點(diǎn)的社團(tuán)相連。實(shí)驗(yàn)結(jié)果表明該算法選擇的一組關(guān)鍵節(jié)點(diǎn)更有影響力。
　　(4)提出了一種基于社團(tuán)結(jié)構(gòu)的快速鏈路預(yù)測(cè)算法。在實(shí)際網(wǎng)絡(luò)中，

6、鏈接傾向于在局部聚集并形成社團(tuán)結(jié)構(gòu)，這種現(xiàn)象表明社團(tuán)結(jié)構(gòu)與鏈路形成之間存在相關(guān)性。因此，本文首先提出一種獲取獨(dú)立社團(tuán)劃分樣本的算法，然后設(shè)計(jì)了兩個(gè)基于社團(tuán)劃分樣本的統(tǒng)計(jì)量，分別用來(lái)預(yù)測(cè)社團(tuán)內(nèi)部和社團(tuán)之間的節(jié)點(diǎn)對(duì)產(chǎn)生連邊的概率。實(shí)驗(yàn)結(jié)果表明與經(jīng)典的SBM模型相比，該算法不僅能夠準(zhǔn)確地預(yù)測(cè)網(wǎng)絡(luò)中的丟失連邊，而且還能夠極大地提升計(jì)算效率。另外，通過(guò)該算法計(jì)算的連邊概率，本文揭示了社團(tuán)結(jié)構(gòu)中的三種鏈路形成機(jī)制。實(shí)驗(yàn)結(jié)果表明該算法在由三種鏈路形成