復雜網絡中的社團結構劃分及分析應用.pdf

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

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

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

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

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

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

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

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

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

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

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

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