復雜網(wǎng)絡中的社團結構劃分及分析應用.pdf

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

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

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

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

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

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

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

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

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

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

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

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