復(fù)雜網(wǎng)絡(luò)中的集團(tuán)結(jié)構(gòu)北京師范大學(xué)系統(tǒng)科學(xué)學(xué)院

1、復(fù)雜網(wǎng)絡(luò)中的集團(tuán)結(jié)構(gòu)北京師范大學(xué)系統(tǒng)科學(xué)學(xué)院綱要綱要l實際網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)l社團(tuán)結(jié)構(gòu)定義l檢驗算法的網(wǎng)絡(luò)與Q函數(shù)l探索社團(tuán)結(jié)構(gòu)的方法l算法的評價以及加權(quán)網(wǎng)絡(luò)的聚類方法l一個具體工作（基于比較性定義下的聚類方法） 實際系統(tǒng)中的社團(tuán)結(jié)構(gòu)實際系統(tǒng)中的社團(tuán)結(jié)構(gòu)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人際關(guān)系網(wǎng)l引文網(wǎng)lWWW網(wǎng)l新陳代謝網(wǎng)l食物鏈網(wǎng)社團(tuán)結(jié)構(gòu)和功能之間的關(guān)系社團(tuán)結(jié)構(gòu)的定義社團(tuán)結(jié)構(gòu)的定義 M. E. J. Newman, Detecting community structure in networks. Eur. Phys. J. B 38, 321-330 (202X). 社團(tuán)結(jié)構(gòu)的數(shù)學(xué)描述社團(tuán)結(jié)構(gòu)的數(shù)學(xué)描述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.社團(tuán)結(jié)構(gòu)的比較性定義社團(tuán)結(jié)構(gòu)的比較性定義檢驗算法的網(wǎng)絡(luò)及檢驗算法的網(wǎng)絡(luò)及Q函數(shù)函數(shù)l人工網(wǎng)絡(luò)lGN BenchmarklLFR benchmarkl一些實證網(wǎng)絡(luò)（已知社團(tuán)結(jié)構(gòu)） 檢驗算法的網(wǎng)絡(luò)檢驗算法的網(wǎng)絡(luò)GN經(jīng)典人造網(wǎng)經(jīng)典人造網(wǎng)l常用的人造網(wǎng)是由128個頂點構(gòu)成的網(wǎng)絡(luò)，這1

7、28個頂點被平均分成四份，構(gòu)成四個社團(tuán)，每個社團(tuán)包含32個頂點。每個頂點度的期望值為16，Zin表示頂點與社團(tuán)內(nèi)部頂點連邊數(shù)目的期望值，Zout表示頂點與社團(tuán)外頂點連邊數(shù)目的期望值，從而Zin + Zout =16.lZout越小說明頂點與社團(tuán)外部的連接越少，網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)越明顯； Zout越大說明網(wǎng)絡(luò)越混亂，社團(tuán)結(jié)構(gòu)越不明顯。l對于Zout值大的網(wǎng)絡(luò)還能夠基本正確的對網(wǎng)絡(luò)進(jìn)行劃分的算法，在實際應(yīng)用中適用范圍更廣，價值更大。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.檢驗算法的一些實際網(wǎng)絡(luò)檢驗算法的一些實際網(wǎng)絡(luò)l空手道俱樂部網(wǎng)（34個點，78條邊）l科學(xué)家合作網(wǎng)（物理學(xué)家、經(jīng)濟(jì)物

9、理學(xué)、桑塔菲研究所） l美國大學(xué)足球賽季網(wǎng)（115個點，616次常規(guī)賽）l猴子網(wǎng)（16個點）已知社團(tuán)結(jié)構(gòu)，便于比較算法的好壞。評價函數(shù)評價函數(shù)-Modularity含義是：網(wǎng)絡(luò)中連接社團(tuán)內(nèi)部頂點間的邊的比例與擁有相同社團(tuán)結(jié)構(gòu)但是頂點間隨機連接的網(wǎng)絡(luò)中連接社團(tuán)內(nèi)部頂點間的邊的比例的期望值的差值。對Q函數(shù)的質(zhì)疑探測集團(tuán)結(jié)構(gòu)的基本方法探測集團(tuán)結(jié)構(gòu)的基本方法尋找社團(tuán)結(jié)構(gòu)的方法尋找社團(tuán)結(jié)構(gòu)的方法l基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)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基于網(wǎng)絡(luò)上的動力學(xué)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函數(shù)優(yōu)化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根據(jù)頂點間的距離或相似程度劃分網(wǎng)絡(luò)中的社團(tuán)。l具體過程為： 1 定義兩點間的距離或相似度，社團(tuán)與社團(tuán)間的距離或相似度； 2 將每個頂點視為一個社團(tuán)，并根據(jù)定義計算社團(tuán)間的距離或相似度； 3 將距離最近的或相似度最高的社團(tuán)合并，形成新的社團(tuán)，重新計算社團(tuán)間的距離或相似度； 4 重復(fù)第3步操作，直到網(wǎng)絡(luò)中的所有頂點被歸入一個社團(tuán)為止。結(jié)構(gòu)等價定義頂點間的相似度l結(jié)構(gòu)等價：如果一個頂點與網(wǎng)絡(luò)中

12、其余頂點的連接方式和另一頂點與網(wǎng)絡(luò)中其余頂點的連接方式完全相同，則這兩個頂點結(jié)構(gòu)等價。例如在人際關(guān)系網(wǎng)中，如果兩個人的朋友完全相同，則這兩個人就是結(jié)構(gòu)等價的。l用歐幾里德距離度量衡量結(jié)構(gòu)等價。頂點i，j的距離為l此距離等于0時，兩頂點結(jié)構(gòu)等價。 其他距離及相似度的定義可參見 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社團(tuán)與社團(tuán)間的距離可以采用最短距離法、最長距離法或平均距離法。l層次距離的過程可以用樹狀圖表示2、GN算法算法lGirvan和Newman提出的分裂算法已經(jīng)成為探索網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的一種經(jīng)典算法，簡稱GN算法。 l由網(wǎng)絡(luò)中社團(tuán)的定義可知，所謂社團(tuán)就是指其內(nèi)部頂點的連接稠密，而與其他社團(tuán)內(nèi)的頂點連接稀疏。這就意味著社團(tuán)與社團(tuán)之間存在聯(lián)系的通道比較少，并且要想從一個社團(tuán)到另一個社團(tuán)，至少要通過這些通道中的一條。如果能找到這些重要的通道，并將它們移除，那么網(wǎng)絡(luò)就自然而然的分成

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

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

16、，探索網(wǎng)絡(luò)中的社團(tuán)。由此產(chǎn)生一類新的算法優(yōu)化算法l貪婪算法的具體步驟：(1)初始時將網(wǎng)絡(luò)中每個頂點都視為一個社團(tuán)，每個社團(tuán)內(nèi)只有一個頂點。即如果網(wǎng)絡(luò)中有n個頂點，則有n個社團(tuán)。(2)兩兩合并社團(tuán)，并計算社團(tuán)合并所產(chǎn)生的Q值的變化量。選擇使得Q值增加最大（或減少最?。┑姆绞竭M(jìn)行合并。(3)重復(fù)步驟(2)的操作，直到所有頂點被歸于一個社團(tuán)為止。網(wǎng)絡(luò)的最優(yōu)劃分為Q函數(shù)最大值所對應(yīng)的劃分方式。5、優(yōu)化算法、優(yōu)化算法EO算法算法l極值優(yōu)化算法的基本思想：通過得到局部變量的極值，達(dá)到全局變量的極值。l全局變量：l局部變量：一個頂點對整體值的貢獻(xiàn)l標(biāo)準(zhǔn)化的局部變量，也稱適合度：優(yōu)化算法優(yōu)化算法l算法的具體過

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

18、矩陣行的標(biāo)準(zhǔn)化，標(biāo)準(zhǔn)矩陣總有最大的特征值等于1，以及與之對應(yīng)的特征向量（1、1、1）。l在對社團(tuán)化明顯的網(wǎng)絡(luò)的分析中發(fā)現(xiàn)，如果網(wǎng)絡(luò)自然呈現(xiàn)m個社團(tuán)，則標(biāo)準(zhǔn)矩陣就有m-1個十分接近1的特征值，而其余的特征值則有較大的距離。最大的特征值所對應(yīng)的特征向量有一個特性：在同一個社團(tuán)中的頂點所對應(yīng)的值較為接近。因此，特征向量中元素的值呈現(xiàn)階梯狀分布，并且階梯的級數(shù)與社團(tuán)的個數(shù)相匹配。圖 頂點0-6號為一個社團(tuán)，頂點7-12號為一個社團(tuán)，頂點13-18號為一個社團(tuán)。圖 橫坐標(biāo)表示頂點的編號，縱坐標(biāo)表示特征向量中頂點對應(yīng)的數(shù)值?？梢?-6號的數(shù)值比較接近，7-12號的數(shù)值比較接近，13-18號的數(shù)值比較接近。

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

20、ication in Weighted Networks, Physica A.l算法的復(fù)雜度（complexity）評價方法評價方法加權(quán)網(wǎng)上的社團(tuán)結(jié)構(gòu)加權(quán)網(wǎng)上的社團(tuán)結(jié)構(gòu)l算法的推廣l權(quán)重的影響M. E. J. Newman，Phys. Rev. E. 70(202X) 056131聚類算法聚類算法 -WGN算法算法l基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)， 邊介數(shù)算法l根據(jù)無權(quán)網(wǎng)計算邊介數(shù)值(Link Betweenness) bij計算加權(quán)網(wǎng)中邊介數(shù)值 ，即Bij= bij/wij；l刪除介數(shù)值最高的邊； M. E. J. Newman，Phys. Rev. E. 70(202X) 056131聚類算法聚類算法 -極值優(yōu)化極值優(yōu)化算法（算法（WEO）l隨機把網(wǎng)絡(luò)劃分為節(jié)點數(shù)相同的兩個集團(tuán)；l把對目標(biāo)函數(shù)貢