1、復雜網絡中的集團結構北京師范大學系統科學學院綱要綱要l實際網絡中的社團結構l社團結構定義l檢驗算法的網絡與Q函數l探索社團結構的方法l算法的評價以及加權網絡的聚類方法l一個具體工作（基于比較性定義下的聚類方法） 實際系統中的社團結構實際系統中的社團結構Collaboration network between scientists working at the Santa Fe Institute. The colors indicate high level communities obtained by the algorithm of Girvan and Newman and corr

2、espond quite closely to research divisions of the institute.Zacharys karate club, a standard benchmark in community detection. The colors correspond to the best partition found by optimizing the modularity of Newman and Girvan.Community structure in technological networks.Sle of the web graph consis

3、ting of the pages of a web site and their mutual hyperlinks, which are directed. Communities, indicated by the colors, were detected with the algorithmof Girvan and Newman, by neglecting thedirectedness of the edges.Best division of econophysicists collaboration network, with the divisions detected

4、by GN algorithm represented by different colors and numbers.Community structure in protein-protein interaction networks. The graph pictures the interactions between proteins in cancerous cells of a rat. Communities, labeled by colors, were detected with the k-clique percolation method by Palla et al

5、.l人際關系網l引文網lWWW網l新陳代謝網l食物鏈網社團結構和功能之間的關系社團結構的定義社團結構的定義 M. E. J. Newman, Detecting community structure in networks. Eur. Phys. J. B 38, 321-330 (202X). 社團結構的數學描述社團結構的數學描述lClique - Complete graphlk-core - subgraph in which each node is adjacent to at least a minimum number, k, of the other nodes in the

6、 subgraph.lK-Clique CommunitylLS-SetlAn LS-set is a set of nodes such that each of its proper subsets has more ties to its complement within the set than outside.社團結構的比較性定義社團結構的比較性定義檢驗算法的網絡及檢驗算法的網絡及Q函數函數l人工網絡lGN BenchmarklLFR benchmarkl一些實證網絡（已知社團結構） 檢驗算法的網絡檢驗算法的網絡GN經典人造網經典人造網l常用的人造網是由128個頂點構成的網絡，這1

7、28個頂點被平均分成四份，構成四個社團，每個社團包含32個頂點。每個頂點度的期望值為16，Zin表示頂點與社團內部頂點連邊數目的期望值，Zout表示頂點與社團外頂點連邊數目的期望值，從而Zin + Zout =16.lZout越小說明頂點與社團外部的連接越少，網絡的社團結構越明顯； Zout越大說明網絡越混亂，社團結構越不明顯。l對于Zout值大的網絡還能夠基本正確的對網絡進行劃分的算法，在實際應用中適用范圍更廣，價值更大。LFR benchmarklLFR benchmark is a generalization of the GN benchmark to heterogeneous g

8、roup sizes and graph degree distribution. Groups are also a priori fixed with the degrees and the community sizes following a power-like distribution. As before, nodes have kin connections within its own group and kout edges linking elsewhere.檢驗算法的一些實際網絡檢驗算法的一些實際網絡l空手道俱樂部網（34個點，78條邊）l科學家合作網（物理學家、經濟物

9、理學、桑塔菲研究所） l美國大學足球賽季網（115個點，616次常規賽）l猴子網（16個點）已知社團結構，便于比較算法的好壞。評價函數評價函數-Modularity含義是：網絡中連接社團內部頂點間的邊的比例與擁有相同社團結構但是頂點間隨機連接的網絡中連接社團內部頂點間的邊的比例的期望值的差值。對Q函數的質疑探測集團結構的基本方法探測集團結構的基本方法尋找社團結構的方法尋找社團結構的方法l基于網絡拓撲結構lGN algorithm based on edge betweenness： M. Girvan, M. E. J. Newman PNAS 99 7821(202X)lSpectral a

10、nalysis； L. Donetti, M. A. Munoz J. Stat. Mech. (202X) P10012l基于網絡上的動力學lPotts Model；J. Reichardt, S. Bornhold, Phys Rev Lett. 93 (202X) 218701lRandom Walk：, ，cond-mat/0412368 ; H. ZhoulCircuits：F. Wu, B.A. Huberman, Eur. Phys. J. B 38 (202X) 331lQ函數優化lExtremal Optimization：J. Duch A. Arenas, Phys Re

11、v E. 72 (202X) 02710lNewmans fast algorithm； M. E. J. Newman, Phys Rev E. 69 (202X) 066133l1、層次聚類法、層次聚類法l根據頂點間的距離或相似程度劃分網絡中的社團。l具體過程為： 1 定義兩點間的距離或相似度，社團與社團間的距離或相似度； 2 將每個頂點視為一個社團，并根據定義計算社團間的距離或相似度； 3 將距離最近的或相似度最高的社團合并，形成新的社團，重新計算社團間的距離或相似度； 4 重復第3步操作，直到網絡中的所有頂點被歸入一個社團為止。結構等價定義頂點間的相似度l結構等價：如果一個頂點與網絡中

12、其余頂點的連接方式和另一頂點與網絡中其余頂點的連接方式完全相同，則這兩個頂點結構等價。例如在人際關系網中，如果兩個人的朋友完全相同，則這兩個人就是結構等價的。l用歐幾里德距離度量衡量結構等價。頂點i，j的距離為l此距離等于0時，兩頂點結構等價。 其他距離及相似度的定義可參見 Mika Gutafsson, Comparison and validation of community structures in complex networks. Physica A 367(202X)559-576 M. Girvan, E. Newman, Community structure in soc

13、ial and biological networks, PNAS99(12)(202X)7821-7826層次聚類法層次聚類法l社團與社團間的距離可以采用最短距離法、最長距離法或平均距離法。l層次距離的過程可以用樹狀圖表示2、GN算法算法lGirvan和Newman提出的分裂算法已經成為探索網絡社團結構的一種經典算法，簡稱GN算法。 l由網絡中社團的定義可知，所謂社團就是指其內部頂點的連接稠密，而與其他社團內的頂點連接稀疏。這就意味著社團與社團之間存在聯系的通道比較少，并且要想從一個社團到另一個社團，至少要通過這些通道中的一條。如果能找到這些重要的通道，并將它們移除，那么網絡就自然而然的分成

14、了各個社團。 l用最短路徑邊介數標記每條邊對連通性的重要程度。GN算法算法l最短路徑邊介數的定義為：找出每對頂點間的最短路徑，計算每條邊被多少條最短路徑通過，這個值就是這條邊的最短路徑邊介數。lGN算法的具體過程： 計算網絡中各條邊的邊介數； 找出邊介數最大的邊，并將它移除（如果最大邊介數的邊不唯一，那么既可以隨機挑選一條邊斷開也可以將這些邊同時斷開）； 重新計算網絡中剩余各條邊的邊介數； 重復第、步，直到網絡中所有的邊都被移除。GN算法與算法與Q值值l最優社團劃分的選擇3、 邊集聚系數法邊集聚系數法l邊集聚系數：一條邊的集聚系數等于網絡中利用這條邊構成的三角形的個數除以利用這條邊潛在可以構成

15、三角形的個數。l連接i，j兩點的邊的集聚系數表示為：l連接不同社團的點的邊，被較少的三角形包含，或者根本不包含于任何三角形。從而邊集聚系數就小。然而社團內部由于有比較稠密的邊，所以應該包含較多的三角形，因此連接集團內部的點的邊的邊集聚系數就大。邊集聚系數法邊集聚系數法l修正的邊集聚系數：l對于加權網其邊集聚系數為：l推廣到更大的環：邊集聚系數法邊集聚系數法l具體過程： 1、確定g值，根據邊集聚系數的定義，計算每條邊的集聚系數； 2、斷開邊集聚系數最小的邊； 3、重新計算每條邊的集聚系數； 重復2、3過程，直到每條邊都被斷開為止。4、優化算法、優化算法貪婪算法貪婪算法l直接以最大化Q函數值為目標

16、，探索網絡中的社團。由此產生一類新的算法優化算法l貪婪算法的具體步驟：(1)初始時將網絡中每個頂點都視為一個社團，每個社團內只有一個頂點。即如果網絡中有n個頂點，則有n個社團。(2)兩兩合并社團，并計算社團合并所產生的Q值的變化量。選擇使得Q值增加最大（或減少最小）的方式進行合并。(3)重復步驟(2)的操作，直到所有頂點被歸于一個社團為止。網絡的最優劃分為Q函數最大值所對應的劃分方式。5、優化算法、優化算法EO算法算法l極值優化算法的基本思想：通過得到局部變量的極值，達到全局變量的極值。l全局變量：l局部變量：一個頂點對整體值的貢獻l標準化的局部變量，也稱適合度：優化算法優化算法l算法的具體過

17、程1、將網絡中的點隨機的分成等大的兩部分，連通的部分構成社團。2、計算每個節點的適合度，將適合度最低的點從一部分移動到另一部分，計算全局Q值，并重新計算每點的適合度。3、重復上述過程直到Q值最大為止。斷開兩部分之間的所有的邊。4、對每一子部分重復1-3過程，直到Q值不能進一步提高為止。6、譜分析算法、譜分析算法l主要思想：分析由連接矩陣形成的拉普拉斯矩陣(Laplacian Matrix)或標準矩陣(Normal Matrix)的特征值特征向量。l以標準矩陣的分析為例l所謂標準矩陣，是由網絡的連接矩陣和一個對角矩陣的逆矩陣構成的。對角矩陣中的元素是每個頂點的度值，表示網絡中頂點的個數。由于標準

18、矩陣行的標準化，標準矩陣總有最大的特征值等于1，以及與之對應的特征向量（1、1、1）。l在對社團化明顯的網絡的分析中發現，如果網絡自然呈現m個社團，則標準矩陣就有m-1個十分接近1的特征值，而其余的特征值則有較大的距離。最大的特征值所對應的特征向量有一個特性：在同一個社團中的頂點所對應的值較為接近。因此，特征向量中元素的值呈現階梯狀分布，并且階梯的級數與社團的個數相匹配。圖 頂點0-6號為一個社團，頂點7-12號為一個社團，頂點13-18號為一個社團。圖 橫坐標表示頂點的編號，縱坐標表示特征向量中頂點對應的數值。可見0-6號的數值比較接近，7-12號的數值比較接近，13-18號的數值比較接近。

19、l同樣的方法也可以對拉普拉斯矩陣進行分析。差別在于，拉普拉斯矩陣總存在平庸的特征值0，考察的標準是大于0的最小的特征值及其對應的特征向量。 算法的評價以及加權網絡的聚類方法算法的評價以及加權網絡的聚類方法劃分結果的比較方法劃分結果的比較方法l正確劃分率比較法l共同信息比較法lD函數比較法l準確度 （accuracy） 計算得到的集團與已知集團比較l精確度 （precision） 在同一個網絡上多次計算得到的多組集團間的兩兩比較 Ying Fan, Menghui Li, et al, Accuracy and Precision of Methods for Community Identif

20、ication in Weighted Networks, Physica A.l算法的復雜度（complexity）評價方法評價方法加權網上的社團結構加權網上的社團結構l算法的推廣l權重的影響M. E. J. Newman，Phys. Rev. E. 70(202X) 056131聚類算法聚類算法 -WGN算法算法l基于網絡拓撲結構， 邊介數算法l根據無權網計算邊介數值(Link Betweenness) bij計算加權網中邊介數值 ，即Bij= bij/wij；l刪除介數值最高的邊； M. E. J. Newman，Phys. Rev. E. 70(202X) 056131聚類算法聚類算法 -極值優化極值優化算法（算法（WEO）l隨機把網絡劃分為節點數相同的兩個集團；l把對目標函數貢