復(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é)