復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)劃分及分析應(yīng)用.pdf

1、過去幾十年間，以Internet為代表的信息技術(shù)的迅猛發(fā)展使人類社會(huì)邁入了網(wǎng)絡(luò)時(shí)代.將數(shù)學(xué)中的圖論應(yīng)用到各種領(lǐng)域中的問題后，形成了以研究某種實(shí)際節(jié)點(diǎn)和節(jié)點(diǎn)之間關(guān)系的學(xué)科-網(wǎng)絡(luò)科學(xué).從網(wǎng)絡(luò)科學(xué)的角度來看，無論是自然界還是人類社會(huì)，網(wǎng)絡(luò)都無處不在，比如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、萬維網(wǎng)、生物網(wǎng)絡(luò)以及工程網(wǎng)絡(luò)等等，這些網(wǎng)絡(luò)相互交叉，深刻且廣泛地影響著人們的日常生活和科學(xué)技術(shù)等各種活動(dòng).因此，利用網(wǎng)絡(luò)科學(xué)，可以探討自然界和人類社會(huì)的各種各樣的復(fù)雜系統(tǒng).

2、在網(wǎng)絡(luò)科學(xué)的思想、理論和方法的大框架下，無論從微觀上還是宏觀上，人們都可以從全新的網(wǎng)絡(luò)的角度、觀點(diǎn)和方法來探討世界萬物的復(fù)雜性問題.復(fù)雜網(wǎng)絡(luò)作為網(wǎng)絡(luò)科學(xué)的表現(xiàn)形式，為人們研究網(wǎng)絡(luò)科學(xué)提供了一條路徑.
　　隨著對(duì)網(wǎng)絡(luò)的研究，人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都有一個(gè)共同的性質(zhì)，即為社團(tuán)結(jié)構(gòu)，也就是說整個(gè)網(wǎng)絡(luò)是由若干個(gè)“群”或“團(tuán)”構(gòu)成的，每一個(gè)社團(tuán)內(nèi)部的節(jié)點(diǎn)之間連接相對(duì)非常緊密，但是各個(gè)社團(tuán)之間的連接相對(duì)比較稀疏.復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的研究對(duì)分析復(fù)雜

3、網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、理解復(fù)雜網(wǎng)絡(luò)的功能、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的隱藏規(guī)律和預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的行為不僅有十分重要的理論意義，而且有廣泛的應(yīng)用前景.盡管網(wǎng)絡(luò)是系統(tǒng)高度抽象的離散數(shù)學(xué)描述，但是因?yàn)槠湟?guī)模的龐大和系統(tǒng)連接的多樣性也使得研究其結(jié)構(gòu)和功能變得復(fù)雜.社團(tuán)化是一種揭示系統(tǒng)結(jié)構(gòu)和功能之間對(duì)應(yīng)關(guān)系、降低對(duì)復(fù)雜系統(tǒng)認(rèn)識(shí)難度的方法.考慮網(wǎng)絡(luò)G的子網(wǎng)絡(luò)V中的節(jié)點(diǎn)i，則ki(V)=kini(V)+kouti(V)，其中kini(V)表示節(jié)點(diǎn)i連接子網(wǎng)絡(luò)V內(nèi)其它節(jié)點(diǎn)

4、的邊的條數(shù)，kouti(V)表示節(jié)點(diǎn)i連接子網(wǎng)絡(luò)V外其它節(jié)點(diǎn)的邊的條數(shù).在此基礎(chǔ)上給出社團(tuán)結(jié)構(gòu)的兩種量的定義:
　　(1)強(qiáng)社團(tuán)結(jié)構(gòu).如果對(duì)任意節(jié)點(diǎn)i，子網(wǎng)絡(luò)V滿足kini(V)＞kouti(V)，(V)i∈V.即該社團(tuán)內(nèi)任何一個(gè)節(jié)點(diǎn)與這個(gè)社團(tuán)內(nèi)部其他所有節(jié)點(diǎn)的連接數(shù)目，比它與該社團(tuán)外部的所有節(jié)點(diǎn)的連接數(shù)目要多，那么稱V為該網(wǎng)絡(luò)的強(qiáng)社團(tuán)結(jié)構(gòu).
　　(2)弱社團(tuán)結(jié)構(gòu).如果子網(wǎng)絡(luò)V滿足∑i∈Vkini(V)＞∑i∈Vkouti(

5、V).即該社團(tuán)內(nèi)節(jié)點(diǎn)間的相互連接比這些節(jié)點(diǎn)與社團(tuán)外部的節(jié)點(diǎn)的聯(lián)系更加緊密，也就是說，社團(tuán)內(nèi)部的邊數(shù)之和大于社團(tuán)邊界上的邊數(shù)之和，那么稱V為該網(wǎng)絡(luò)的弱社團(tuán)結(jié)構(gòu).
　　社團(tuán)結(jié)構(gòu)的劃分方法主要分為兩類:全局方法與局部方法.全局方法包含譜方法、模塊度方法以及密度子圖方法等等;局部方法主要采用局部聚類的方式來劃分社團(tuán)結(jié)構(gòu).這些方法主要是基于統(tǒng)計(jì)物理的方法和啟發(fā)式算法，我們從圖論的角度出發(fā)，提出了新的社團(tuán)劃分方法.二分圖又稱作二部圖，是圖論中

6、的一種特殊模型.設(shè)G(VE)是一個(gè)無向圖，如果頂點(diǎn)V可分割為兩個(gè)互不相交的子集（U,K），并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn)i和j分別屬于這兩個(gè)不同的頂點(diǎn)集（i∈U,j∈K），則稱圖G為一個(gè)二分圖.我們根據(jù)一個(gè)一般的網(wǎng)絡(luò)G(V,E)建立與之相關(guān)的二分網(wǎng)絡(luò)G(V,V'，E)，把原始網(wǎng)絡(luò)中G的節(jié)點(diǎn)分別作為二分網(wǎng)絡(luò)的兩部分節(jié)點(diǎn)(V,V')，根據(jù)原來的邊集E在兩部分節(jié)點(diǎn)之間連邊，這樣就建立了一個(gè)二分網(wǎng)絡(luò).最大流問題是在網(wǎng)絡(luò)中求源點(diǎn)到匯點(diǎn)

7、的最大流值的問題，在二分網(wǎng)絡(luò)中，把點(diǎn)集V作為源點(diǎn)集合，并建立k個(gè)匯點(diǎn)集合，每條邊上的流值為1，最后統(tǒng)計(jì)匯點(diǎn)上的最大流值.k個(gè)匯點(diǎn)就可以看成k個(gè)社團(tuán)，流向這些匯點(diǎn)的源點(diǎn)就是這個(gè)社團(tuán)內(nèi)的點(diǎn)，稱這種方法為基于改進(jìn)最大流問題的社團(tuán)劃分方法.
　　圖的均勻染色是一種特殊的點(diǎn)染色.如果圖G(VE)的點(diǎn)集V可以劃分成k個(gè)獨(dú)立的子集V1，V2，…，Vk，使得||Vi|-|Vj||≤1(1≤i，j≤k)，則稱圖G是均勻k-可染的.由此我們同樣可以定

8、義網(wǎng)絡(luò)的均勻社團(tuán)劃分，并且根據(jù)不同的指標(biāo)就能劃分不同的社團(tuán)結(jié)構(gòu).我們主要研究了兩種均勻社團(tuán)結(jié)構(gòu)的劃分，一種是全均勻社團(tuán)劃分，各個(gè)社團(tuán)內(nèi)部的節(jié)點(diǎn)數(shù)目差值小于1;第二種是密度均勻的社團(tuán)結(jié)構(gòu)，各個(gè)社團(tuán)之間的劃分密度，也就是邊數(shù)與點(diǎn)數(shù)的比值，保持一致.結(jié)合這兩個(gè)定義在文章中介紹了對(duì)應(yīng)的社團(tuán)劃分方法以及意義，說明了網(wǎng)絡(luò)的均勻社團(tuán)劃分具有廣泛的應(yīng)用價(jià)值.
　　挖掘網(wǎng)絡(luò)中的重要節(jié)點(diǎn)是網(wǎng)絡(luò)中很重要的一類問題，也就是對(duì)于網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性進(jìn)行排序.

9、在探索網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)時(shí)，一般的社團(tuán)劃分方法并不能真正反應(yīng)節(jié)點(diǎn)和社團(tuán)的實(shí)際關(guān)系，重疊社團(tuán)發(fā)現(xiàn)更符合真實(shí)世界的社團(tuán)組織規(guī)律，這種現(xiàn)象普遍存在于各種真實(shí)網(wǎng)絡(luò)之中，如社會(huì)網(wǎng)絡(luò)中的人屬于多個(gè)集體、網(wǎng)絡(luò)中的網(wǎng)頁屬于多個(gè)主題等.因此，位于網(wǎng)絡(luò)中重疊區(qū)域的節(jié)點(diǎn)就尤為重要.在網(wǎng)絡(luò)中，通過比較疾病在相同條件下的傳播范圍，來確定節(jié)點(diǎn)的重要性，范圍越廣，影響力越高.文中分別分析了具有最大度數(shù)的點(diǎn)，最大介數(shù)的點(diǎn)，最大聚類系數(shù)的點(diǎn)以及位于重疊區(qū)域節(jié)點(diǎn)的傳播范圍，確

10、認(rèn)處于重疊區(qū)域的點(diǎn)的影響力相較于其它的節(jié)點(diǎn)要高.因此，在疾病傳播過程中，應(yīng)優(yōu)先對(duì)這些點(diǎn)進(jìn)行免疫或者隔離，而在新聞傳播中應(yīng)重點(diǎn)宣傳.
　　為了更好地了解復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，人們建立了各種網(wǎng)絡(luò)演化模型，比如隨機(jī)網(wǎng)絡(luò)模型，小世界網(wǎng)絡(luò)以及無標(biāo)度網(wǎng)絡(luò).這些模型很好的匹配了網(wǎng)絡(luò)演化過程中的某些性質(zhì).任意兩個(gè)質(zhì)點(diǎn)之間都存在引力，與質(zhì)點(diǎn)的質(zhì)量成正比，而與質(zhì)點(diǎn)間的距離的平方成反比，這是萬有引力定律的基本內(nèi)容，文中認(rèn)為這一定律同樣適用于復(fù)雜網(wǎng)絡(luò)的演化

11、過程.把節(jié)點(diǎn)的度數(shù)看成質(zhì)量，再加上節(jié)點(diǎn)間的距離，就建立了適用于網(wǎng)絡(luò)演化的引力網(wǎng)絡(luò)模型.利用這一模型建立的網(wǎng)絡(luò)具有更多的實(shí)際網(wǎng)絡(luò)的性質(zhì)，而且包含明顯的社團(tuán)結(jié)構(gòu).社團(tuán)與社團(tuán)之間的結(jié)構(gòu)也是不同的，文中揭示了兩種社團(tuán)結(jié)構(gòu)，一種是領(lǐng)導(dǎo)者社團(tuán)，社團(tuán)內(nèi)部存在一個(gè)或者幾個(gè)具有較大度數(shù)的節(jié)點(diǎn);另一種是自組織社團(tuán)，社團(tuán)內(nèi)部的所有節(jié)點(diǎn)的度數(shù)相差不大.文中綜合探討了這兩種社團(tuán)結(jié)構(gòu).此外，引力網(wǎng)絡(luò)模型中也包含這兩種社團(tuán)結(jié)構(gòu).
　　本文主要研究的是復(fù)雜網(wǎng)絡(luò)中

12、的社團(tuán)結(jié)構(gòu)劃分，以及與社團(tuán)結(jié)構(gòu)相關(guān)的復(fù)雜網(wǎng)絡(luò)問題，全文共分為五章.
　　第一章給出了一個(gè)相對(duì)完整的簡(jiǎn)介.首先介紹一些復(fù)雜網(wǎng)絡(luò)的歷史和概念，然后給出了關(guān)于社團(tuán)結(jié)構(gòu)劃分方法以及社團(tuán)結(jié)構(gòu)的評(píng)價(jià)指標(biāo)的相對(duì)完整的綜述，最后，給出了本文的主要結(jié)果.
　　第二章我們首先研究了基于改進(jìn)的最大流問題的社團(tuán)劃分方法，并給出了幾個(gè)實(shí)際網(wǎng)絡(luò)的劃分情況.然后討論了網(wǎng)絡(luò)中的均勻社團(tuán)劃分，我們揭示了兩種均勻社團(tuán)結(jié)構(gòu)，并結(jié)合一個(gè)真實(shí)網(wǎng)絡(luò)說明了均勻社團(tuán)劃分的