復(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實(shí)際網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)l社團(tuán)結(jié)構(gòu)定義l檢驗(yàn)算法的網(wǎng)絡(luò)與Q函數(shù)l探索社團(tuán)結(jié)構(gòu)的方法l算法的評(píng)價(jià)以及加權(quán)網(wǎng)絡(luò)的聚類方法l一個(gè)具體工作（基于比較性定義下的聚類方法） 實(shí)際系統(tǒng)中的社團(tuán)結(jié)構(gòu)實(shí)際系統(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)的比較性定義檢驗(yàn)算法的網(wǎng)絡(luò)及檢驗(yàn)算法的網(wǎng)絡(luò)及Q函數(shù)函數(shù)l人工網(wǎng)絡(luò)lGN BenchmarklLFR benchmarkl一些實(shí)證網(wǎng)絡(luò)（已知社團(tuán)結(jié)構(gòu)） 檢驗(yàn)算法的網(wǎng)絡(luò)檢驗(yàn)算法的網(wǎng)絡(luò)GN經(jīng)典人造網(wǎng)經(jīng)典人造網(wǎng)l常用的人造網(wǎng)是由128個(gè)頂點(diǎn)構(gòu)成的網(wǎng)絡(luò)，這1

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

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

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

14、了各個(gè)社團(tuán)。 l用最短路徑邊介數(shù)標(biāo)記每條邊對(duì)連通性的重要程度。GN算法算法l最短路徑邊介數(shù)的定義為：找出每對(duì)頂點(diǎn)間的最短路徑，計(jì)算每條邊被多少條最短路徑通過，這個(gè)值就是這條邊的最短路徑邊介數(shù)。lGN算法的具體過程： 計(jì)算網(wǎng)絡(luò)中各條邊的邊介數(shù)； 找出邊介數(shù)最大的邊，并將它移除（如果最大邊介數(shù)的邊不唯一，那么既可以隨機(jī)挑選一條邊斷開也可以將這些邊同時(shí)斷開）； 重新計(jì)算網(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)成的三角形的個(gè)數(shù)除以利用這條邊潛在可以構(gòu)成

15、三角形的個(gè)數(shù)。l連接i，j兩點(diǎn)的邊的集聚系數(shù)表示為：l連接不同社團(tuán)的點(diǎn)的邊，被較少的三角形包含，或者根本不包含于任何三角形。從而邊集聚系數(shù)就小。然而社團(tuán)內(nèi)部由于有比較稠密的邊，所以應(yīng)該包含較多的三角形，因此連接集團(tuán)內(nèi)部的點(diǎn)的邊的邊集聚系數(shù)就大。邊集聚系數(shù)法邊集聚系數(shù)法l修正的邊集聚系數(shù)：l對(duì)于加權(quán)網(wǎng)其邊集聚系數(shù)為：l推廣到更大的環(huán)：邊集聚系數(shù)法邊集聚系數(shù)法l具體過程： 1、確定g值，根據(jù)邊集聚系數(shù)的定義，計(jì)算每條邊的集聚系數(shù)； 2、斷開邊集聚系數(shù)最小的邊； 3、重新計(jì)算每條邊的集聚系數(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)初始時(shí)將網(wǎng)絡(luò)中每個(gè)頂點(diǎn)都視為一個(gè)社團(tuán)，每個(gè)社團(tuán)內(nèi)只有一個(gè)頂點(diǎn)。即如果網(wǎng)絡(luò)中有n個(gè)頂點(diǎn)，則有n個(gè)社團(tuán)。(2)兩兩合并社團(tuán)，并計(jì)算社團(tuán)合并所產(chǎn)生的Q值的變化量。選擇使得Q值增加最大（或減少最?。┑姆绞竭M(jìn)行合并。(3)重復(fù)步驟(2)的操作，直到所有頂點(diǎn)被歸于一個(gè)社團(tuán)為止。網(wǎng)絡(luò)的最優(yōu)劃分為Q函數(shù)最大值所對(duì)應(yīng)的劃分方式。5、優(yōu)化算法、優(yōu)化算法EO算法算法l極值優(yōu)化算法的基本思想：通過得到局部變量的極值，達(dá)到全局變量的極值。l全局變量：l局部變量：一個(gè)頂點(diǎn)對(duì)整體值的貢獻(xiàn)l標(biāo)準(zhǔn)化的局部變量，也稱適合度：優(yōu)化算法優(yōu)化算法l算法的具體過

17、程1、將網(wǎng)絡(luò)中的點(diǎn)隨機(jī)的分成等大的兩部分，連通的部分構(gòu)成社團(tuán)。2、計(jì)算每個(gè)節(jié)點(diǎn)的適合度，將適合度最低的點(diǎn)從一部分移動(dòng)到另一部分，計(jì)算全局Q值，并重新計(jì)算每點(diǎn)的適合度。3、重復(fù)上述過程直到Q值最大為止。斷開兩部分之間的所有的邊。4、對(duì)每一子部分重復(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è)對(duì)角矩陣的逆矩陣構(gòu)成的。對(duì)角矩陣中的元素是每個(gè)頂點(diǎn)的度值，表示網(wǎng)絡(luò)中頂點(diǎn)的個(gè)數(shù)。由于標(biāo)準(zhǔn)

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

19、l同樣的方法也可以對(duì)拉普拉斯矩陣進(jìn)行分析。差別在于，拉普拉斯矩陣總存在平庸的特征值0，考察的標(biāo)準(zhǔn)是大于0的最小的特征值及其對(duì)應(yīng)的特征向量。 算法的評(píng)價(jià)以及加權(quán)網(wǎng)絡(luò)的聚類方法算法的評(píng)價(jià)以及加權(quán)網(wǎng)絡(luò)的聚類方法劃分結(jié)果的比較方法劃分結(jié)果的比較方法l正確劃分率比較法l共同信息比較法lD函數(shù)比較法l準(zhǔn)確度 （accuracy） 計(jì)算得到的集團(tuán)與已知集團(tuán)比較l精確度 （precision） 在同一個(gè)網(wǎng)絡(luò)上多次計(jì)算得到的多組集團(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）評(píng)價(jià)方法評(píng)價(jià)方法加權(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)計(jì)算邊介數(shù)值(Link Betweenness) bij計(jì)算加權(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隨機(jī)把網(wǎng)絡(luò)劃分為節(jié)點(diǎn)數(shù)相同的兩個(gè)集團(tuán)；l把對(duì)目標(biāo)函數(shù)貢