重慶郵電大學研究生堂下考試答卷2011學年第1學期考試科目圖論及其應用姓名王裕坤年級2011級專業計算機應用技術2011年12月18日網絡中的群落結構性分析及應用摘要：在對科學網絡的研充中，包括社交網絡、計算機網絡、管理網絡等都需要對網絡進行分類，探測以及描述網絡的特征是網絡系統研究過程中一個非常重要的問題。其中有一個非常高效的辦法就是在網絡可能的劃分上使質量函數模塊度(modularity)的值達到最優(在后面會看到實際上就是使得模塊度的值達到最大)。而模塊度可以用描述網絡的特征矩陣的特征向量來表示，這種表示方法使用譜算法對群落進行探測。這種算法與競爭算法相比具有更好的性能，這在以后的應用中會加以闡釋。關鍵字：劃分；模塊度；社交網絡；模塊1、 社交網絡劃分的背景許多具有科學價值的系統都可以用節點組，或者通過邊所連接的節點來進行表示，這樣的例子有很多，比如因特網、萬維網、新陳代謝網絡、食品網絡、神經網絡、通信和分布式網絡、社交網絡等等。關于網絡系統的研究己經有很多的歷史了，但是研究網絡的興趣在最近的十兒年卻慢慢的增加，特別是在數學科學中，這主要是由于描述現實的網絡拓撲中大規模精確數據應用的增加。對這些數據的分析顯示了一些未料到的特征，比如高度的網絡傳遞性，藉-律度的分布性等等現在有一個研究方向引起了很大的關注，這就是對網絡中群落結構進行探測以及描述，這意味著發現高密度節點相連接的群落，而在不同的群落之間只有很少的連接。這種探測群落的能力將會有重要的意義，例如，在萬維網上的群落所對應的網頁組可能具有相同的話題，網絡中的群落可能與現實中的社會單元或者團體相對應。現在僅有的發現是網絡中包含的緊緊交織的群落可以傳遞出有用的信息，如果一個新陳代謝的網絡被劃分成這樣的群落，那么它可以為網絡動態變化的模塊式觀點提供有用的證據。這種網絡的動態變化的模塊式觀點是不同群落中的結點具有不同的功能，并且具有一定的獨立性。在過去對網絡的劃分上分為兩個派系，并且這兩個派系都有很長的歷史，第一種是利用圖形來進行劃分，這種方法被計算機科學以及相關的領域推崇,廣泛的應用于平行計算以及集成電路的設計。第二種方法是采用塊模型、層次性集中或者群落結構探測等，主要是一些社會學家、物理學家以及生物學家在用這個方法，這個方法特別應用于社會和生物網絡。而在本文中的重點則是在網絡數據集的基彳冊［?來探測群落結構。當給定我們二個網絡時，我們最常用的方法就是去尋找兩個部落節點的分界以此來減少兩個部落之間邊的數目，這種最小切割的方法是在圖形分割中最為常用的。但是這種僅僅依靠邊數來量化群落結構顯然不是一個好的方法，一個好的分割群落的方法應該不僅僅是在兩個群落之間有很少的邊數，更應該是兩個群落之間的邊數比我們預期的要少。2、 模塊度在社交網絡劃分上應用在網絡中真正群落結構和邊的排布從靜態上看具有驚人的一致性，這可以通過模塊度(modularity)的方法進行量化。模塊度的值既可以是正數也可以是負數，正數預示著群落可能的結構，因此我們可以非常精確的得到網絡的結構通過尋找那些模塊度的值比較大的網絡劃分。這種依靠模塊度來分割的方法比其他的分割的方法都要優秀的多，現在我們就來看一看如何求的一個網絡的模塊度的值。假設我們的網絡包含n個頂點，首先我們考慮將網絡劃分為兩個群落的的情況，如果頂點i屬于群落1我們讓禹=1,如果頂點1屬于群落2我們讓Sj=-1,頂點i與頂點j之間的邊我們稱為可，它的值通常是0或者1,當多條邊存在的情況下它的值會更大一些（0也被稱為鄰接矩陣）。在同一時間頂點i和頂點j有邊的概率為人氣/2皿，其中&和kj是頂點的度，而01=1^是網絡中邊的總數目，模塊度的值Q是落在相同群落所有頂11點/2m的總和。通過觀察我們可以得到如果頂點i和頂點j在同一群落那么l（siSj+1）為1,如果不在同一群落那么表達式的值為Oo我們可以將模塊度的值如下表示：①土知土"孑岑）爭[1]通過觀察我們還得知。前面的1/4m僅僅是一個傳統的參數，1ij它的只是為前面的模塊度定義相兼容。方程[1]可以很方便的寫成矩陣的形式。Q=—stBs[2]4m在這里s為列向量，它的元素為S|,我們乂定義了一個對稱矩陣B并且它的元素為：B一業⑶1J氣2m我們稱B矩陣為模塊度矩陣，在這篇文章中我們大部分的篇幅都在研究這個矩陣的特性。我們會發現B矩陣的每行以及每列的元素之和都為0,所以它總會有一個與特征值0相對應的特征向量（1,1,1……）。根據己給出的方程[2],我們可以將S用矩陣B的標準化特征向量II】的線性組合加以表示，即：s=￡，aq，其中a-ujso然后我們發現：。=土2>*￡3凹=土立（耳T.S）也 [4]qm1 j qm在這里及是矩陣B的特征值，其所對應的特征向量為II,,我們假設特征值按照遞減的順序進行排列，即：P1>P2>-Pn^我們可以對網絡恰當的劃分使得模塊度的值達到最大，同樣也可以選擇禹的值使得模塊度的值達到最大。這意味著我如果我們對S出了標準化之外沒有其們要選的S使得史("?如果我們對S出了標準化之外沒有其他的限制，我們'可以很簡單的完成這個任務，即：選擇S和特征向量II,成比例。這將所有的比重都加在了特征值為們的這一項上，其他項都為0,因為特征向量都相互正交。但是不幸的是，我們有另外一個限制，即S元素的值只能是+1或者-1,這意味著我們不能選擇讓s和烏成比例。但是我們可以S與II】盡可能的平行,這和讓u/.s的點積取的最大值是等價的。簡明的說就是如果4中相應的元素為正數我們就將％設置為+1,相反我們將島設置為-1。換句話說，我們將所有頂點相對應的元素，正數放在一個群里，剩下的放在另一個群落。這也給劃分網絡提供了一個方法:我們計算模塊度矩陣的第一個(最大的)特征向量,然后根據特征向量的元素的符號來將頂點分成兩個不同的群落。我們很快就發現了這個方法所具有的令人滿意的特點，第一，在之前己經被說的很清楚了，這個方法在不知道群落的大小的情況下仍然是實用的。不像一些最小化群落之間邊的數目的傳統算法，這種算法不需要對群落的大小加以限制或者禁止單群落所有頂點的平凡解。然而在模塊度矩陣中可能沒有正數的特征值，在這種情況下，第一個特征向量為(1,1,1……)與單群落所有頂點相對應。但是這是最精確的結果，這個算法在這種情況下告訴我們，在特征值都為非正數的模塊度矩陣是不可分割的，這從方程［4］可以直接的看出來，因為所有的項目的和只能是0或者是負數。不能分割的網絡其模塊度的值為0,這是算法可以達到的最好的結果。這是算法的一個很重要的特征，這個算法不僅能高效的對網絡進行分割，并且在沒有好的分割方法存在的情況下能拒絕分割網絡，后一種情況在網絡中成為不可分割。即：如果模塊度矩陣沒有正數的特征值那么這個網絡不可分割，這個思想在以后的研充中起著重要的作用。這個算法僅用到第一個特征向量元素的符號，但是元素的度也能傳遞一些有用的信息。如果頂點所對應的元素有很大的度的話，那么它對模塊度的值的貢獻也就越大，反之亦然，這在方程［4］中可以看到。如果一個頂點，它所對應的元素的度很大，不可能將這個元素從一個群落移動到另一個群落而不引起模塊度值大的變化。因此在第一個特征向量中的元素值描述了頂點屬于指定群落的緊密程度，那些元素值比較大的是群落的核心成員，而那些值相對較小的元素在群落中則不那么重要。3、實驗部分我們現在運用模塊度的方法得出了這樣一個算法，現在我們來簡單的檢驗一下這個算法是不是像我們前面所得出的結論那樣可以高效的對網絡進行劃分。在某個實驗室中有兩個實驗小組，分別為A組和B組，總共有12人。他們都在實驗室但是分別從事的是不同的項目，每一個組有一個核心的成員負責他的組的進度，有些成員即在從事A組的項目同時乂在做B組的項目，為了方便我們把每一個成員進行編號，分別為1號到12號，因為我們己經事先知道哪些成員是屬于A組，哪些成員是屬于B組，所以我們這個小實驗只是來進行驗證，以下是實驗室所有成員的網絡拓撲：圖一中的網絡拓撲就描述了實驗室各成員之間的情況，很明顯的可以看出一組以6號成員為核心成員，一組以11號成員為核心成員，現在我們考慮在Matlab的實驗環境下對上述算法進行測試，看是否能夠達到我們要求的效果。上述的網絡拓撲建立相應的鄰接矩陣如下：X123456—89101112101000010000021010010000003010101000000400100100000050000010000006011110100000—10000100000080000101010109000000010110100000000010111100000001110112000000000110圖二2634759810111226347598101112由圖二可知，鄰接矩陣是一個對稱矩陣，對每一對（i,j）在鄰接矩陣A中都有唯一的一個元素Aj與之對應。在Matlab實現模塊性劃分算法的源代碼如下：mnction[]=Main(j[SociaLData]=xlsread(D:\matlab數據\test_data.xlsl;K=K=[233215343,342];A二SociaLData;m=sum(K)；[kl,k2]=size(A)；zeros(kl,k2);fori=l:k2%用以描述結點的度財表示為鄰接矩陣%為所有結點度的總和forj=l:k2B(切二A(i,j)-K(i)*K(j)/2*m;endend%求出B矩陣[V,D]=eig(B);max=D(1,1);fork=l:k2遷(D(k,k)>max)%求出B矩陣的最大特征值max%求出B矩陣的最大特征值max_k=k;endend%求出B矩陣最大特征值所對應的最%大特征向量Vector_max=%求出B矩陣最大特征值所對應的最%大特征向量cl=l;c2=l;fort=l:k2%根據最大特征向量中的值對結點進行if(Vector_max(t)>0)%根據最大特征向量中的值對結點進行S_pos(cl)=t;%分類cl=cl+l;elseS_neg(c2)二t;c2=c2+l;endendRl=sprintf(Thenumbersoffollowingnode%disingroupA\n\S_pos)R2=sprintf(Thenumbersoffollowingnode%disingroupB\n；S_neg)運行上述程序得到如下的結果截圖如下:?MainR1=Thenumbersoffollowingnode1isingroupAThenumbersoffollowingnode2isingroupAThenumbersoffollowingnode3isingroupAIhenumbersoffollowingnode4isingroupAIhenumbersoffollowingnode5isingroupAThenumbersoffollowingnode6isingroupAThenumbersoffollowingnode7isingroupAR2=Thenumbersoffollowingnode8isingroupBThenumbersoffollowingnode9isingroupBThenumbersoffollowingnode10isingroupBThenumbersoffollowingnode11isingroupBThenumbersoffollowingnode8isingroupBThenumbersoffollowingnode9isingroupBThenumbersoffollowingnode10isingroupBThenumbersoffollowingnode11isingroupBIhenumbersoffollowingnode12isingroupE將上述截圖的結果轉換為用例圖如下:從圖三中可以看出，上述算法完美的把成員進行了劃分，也就是我們之前在所說的A、B組。所以驗證的結果還是比較滿意。現在我們重新組織一下實驗室的人的組織結構的到一下的網絡拓撲：192683510412圖四11192683510412圖四11我們重新運行程序得到一下的結果:圖五圖五我們從圖五可以看到原先5號成員是屬于A組，但是經過人員的調動，他現在被劃分到B組中去，這也和實際中的比較一致。當然如果我們有另外的一種情況，原先實驗室的A、B組被合為一組來做一個比較大的項目，這樣的話應該不會有可能的分組才對，所以我們用上述的算法進行再次的驗證，這樣的話實驗室人員的組織拓撲結構如下圖所示：124圖六124圖六而通過上述算法我們得到圖七的網絡拓撲劃分:我們發現在圖七中上述的算法還是把網絡劃分為兩個組，其實這并不是算法本身的問題，而是我們所涉及的這個實驗室組的模型并不完善，而在相對完善的模型中我們可以看到如果網絡是一個統一的整體，那么算法是拒絕分割的，這也是本算法一個比較重要的方面。4、總結、在這篇文章中，我們討論了在社交網絡群落結構檢測方面的一些問題，通過尋找模塊度的最大值來得到網絡的劃分，我們也展示了這個問題是如何通過轉化為與模塊度矩陣的特征向量和特征值相關的問題的，在文章的最后，我們通過一個實驗室成員的例子對我們所提出的算法進行了一些測試，測試的結果還是非常滿意，在最后的一個例子中，是實驗數據而不是算法的問題導致了結果的不正確,在真實的實驗性數據下，所得到的結果應該還是非常理想的。我們可以將這個算法用于真實世界的網絡結構中。備注：這篇論文是M.E.J.Newman在2006發表的ModularityandCommunitystructureinnetworks的驗證性實驗，在論文中M.E.J.Newman首次提出通過模塊度的思想對社交網絡進行劃分，而在本論文中只是通過一些實例對模塊度的相關算法進行驗證。5、參考文獻:M.E.J.Newman(2006)ModularityandCommunitystructureinnetworks.殷劍宏吳開亞(2005)圖論及其算法26-35同濟大學數學系線性代數(第五版)Albert, R &Baraba#si,A.-L. (2002) Rev.Mod.Phys. 74, 47- 97.Dorogovtsev,S.N. &