復(fù)雜網(wǎng)絡(luò)社區(qū)提取綜述

復(fù)雜網(wǎng)絡(luò)論文匯報(bào)2013.10網(wǎng)絡(luò)基本概念復(fù)雜網(wǎng)絡(luò)及其特性社區(qū)提取及一些經(jīng)典算法網(wǎng)絡(luò)傳統(tǒng)的對(duì)網(wǎng)絡(luò)的研究最早起源于著名的歐拉七橋問(wèn)題。許多真實(shí)系統(tǒng)都可以用網(wǎng)絡(luò)的形式加以描述，一個(gè)典型的網(wǎng)絡(luò)是由許多結(jié)點(diǎn)與連接結(jié)點(diǎn)之間的邊組成的。結(jié)點(diǎn)代表系統(tǒng)中的個(gè)體，邊則表示結(jié)點(diǎn)之間的作用關(guān)系。通常是當(dāng)兩個(gè)節(jié)點(diǎn)之間具有某種特定的關(guān)系時(shí)連一條邊,反之則不連邊.有邊相連的兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中被看作是相鄰的.我們把網(wǎng)絡(luò)不依賴于節(jié)點(diǎn)的具體位置和邊的具體形態(tài)就能表現(xiàn)出來(lái)的性質(zhì)叫做網(wǎng)絡(luò)的拓?fù)湫再|(zhì),相應(yīng)的結(jié)構(gòu)叫做網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).基本概念圖（網(wǎng)絡(luò)）

由若干個(gè)不同頂點(diǎn)與連接其中某些頂點(diǎn)的邊所組成的圖形就稱為圖。（頂點(diǎn)的位置以及邊的曲直都是無(wú)關(guān)緊要的，而且也是沒(méi)有假定這些頂點(diǎn)和邊都要在一個(gè)平面內(nèi)，只關(guān)心頂點(diǎn)的多少和這些邊是連接哪些頂點(diǎn)的），通常用大寫字母G表示圖，記作G=(V,E)。其中頂點(diǎn)集合和邊的集合分別用V(G)和E(G)表示。同時(shí)集合E(G)中的每一條邊都與集合V(G)中的一對(duì)結(jié)點(diǎn)相對(duì)應(yīng)，另外由一條邊相互連接的兩個(gè)結(jié)點(diǎn)稱之為相鄰節(jié)點(diǎn)。V(G)中的元素稱為頂點(diǎn)（Vertex），頂點(diǎn)個(gè)數(shù)稱為圖的階（Order）。E(G)中的元素稱為邊（Edge），邊的個(gè)數(shù)稱為圖的邊數(shù)（Size）（規(guī)模）。有向圖和無(wú)向圖如果任意的結(jié)點(diǎn)對(duì)(i,j)和(j,i)對(duì)應(yīng)著同一條邊,那么這種圖就被稱為無(wú)向圖，即(i,j)=(j,i)。若(i,j)≠(j,i)，則為有向圖。對(duì)應(yīng)有向網(wǎng)絡(luò)和無(wú)向網(wǎng)絡(luò)。路徑、跡、路在圖G(V,E)中，若從頂點(diǎn)vi出發(fā)，沿著一些邊經(jīng)過(guò)一些頂點(diǎn)vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj，則稱頂點(diǎn)序列(vi,vp1,vp2,…,vpm,vj)為從頂點(diǎn)vi到頂點(diǎn)vj的一條路徑（Path，或稱為通路），其中(vi,vp1),(vp1,vp2),…,(vpm,vj)為圖G中的邊。如果各邊都不相同，則稱該路徑為圖G的一個(gè)跡。頂點(diǎn)互不相同的跡稱為路。圖（網(wǎng)絡(luò)）的存儲(chǔ)表示鄰接矩陣

除了記錄各個(gè)頂點(diǎn)信息的頂點(diǎn)數(shù)組外，還表示各個(gè)頂點(diǎn)之間關(guān)系的矩陣，稱為鄰接矩陣（AdjacencyMatrix）。

對(duì)于一個(gè)無(wú)權(quán)無(wú)向的網(wǎng)絡(luò)來(lái)說(shuō),在它的鄰接矩陣W的表示方法中,如果網(wǎng)絡(luò)中的節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在連接的邊,那么元素Wij=1,如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間沒(méi)有邊相連接則Wij=0,則由此可以知道該鄰接矩陣是一個(gè)對(duì)稱矩陣。

對(duì)于有向網(wǎng)絡(luò),鄰接矩陣則代表著某個(gè)節(jié)點(diǎn)的出入度數(shù)目,其中第i行上非零的列數(shù)代表節(jié)點(diǎn)i的出度,第j列上非零的行數(shù)代表節(jié)點(diǎn)j的入度;對(duì)于加權(quán)網(wǎng)絡(luò)中,如果結(jié)點(diǎn)i和結(jié)點(diǎn)j之間存在一條邊,那么元素Wij的值等于節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的相應(yīng)的權(quán)重的值。laplace矩陣（度矩陣減鄰接矩陣）

路徑的長(zhǎng)度、距離、平均路徑長(zhǎng)度、直徑、

路徑中邊的數(shù)目通常稱為路徑的長(zhǎng)度。單源最短路徑

就是固定一個(gè)頂點(diǎn)，將此頂點(diǎn)當(dāng)作源點(diǎn)，求源點(diǎn)到其他各個(gè)頂點(diǎn)的最短路徑。節(jié)點(diǎn)的度結(jié)點(diǎn)i的度定義為與這個(gè)結(jié)點(diǎn)i相連接的其它結(jié)點(diǎn)的數(shù)目。換句話說(shuō),也就是與節(jié)點(diǎn)i相連接的邊的數(shù)目。度有入度和出度之分，節(jié)點(diǎn)的度描述節(jié)點(diǎn)性質(zhì)的一個(gè)特別重要的概念，在網(wǎng)絡(luò)中,如果某個(gè)節(jié)點(diǎn)的度很大,說(shuō)明這個(gè)結(jié)點(diǎn)對(duì)于整個(gè)網(wǎng)絡(luò)來(lái)說(shuō)非常重要。（核心節(jié)點(diǎn)算法就是先找出度數(shù)最大的點(diǎn)）

度分布網(wǎng)絡(luò)中的度分布則是描述網(wǎng)絡(luò)性質(zhì)的一個(gè)非常重要的統(tǒng)計(jì)量，無(wú)向網(wǎng)絡(luò)中的節(jié)點(diǎn)的度的分布情況可以用分布函數(shù)P(k)來(lái)表示,它所代表的含義是隨機(jī)地選擇網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)度為k的概率，換句話說(shuō)就是在網(wǎng)絡(luò)中度為k的節(jié)點(diǎn)數(shù)目總數(shù)占網(wǎng)絡(luò)中所有節(jié)點(diǎn)總數(shù)的比例。對(duì)于有向網(wǎng)絡(luò)，其度分布還可細(xì)致地分為網(wǎng)絡(luò)的入度分布(in-degreedistribution)和出度分布(out-degreedistribution)。隨機(jī)網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)有不同的度分布。介數(shù)（居間中心性）(betweenness)網(wǎng)絡(luò)中的介數(shù)分為節(jié)點(diǎn)介數(shù)和邊介數(shù)。

通常在整個(gè)網(wǎng)絡(luò)中,如果從某一個(gè)節(jié)點(diǎn)沿著最短路徑到達(dá)另外一個(gè)節(jié)點(diǎn)時(shí),一般會(huì)經(jīng)過(guò)若干節(jié)點(diǎn),但是這些節(jié)點(diǎn)的經(jīng)過(guò)次數(shù)不一樣,網(wǎng)絡(luò)中的有些節(jié)點(diǎn)被經(jīng)過(guò)的次數(shù)明顯高于別的節(jié)點(diǎn)經(jīng)過(guò)的次數(shù)，這種現(xiàn)象就有節(jié)點(diǎn)的介數(shù)來(lái)描述。節(jié)點(diǎn)介數(shù)定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過(guò)該節(jié)點(diǎn)的路徑的數(shù)目占最短路徑總數(shù)的比例.邊介數(shù)定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過(guò)該邊的路徑的數(shù)目占最短路徑總數(shù)的比例.介數(shù)反映了相應(yīng)的節(jié)點(diǎn)或者邊在整個(gè)網(wǎng)絡(luò)中的作用和影響力，是一個(gè)重要的全局幾何量，具有很強(qiáng)的現(xiàn)實(shí)意義。GN算法中某條邊的邊介數(shù)是指網(wǎng)絡(luò)中通過(guò)這條邊的最短路徑的數(shù)目。

節(jié)點(diǎn)k的介數(shù)的計(jì)算公式為：公式2.4中，Ck(i,j)表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑中經(jīng)過(guò)節(jié)點(diǎn)k的數(shù)目，C(i,j)表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最短路徑的總數(shù)目。邊介數(shù)的定義類似于節(jié)點(diǎn)介數(shù)的定義。聚類系數(shù)（聚集系數(shù)）（簇系數(shù)）

網(wǎng)絡(luò)的聚集系數(shù)表明復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)的聚集情況也就是網(wǎng)絡(luò)的聚集性,換句話說(shuō),就是同一個(gè)節(jié)點(diǎn)的兩個(gè)相鄰節(jié)點(diǎn)仍然是相鄰節(jié)點(diǎn)的幾率有多大,網(wǎng)絡(luò)的聚集系數(shù)反映了網(wǎng)絡(luò)中的局部特性"例如在朋友關(guān)系網(wǎng)絡(luò)中,你的兩個(gè)朋友之間很有可能彼此也是朋友。聚類系數(shù)另一個(gè)圖形化的等價(jià)定義局部集聚系數(shù)：藍(lán)點(diǎn)有三個(gè)鄰接點(diǎn)（白點(diǎn)）。如果三個(gè)白點(diǎn)都相互連接（上圖），那么藍(lán)點(diǎn)的集聚系數(shù)是3÷3=1；如果只有兩點(diǎn)之間相連（中圖，只有一條邊），那么集聚系數(shù)是1/3；如果沒(méi)有兩點(diǎn)是相連的接，那么集聚系數(shù)就是0。貪婪算法（貪心算法）在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。比如k-l算法。一些網(wǎng)絡(luò)演化模型（沒(méi)仔細(xì)看）規(guī)則網(wǎng)絡(luò)簡(jiǎn)介右圖是一種最簡(jiǎn)單的規(guī)則網(wǎng)絡(luò)模型，在其中，N個(gè)節(jié)點(diǎn)排成環(huán)，每個(gè)節(jié)點(diǎn)與其鄰近的m個(gè)節(jié)點(diǎn)連接（這里m=4），很容易得到該網(wǎng)絡(luò)的主要統(tǒng)計(jì)性質(zhì)。度分布：p(k)=1(k=m)或0（k≠m）各點(diǎn)聚類系數(shù)：3/(0.5*4*3)=1/2（鄰接點(diǎn)之間的實(shí)際邊數(shù)比上最大變數(shù)）網(wǎng)絡(luò)的聚類系數(shù)：1/2(與N無(wú)關(guān))平均路徑長(zhǎng)度：復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)p148（沒(méi)看懂）與N成正比。大聚類系數(shù)，大平均路徑長(zhǎng)度。ER隨機(jī)網(wǎng)絡(luò)模型（沒(méi)仔細(xì)看）（1）給定網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)為N。（2）在每一步，任意選擇兩點(diǎn)，以概率p=(2n)/(N(N-1))把它們連邊。其中n是給定的總邊數(shù)（n<0.5*N(N-1)）0.5*N(N-1)是最大可能連邊數(shù)。（3）當(dāng)邊數(shù)達(dá)到n時(shí)停止演化。度分布是泊松分布，聚類系數(shù)與N成反比，平均路徑長(zhǎng)度與㏑N成正比。小聚類系數(shù)，小平均路徑長(zhǎng)度。網(wǎng)絡(luò)理論研究先后經(jīng)歷了三個(gè)階段，分別為規(guī)則網(wǎng)絡(luò)（真實(shí)系統(tǒng)各因素之間的關(guān)系可以用一些規(guī)則的結(jié)構(gòu)表示）、隨機(jī)網(wǎng)絡(luò)（兩個(gè)節(jié)點(diǎn)之間連邊與否不再是確定的事情,而是根據(jù)一個(gè)概率決定，數(shù)學(xué)家把這樣生成的網(wǎng)絡(luò)叫做隨機(jī)網(wǎng)絡(luò)）、復(fù)雜網(wǎng)絡(luò)（錢學(xué)森給出了復(fù)雜網(wǎng)絡(luò)的一個(gè)較嚴(yán)格的定義：具有自組織（自我完善，不斷提高）、自相似（自己與自身的一小部分相似）、吸引子、小世界、無(wú)標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò)）。大多數(shù)真實(shí)網(wǎng)絡(luò)既不是規(guī)則的，也不是隨機(jī)的，而是呈現(xiàn)一定規(guī)律的復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)的研究大致可以描述為三個(gè)密切相關(guān)但又依次深入的方面：大量的真實(shí)網(wǎng)絡(luò)的實(shí)證研究，分析真實(shí)網(wǎng)絡(luò)的統(tǒng)計(jì)特性；構(gòu)建符合真實(shí)網(wǎng)絡(luò)統(tǒng)計(jì)性質(zhì)的網(wǎng)絡(luò)演化模型，研究網(wǎng)絡(luò)的形成機(jī)制和內(nèi)在機(jī)理；研究網(wǎng)絡(luò)上的動(dòng)力學(xué)行為。復(fù)雜網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)的特性大量的實(shí)證研究表明許多真實(shí)世界的網(wǎng)絡(luò)具有三個(gè)基本性質(zhì)：小世界特性(smallworldcharacter)，無(wú)標(biāo)度特性(scale-freecharacter)和社區(qū)結(jié)構(gòu)（community）一、小世界（較小的平均最短距離，六度分隔）小世界特性是指與相同規(guī)模（圖的邊數(shù)）的隨機(jī)網(wǎng)絡(luò)相比，該網(wǎng)絡(luò)具有較小的平均最短距離和較大的簇系數(shù)。把同時(shí)具有較大的族系數(shù)和較小的平均距離等兩個(gè)統(tǒng)計(jì)特征的復(fù)雜網(wǎng)絡(luò),稱為小世界網(wǎng)絡(luò)。WS小世界網(wǎng)絡(luò)模型（沒(méi)仔細(xì)看）小世界網(wǎng)絡(luò)模型的平均路徑長(zhǎng)度類似于ER隨機(jī)網(wǎng)絡(luò)模型，聚類系數(shù)類似于規(guī)則網(wǎng)絡(luò)。從規(guī)則網(wǎng)絡(luò)開(kāi)始，以概率p斷開(kāi)一個(gè)節(jié)點(diǎn),隨機(jī)地從網(wǎng)絡(luò)中選取一個(gè)節(jié)點(diǎn)進(jìn)行連接"即保持邊的一個(gè)端點(diǎn)不變,而另一個(gè)端點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)節(jié)點(diǎn)"如果所選的節(jié)點(diǎn)已經(jīng)與此節(jié)點(diǎn)相連,則再隨機(jī)選擇別的節(jié)點(diǎn)來(lái)重連"。在構(gòu)造過(guò)程中,如p=0則網(wǎng)絡(luò)為規(guī)則網(wǎng)絡(luò),p=1時(shí),則為隨機(jī)網(wǎng)絡(luò)；o<p<1時(shí)網(wǎng)絡(luò)同時(shí)具有大的聚集系數(shù)和小的平均路徑兩個(gè)特征,而這樣的網(wǎng)絡(luò)我們稱之為小世界網(wǎng)絡(luò)。大聚類系數(shù)，小平均路徑長(zhǎng)度。二、無(wú)標(biāo)度（無(wú)尺度）（馬太效應(yīng)，富人窮人）把網(wǎng)絡(luò)的度分布符合冪律分布的網(wǎng)絡(luò),稱為無(wú)標(biāo)度網(wǎng)絡(luò)。冪律分布這一特性，正說(shuō)明了無(wú)尺度網(wǎng)絡(luò)的度分布與一般隨機(jī)網(wǎng)絡(luò)的不同。隨機(jī)網(wǎng)絡(luò)的節(jié)點(diǎn)度分布屬于正態(tài)分布，因此有一個(gè)特征度數(shù)，即大部分節(jié)點(diǎn)的度數(shù)都接近它。無(wú)尺度網(wǎng)絡(luò)的度分布是呈集散分布：大部分的節(jié)點(diǎn)只有比較少的連接，而少數(shù)節(jié)點(diǎn)有大量的連接。由于不存在特征度數(shù)，因此得名“無(wú)尺度”。無(wú)尺度網(wǎng)絡(luò)的特性是：當(dāng)節(jié)點(diǎn)意外失效或改變時(shí)，對(duì)網(wǎng)絡(luò)的影響一般很小，只有很小的概率會(huì)發(fā)生大的影響，但當(dāng)有集散節(jié)點(diǎn)受到影響時(shí)，網(wǎng)絡(luò)受到的影響會(huì)比隨機(jī)網(wǎng)絡(luò)大得多。BA無(wú)標(biāo)度網(wǎng)絡(luò)模型在雙對(duì)數(shù)坐標(biāo)系中冪律分布的圖像呈直線。指數(shù)就是直線的斜率。p(k)~k^-a等價(jià)于logp(k)~-alog(k)（反比關(guān)系）指數(shù)a是直線的斜率。（沒(méi)研究a）三、社區(qū)結(jié)構(gòu)整個(gè)網(wǎng)絡(luò)是由若干個(gè)“社區(qū)"或“組’’構(gòu)成的。每個(gè)社區(qū)內(nèi)部的結(jié)點(diǎn)間的連接相對(duì)非常緊密，但是各個(gè)社區(qū)之間的連接相對(duì)來(lái)說(shuō)卻比較稀疏（網(wǎng)絡(luò)中的頂點(diǎn)可以分成組,組內(nèi)連接稠密而組間連接稀疏）。我們將復(fù)雜網(wǎng)絡(luò)的這種結(jié)構(gòu)特征稱之為復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)或社區(qū)結(jié)構(gòu)。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)重要的特性，社區(qū)也被稱為簇，大量研究表明網(wǎng)絡(luò)是由各種不同類型的節(jié)點(diǎn)構(gòu)成的，一般情況下，在不同類型的節(jié)點(diǎn)間存在較少的邊，而在相同類型的節(jié)點(diǎn)間會(huì)有較多的邊。位于一個(gè)子圖內(nèi)的節(jié)點(diǎn)和邊組成一個(gè)社團(tuán)。復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)還有一個(gè)很重要的特性,即是它的層次特性"現(xiàn)實(shí)中的網(wǎng)絡(luò)是由一個(gè)個(gè)較小的社團(tuán)組成,而這些社團(tuán)又可以包括更小的社團(tuán)。發(fā)現(xiàn)網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu),對(duì)于了解網(wǎng)絡(luò)結(jié)構(gòu)，分析網(wǎng)絡(luò)特性都具有很重要的意義。具有社團(tuán)結(jié)構(gòu)性質(zhì)的網(wǎng)絡(luò)網(wǎng)絡(luò)的社區(qū)社區(qū)結(jié)構(gòu)的幾種定義（沒(méi)仔細(xì)看）派系社區(qū)分解算法及度量標(biāo)準(zhǔn)社區(qū)分解算法的幾種分類在復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的研究中，社區(qū)結(jié)構(gòu)劃分算法所要?jiǎng)澐值木W(wǎng)絡(luò)大致可分為兩類，一類是比較常見(jiàn)的網(wǎng)絡(luò)，即僅包含正聯(lián)系的網(wǎng)絡(luò)(網(wǎng)絡(luò)中邊的權(quán)值為正實(shí)數(shù))；另一類是符號(hào)社會(huì)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中既包含正向聯(lián)系的邊，也包含負(fù)向聯(lián)系的邊。因此劃分網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法相應(yīng)分為兩大類，而對(duì)于第一類網(wǎng)絡(luò)又提出了許多不同的社區(qū)結(jié)

構(gòu)劃分算法，劃分第一類網(wǎng)絡(luò)社區(qū)的傳統(tǒng)算法可分為兩大類，第一類是基于圖論的算法，比如K—L算法（增益函數(shù)）、譜平分法、隨機(jī)游走算法和派系過(guò)濾算法等；第二類是層次聚類算法，比如基于相似度度量的凝聚算法和基于邊介數(shù)度量的分裂算法（GN算法）等。早期分析社團(tuán)結(jié)構(gòu)的算法,包括基于計(jì)算機(jī)科學(xué)中的圖形分割和社會(huì)學(xué)中的層次聚類兩大類,前者主要包括Kernighan-Lin算法和譜平分算法兩種;而后者則以GN算法為代表。之后,又有很多學(xué)者在GN算法的基礎(chǔ)上提出了一系列算法按照復(fù)雜網(wǎng)絡(luò)中社團(tuán)形成的過(guò)程,網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的劃分思路大體可以分成4類:凝聚過(guò)程、分裂過(guò)程、搜索過(guò)程和其他過(guò)程。凝聚過(guò)程是以頂點(diǎn)為基礎(chǔ),通過(guò)逐步凝結(jié)形成社團(tuán)。其主要步驟為:1)設(shè)定某種標(biāo)準(zhǔn)可以衡量社團(tuán)與社團(tuán)之間的距離或相似度;2)將網(wǎng)絡(luò)中的每一個(gè)頂點(diǎn)視為一個(gè)社團(tuán),所以網(wǎng)絡(luò)中有多少頂點(diǎn)就有多少初始社團(tuán),并且每個(gè)社團(tuán)只包含一個(gè)頂點(diǎn);3)根據(jù)設(shè)定的衡量標(biāo)準(zhǔn),計(jì)算社團(tuán)與社團(tuán)間的距離或相似度,并將距離最近的社團(tuán)或相似度最高的社團(tuán)合并在一起形成新的社團(tuán);4)重新計(jì)算每對(duì)社團(tuán)間的距離或相似度;5)不斷重復(fù)合并及重新計(jì)算的步驟,直到所有頂點(diǎn)都聚集成一個(gè)社團(tuán)。分裂過(guò)程則相反,它首先將網(wǎng)絡(luò)中的所有頂點(diǎn)都視為一大社團(tuán),通過(guò)逐步分割這個(gè)大社團(tuán)形成小社團(tuán)。其主要步驟為:1)設(shè)定某種衡量頂點(diǎn)間密切程度或邊對(duì)網(wǎng)絡(luò)結(jié)構(gòu)影響程度的指標(biāo);2)按照一定標(biāo)準(zhǔn)進(jìn)行刪邊;3)不斷重復(fù)計(jì)算和斷邊的過(guò)程,網(wǎng)絡(luò)將被劃分成一個(gè)個(gè)越來(lái)越小的連通社團(tuán),這些連通社團(tuán)就是對(duì)應(yīng)某一階段的社團(tuán);4)全部過(guò)程以每個(gè)頂點(diǎn)被獨(dú)立地分成一個(gè)社團(tuán)為終點(diǎn)。整個(gè)過(guò)程可以用一個(gè)直立的樹(shù)狀圖表示,過(guò)程方向與凝聚過(guò)程相反。搜索過(guò)程不拘泥于統(tǒng)一的凝結(jié)或分裂,而是建立一個(gè)逐步優(yōu)化目標(biāo)的探索過(guò)程,社團(tuán)結(jié)構(gòu)直接由最后的優(yōu)化結(jié)果給出。以上提到的所有算法,其共同特點(diǎn)是致力于盡快且盡量準(zhǔn)確地求得整個(gè)網(wǎng)絡(luò)的社團(tuán)構(gòu)。因此,這些算法的前提是需要知道整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。局部社區(qū)發(fā)現(xiàn)

在不知道整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的情況下，要求尋找一個(gè)起始節(jié)點(diǎn)所在社區(qū)，而無(wú)須找到網(wǎng)絡(luò)中所有社區(qū)的算法叫做局部社區(qū)發(fā)現(xiàn)。局部社區(qū)發(fā)現(xiàn)特別適用于Web上的社區(qū)發(fā)現(xiàn)，因?yàn)閃eb上的網(wǎng)頁(yè)規(guī)模極大，而且動(dòng)態(tài)更新較快，想得到Web的全局拓?fù)浣Y(jié)構(gòu)幾乎是不可能的，因此只能從局部出發(fā)，挖掘出與某個(gè)起始網(wǎng)頁(yè)主題相關(guān)的的其他網(wǎng)頁(yè)，或者說(shuō)挖掘出用戶感興趣主題的網(wǎng)頁(yè)及信息。這樣就可以節(jié)省開(kāi)銷而且具有針對(duì)性。全局社區(qū)發(fā)現(xiàn)

在知道整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的情況下，尋找該類網(wǎng)絡(luò)中所有社區(qū)的算法叫做全局社區(qū)發(fā)現(xiàn)。全局社區(qū)發(fā)現(xiàn)算法更多的是針對(duì)在某一段時(shí)間內(nèi)，拓?fù)浣Y(jié)構(gòu)相對(duì)穩(wěn)定的網(wǎng)絡(luò)，這也是目前研究得較多的一個(gè)方向，理論成果也很豐碩。比較經(jīng)典的有基于模塊度優(yōu)化的方法、圖分割法（大多數(shù)圖分割方法均基于迭代二分法：首先將圖按要求分割成2個(gè)子圖，然后再分別對(duì)這2個(gè)子圖進(jìn)行分割，如此迭代下去直至獲得所要求的子圖個(gè)數(shù)。如KL算法，譜二分法）、層次聚類法（分為凝聚法和分裂法，GN算法為代表）、重疊社區(qū)發(fā)現(xiàn)方法和一些其他方法等。存在的問(wèn)題目前社區(qū)發(fā)現(xiàn)算法的研究主要存在以下一些問(wèn)題：1對(duì)大規(guī)模網(wǎng)絡(luò)難以處理現(xiàn)有的社區(qū)發(fā)現(xiàn)算法大多不能處理大規(guī)模的網(wǎng)絡(luò)，它們的時(shí)間復(fù)雜度較大。2中心點(diǎn)個(gè)數(shù)難確定（凝聚算法中）（不明白）

有些社區(qū)發(fā)現(xiàn)算法是基于網(wǎng)絡(luò)圖的中心點(diǎn)，它們都是以度數(shù)最大的一些節(jié)點(diǎn)，稱之為中心點(diǎn)，為起始節(jié)點(diǎn)進(jìn)行擴(kuò)展或者行走，中心點(diǎn)的選取很大程度上決定了最終社區(qū)劃分。然而，這些算法對(duì)于網(wǎng)絡(luò)中心點(diǎn)的數(shù)目一般難以確定，只能進(jìn)行一定程度的嘗試，通過(guò)重復(fù)設(shè)置中心點(diǎn)個(gè)數(shù)，多次重復(fù)運(yùn)行算法，然后選取最好的結(jié)果作為社區(qū)劃分。3社區(qū)結(jié)構(gòu)不穩(wěn)定

目前很多社區(qū)發(fā)現(xiàn)算法都存在一定的隨機(jī)性，都是因?yàn)榉N子節(jié)點(diǎn)選取的隨機(jī)性而造成最終得到的社區(qū)結(jié)構(gòu)不穩(wěn)定。不同種子節(jié)點(diǎn)的選取會(huì)造成得到不一樣的社區(qū)結(jié)構(gòu)。4要求提前給定社區(qū)個(gè)數(shù)（GN算法）

有的社區(qū)發(fā)現(xiàn)算法需要提前指定該算法要找到的社區(qū)個(gè)數(shù)，也即把網(wǎng)絡(luò)劃分成指定個(gè)數(shù)的社區(qū)，一個(gè)具體網(wǎng)絡(luò)的真實(shí)社區(qū)個(gè)數(shù)是很難預(yù)先知道的，而社區(qū)個(gè)數(shù)也正是算法需要找到的，這樣的算法顯得有些本末倒置。模塊度（NG模塊度）（衡量分割后社區(qū)的好壞，網(wǎng)絡(luò)分解的質(zhì)量，GN算法）其基本假設(shè)是：隨機(jī)網(wǎng)絡(luò)沒(méi)有社區(qū)結(jié)構(gòu)。Q=0時(shí)一個(gè)社區(qū)；Q=1時(shí)k個(gè)獨(dú)立的社。GN算法是分裂法，可以用樹(shù)狀圖來(lái)表示算法過(guò)程。當(dāng)沿著樹(shù)狀圖逐步下移時(shí)，每移一步就對(duì)該截取位置對(duì)應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)計(jì)算Q值，并找到局部峰值，既是對(duì)應(yīng)著的比較好的截取位置。幾種社區(qū)提取算法及其優(yōu)缺點(diǎn)KL算法Kernighan－Lin算法是一種試探優(yōu)化算法，它基于貪婪算法原理的二分法該算法將網(wǎng)絡(luò)劃分為兩個(gè)已知大小的社區(qū)．它的基本思想是引進(jìn)一個(gè)增益函數(shù)Q，定義為兩個(gè)社區(qū)內(nèi)部的變數(shù)減去鏈接兩個(gè)社團(tuán)之間的變數(shù)，然后尋找最優(yōu)方法使Q值達(dá)到最大（Q定義為兩個(gè)社區(qū)內(nèi)部的邊數(shù)減去連接兩個(gè)社區(qū)之間的邊數(shù)，然后尋找使Q值最大的劃分方法。）這種劃分的方法的缺陷是只能用于劃分存在兩個(gè)社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)，并且必須事先知道該網(wǎng)絡(luò)的兩個(gè)社區(qū)的規(guī)模．面臨著如何事先知道網(wǎng)絡(luò)中的社區(qū)數(shù)目，以及確定二分法要重復(fù)到哪一步停止的問(wèn)題。這些局限使得該算法很難應(yīng)用于實(shí)際問(wèn)題．

KL算法的不足：

找到的解往往是局部最優(yōu)而不是全局最優(yōu)解。

KL對(duì)初始解非常敏感，它需要先驗(yàn)知識(shí)。

KL算法的時(shí)間復(fù)雜性:

O(tn2)，t表示算法終止時(shí)的迭代次數(shù)，n表示網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)。

KL算法可描述如下1將網(wǎng)絡(luò)中的結(jié)點(diǎn)隨機(jī)地劃分為已知大?。A數(shù)或規(guī)模，階數(shù)是頂點(diǎn)數(shù)，規(guī)模是邊數(shù)）的兩個(gè)社區(qū)。在此基礎(chǔ)上，考慮所有可能的結(jié)點(diǎn)對(duì)，其中每個(gè)結(jié)點(diǎn)對(duì)的結(jié)點(diǎn)分別來(lái)自兩個(gè)社區(qū)。2引進(jìn)增益函數(shù)Q，Q表示兩個(gè)社區(qū)內(nèi)部的邊數(shù)減去連接兩個(gè)社區(qū)之間的邊數(shù)。3計(jì)算每對(duì)節(jié)點(diǎn)的Q（交換前）值和沒(méi)對(duì)節(jié)點(diǎn)交換后的Q（交換后）值，求=Q（交換后）—Q（交換前），（負(fù)值怎么辦，是安正負(fù)比較大小嗎？）找出最大的，并將其對(duì)應(yīng)的節(jié)點(diǎn)交換。并記錄交換后的Q值。注意節(jié)點(diǎn)對(duì)的點(diǎn)必須位于兩個(gè)社區(qū)。4重復(fù)這個(gè)交換過(guò)程，規(guī)定每個(gè)結(jié)點(diǎn)只能交換一次，直到某個(gè)社區(qū)內(nèi)所有的結(jié)點(diǎn)都被交換一次為止。5當(dāng)交換完畢后，便找到上述交換過(guò)程中所記錄的最大的Q值。這時(shí)對(duì)應(yīng)的社區(qū)結(jié)構(gòu)就認(rèn)為是該網(wǎng)絡(luò)實(shí)際的社區(qū)結(jié)構(gòu)。注：貪婪算法：貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。規(guī)模:邊的數(shù)目。GN算法層次聚類是尋找社會(huì)網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的一類傳統(tǒng)算法。它基于各個(gè)節(jié)點(diǎn)之間連接的相似性或者強(qiáng)度,把網(wǎng)絡(luò)自然地劃分為各個(gè)子群。根據(jù)加邊或去邊,該類算法又可以分為兩類:凝聚方法和分裂方法。，層次聚類方法通常采用譜系圖或樹(shù)狀圖來(lái)記錄算法的結(jié)果，從而描述整個(gè)網(wǎng)絡(luò)從單個(gè)獨(dú)立的子群逐步凝聚為整個(gè)網(wǎng)絡(luò)或者從整個(gè)網(wǎng)絡(luò)逐步分解為若干個(gè)越來(lái)越小的子群的連續(xù)過(guò)程，其中底部的各個(gè)圓代表了網(wǎng)絡(luò)中的各個(gè)結(jié)點(diǎn)。當(dāng)水平虛線從樹(shù)的底端逐步上移，各結(jié)點(diǎn)也逐步聚合成為更大的社區(qū)。當(dāng)虛線移至頂部，即表示整個(gè)網(wǎng)絡(luò)就成為一個(gè)社區(qū)。在該樹(shù)狀圖的任何一個(gè)位置用虛線斷開(kāi)，就對(duì)應(yīng)著一種社區(qū)結(jié)構(gòu)。分裂方法中最典型的算法是GN方法。它的基本思想是通過(guò)不斷地從網(wǎng)絡(luò)中移除介數(shù)(Betweenness)最大的邊將整個(gè)網(wǎng)絡(luò)分解為各個(gè)社區(qū)。其中，邊介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過(guò)該邊的最短路徑的數(shù)目。它為區(qū)分一個(gè)社區(qū)的內(nèi)部邊和連接社區(qū)之間的邊提供了一種有效的度量標(biāo)準(zhǔn)。

GN算法的基本流程如下1計(jì)算網(wǎng)絡(luò)中所有邊的介數(shù)（網(wǎng)絡(luò)中經(jīng)過(guò)該邊的最短路徑的數(shù)目）；

2找到介數(shù)最高的邊并將它從網(wǎng)絡(luò)中移除；

重復(fù)步驟1和2，直到每個(gè)結(jié)點(diǎn)就是一個(gè)退化的社區(qū)為止。GN算法彌補(bǔ)了一些傳統(tǒng)算法的不足，GN算法有兩個(gè)缺陷,首先對(duì)于網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)并沒(méi)有一個(gè)量的定義，因此不能直接從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來(lái)判斷它所求的社團(tuán)是否是實(shí)際網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。其次在不知道社團(tuán)數(shù)目的情況下,GN算法也不知道這種分解要進(jìn)行到哪一步終止。為解決這些問(wèn)題,Newman等人引進(jìn)了一個(gè)衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)-模塊度。GN算法考慮網(wǎng)絡(luò)全局，劃分社區(qū)準(zhǔn)確度較高，但是對(duì)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)缺少量的定義，需要事先知道社團(tuán)個(gè)數(shù)GN算法的缺點(diǎn)

GN的最大缺點(diǎn)是計(jì)算速度慢，邊介數(shù)計(jì)算的開(kāi)銷過(guò)大O(mn)，GN具有很高的時(shí)間復(fù)雜性O(shè)(m2n)，只適合處理中小規(guī)模的網(wǎng)絡(luò)(包含幾百個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò))。core-vertices算法（核心頂點(diǎn)算法）基于一些節(jié)點(diǎn)擁有最高的度數(shù)（從一個(gè)頂點(diǎn)V引出的邊的條數(shù)，稱為V的度數(shù)），它們可能屬于某一社區(qū)的核心，我們提出了核心節(jié)點(diǎn)算法。首先找到核心節(jié)點(diǎn)并將其看成最初的社團(tuán)，然后計(jì)算各社團(tuán)和其鄰接點(diǎn)的親密度（intimatedegree），根據(jù)親密度來(lái)吸收新節(jié)點(diǎn)到該社區(qū)。該算法可以在社區(qū)提取的過(guò)程中精確地找到公共節(jié)點(diǎn)。算法步驟如下1、找出度數(shù)最大的節(jié)點(diǎn)作為核心節(jié)點(diǎn)（初始社區(qū)），分成幾個(gè)社區(qū)就找?guī)讉€(gè)節(jié)點(diǎn)。2、計(jì)算各核心節(jié)點(diǎn)和其鄰接點(diǎn)的親密度，親密度定義為NCCN是社區(qū)和其鄰居共同連接節(jié)點(diǎn)的個(gè)數(shù)（如果核心節(jié)點(diǎn)與鄰接點(diǎn)有連接就加1否則不加），分母kj是鄰居（鄰接點(diǎn)）的度，n是節(jié)點(diǎn)的個(gè)數(shù)（階數(shù)），C代表不同的社區(qū)。3、比較親密度大小，將鄰接點(diǎn)歸于親密度大的社區(qū)內(nèi)，找出公共節(jié)點(diǎn)。4、計(jì)算公共節(jié)點(diǎn)與各社區(qū)內(nèi)節(jié)點(diǎn)的親密度，根據(jù)親密度的最大值來(lái)決定把公共節(jié)點(diǎn)歸于哪一個(gè)社區(qū)。5、計(jì)算模塊度衡量網(wǎng)絡(luò)分解的質(zhì)量。6、計(jì)算時(shí)間復(fù)雜度。（沒(méi)看）Dijkstra算法（單源最短路徑算法）（介數(shù)）用于解決最短路徑問(wèn)題的算法被稱做“最短路徑算法”，有時(shí)被簡(jiǎn)稱作“路徑算法”。所謂單源最短路徑問(wèn)題是指：已知圖G=（V，E），我們希望找出從某給定的源結(jié)點(diǎn)S∈V到V中的每