復雜網(wǎng)絡基礎2

1、復雜網(wǎng)絡基礎理論復雜網(wǎng)絡基礎理論第二章第二章 網(wǎng)絡拓撲結(jié)構與靜態(tài)特征網(wǎng)絡拓撲結(jié)構與靜態(tài)特征第二章 網(wǎng)絡拓撲結(jié)構與靜態(tài)特征l2.1 引言l2.2 網(wǎng)絡的基本靜態(tài)幾何特征l2.3 無向網(wǎng)絡的靜態(tài)特征l2.4 有向網(wǎng)絡的靜態(tài)特征l2.5 加權網(wǎng)絡的靜態(tài)特征l2.6 網(wǎng)絡的其他靜態(tài)特征l2.7 復雜網(wǎng)絡分析軟件2 22.1 引言 與圖論的研究有所不同，復雜網(wǎng)絡的研究更側(cè)重于從各種實際網(wǎng)絡的現(xiàn)象之上抽象出一般的網(wǎng)絡幾何量，并用這些一般性質(zhì)指導更多實際網(wǎng)絡的研究，進而通過討論實際網(wǎng)絡上的具體現(xiàn)象發(fā)展網(wǎng)絡模型的一般方法，最后討論網(wǎng)絡本身的形成機制。 統(tǒng)計物理學在模型研究、演化機制與結(jié)構穩(wěn)定性方面的豐富的研究

2、經(jīng)驗是統(tǒng)計物理學在復雜網(wǎng)絡研究領域得到廣泛應用的原因；而圖論與社會網(wǎng)絡分析提供的網(wǎng)絡靜態(tài)幾何量及其分析方法是復雜網(wǎng)絡研究的基礎。3 32.1 引言 靜態(tài)特征指給定網(wǎng)絡的微觀量的統(tǒng)計分布或宏觀統(tǒng)計平均值。 在本章中我們將對網(wǎng)絡的各種靜態(tài)特征做一小結(jié)。由于有向網(wǎng)絡與加權網(wǎng)絡有其特有的特征量，我們將分開討論無向、有向與加權網(wǎng)絡。4 4返回 目錄2.2 網(wǎng)絡的基本靜態(tài)幾何特征2.2.1 平均距離2.2.2 集聚系數(shù)2.2.3 度分布2.2.4 實際網(wǎng)絡的統(tǒng)計特征5 52.2.1 平均距離1.網(wǎng)絡的直徑與平均距離 網(wǎng)絡中的兩節(jié)點vi和vj之間經(jīng)歷邊數(shù)最少的一條簡單路徑（經(jīng)歷的邊各不相同），稱為測地線。

3、測地線的邊數(shù)dij稱為兩節(jié)點vi和vj之間的距離（或叫測地線距離）。 1dij稱為節(jié)點vi和vj之間的效率，記為ij。通常效率用來度量節(jié)點間的信息傳遞速度。當vi和vj之間沒有路徑連通時，dij，而ij0，所以效率更適合度量非全通網(wǎng)絡。 網(wǎng)絡的直徑D定義為所有距離dij中的最大值6 62.2.1 平均距離 平均距離（特征路徑長度）L定義為所有節(jié)點對之間距離的平均值，它描述了網(wǎng)絡中節(jié)點間的平均分離程度，即網(wǎng)絡有多小，計算公式為 對于無向簡單圖來說，dijdji且dii0，則上式可簡化為 很多實際網(wǎng)絡雖然節(jié)點數(shù)巨大，但平均距離卻小得驚人，這就是所謂的小世界效應。7 72.2.1 平均距離2.距離與

4、鄰接矩陣的關系 定義對于無權簡單圖來說，當l1時， 。容易證明無權簡單圖鄰接矩陣A A的l次冪A Al的元素 表示節(jié)點vi和vj之間通過l條邊連接的路徑數(shù)。當l2時，容易推出式中，U表示單位指示函數(shù)，即當x0，U（x）1；否則U（x）0。當ij時，ij1；否則ij0。8 82.2.1 平均距離 容易用數(shù)學歸納法證明據(jù)此，若D為網(wǎng)絡直徑，則兩節(jié)點vi和vj之間的距離dij可以表示為9 92.2.2 集聚系數(shù) 首先來看節(jié)點的集聚系數(shù)定義。假設節(jié)點vi與ki個節(jié)點直接連接，那么對于無向網(wǎng)絡來說，這ki個節(jié)點間可能存在的最大邊數(shù)為ki（ki1）2，而實際存在的邊數(shù)為Mi，由此我們定義Ci2Miki（k

5、i1）為節(jié)點vi的集聚系數(shù)。 對于有向網(wǎng)絡來說，這ki個節(jié)點間可能存在的最大弧數(shù)為ki（ki1），此時vi的集聚系數(shù)CiMiki（ki1）。 將該集聚系數(shù)對整個網(wǎng)絡作平均，可得網(wǎng)絡的平均集聚系數(shù)為10102.2.2 集聚系數(shù) 顯然，0C1。當C0，所有節(jié)點都是孤立節(jié)點，沒有邊連接。當C1時，網(wǎng)絡為所有節(jié)點兩兩之間都有邊連接的完全圖。對于完全隨機網(wǎng)絡來說，當節(jié)點數(shù)很大時，CO（1N）。而許多大規(guī)模的實際網(wǎng)絡的集聚系數(shù)通常遠小于1而大于O（1N)。對于社會網(wǎng)絡來說，通常隨著N，集聚系數(shù)CO（1），即趨向一個非零常數(shù)。 節(jié)點vi的集聚系數(shù)也可定義為CiNiNi。式中Ni代表與節(jié)點vi相連的“三角形”

6、數(shù)目，數(shù)值上就等于Mi；Ni代表與節(jié)點vi相連的“三元組”數(shù)目，即節(jié)點vi與其它兩個節(jié)點都有連接，即“至少與其他兩個分別認識”，數(shù)值上就等于ki（ki1）2。11112.2.2 集聚系數(shù) 如何根據(jù)無向無權簡單圖的鄰接矩陣A A來求節(jié)點vi的集聚系數(shù)Ci？ 顯然，鄰接矩陣二次冪A A2的對角元素 表示的是與節(jié)點vi相連的邊數(shù)，也就是節(jié)點vi的度ki。而鄰接矩陣三次冪A A3的對角元素 （aijajlali）（jl）表示的是從節(jié)點vi出發(fā)經(jīng)過三條邊回到節(jié)點vi的路徑數(shù)，也就是與節(jié)點vi相連的三角形數(shù)的兩倍（正向走和反向走）。因此，由集聚系數(shù)的定義可知12122.2.2 集聚系數(shù)【例例2.12.1】

7、計算下面簡單網(wǎng)絡的直徑、平均距離和各節(jié)點的集聚系數(shù)。解：首先計算出所有節(jié)點對的距離：d121；d131；d142；d151；d162；d231；d241；d252；d262；d342；d352；d361；d453；d461；d563。由此可得直徑和平均距離為13132.2.2 集聚系數(shù) 下面以節(jié)點v1的集聚系數(shù)計算為例：采用第一種定義可知，節(jié)點v1與3個節(jié)點直接連接，而這3個節(jié)點之間可能存在的最大邊數(shù)為3（31）2，而實際存在的邊數(shù)為1，由此可得C123（31）13。 若采用第二種定義可知：與相連的三角形數(shù)為N1，而與v1相連的三元組數(shù)為N13，故C113。 也可以利用式 計算，因為鄰接矩陣A

8、 A的前三次冪為14142.2.2 集聚系數(shù)故 2， 3，從而同理可得其他各節(jié)點的集聚系數(shù)為C213；C313；C40；C50；C60由此很容易算出該網(wǎng)絡的集聚系數(shù)15152.2.3 度分布1.節(jié)點的度 在網(wǎng)絡中，節(jié)點vi的鄰邊數(shù)ki稱為該節(jié)點vi的度。 對網(wǎng)絡中所有節(jié)點的度求平均，可得到網(wǎng)絡的平均度k 無向無權圖鄰接矩陣A A的二次冪A A2的對角元素 就是節(jié)點vi的鄰邊數(shù)，即 。實際上，無向無權圖鄰接矩陣A A的第i行或第i列元素之和也是度。從而無向無權網(wǎng)絡的平均度就是A A2對角線元素之和除以節(jié)點數(shù)，即ktr（A A2）N。式中，tr（A A2）表示矩陣A A2的跡，即對角線元素之和。1

9、6162.2.3 度分布2.度分布 大多數(shù)實際網(wǎng)絡中的節(jié)點的度是滿足一定的概率分布的。定義P（k）為網(wǎng)絡中度為k的節(jié)點在整個網(wǎng)絡中所占的比率。 規(guī)則網(wǎng)絡：由于每個節(jié)點具有相同的度，所以其度分布集中在一個單一尖峰上，是一種Delta分布。 完全隨機網(wǎng)絡：度分布具有Poisson分布的形式，每一條邊的出現(xiàn)概率是相等的，大多數(shù)節(jié)點的度是基本相同的，并接近于網(wǎng)絡平均度k，遠離峰值k，度分布則按指數(shù)形式急劇下降。把這類網(wǎng)絡稱為均勻網(wǎng)絡。 無標度網(wǎng)絡：具有冪指數(shù)形式的度分布：P（k）k 。所謂無標度是指一個概率分布函數(shù)F（x）對于17172.2.3 度分布任意給定常數(shù)a存在常數(shù)b使得F（x）滿足F（ax）

10、bF（x）。冪律分布是唯一滿足無標度條件的概率分布函數(shù)。許多實際大規(guī)模無標度網(wǎng)絡，其冪指數(shù)通常為23，絕大多數(shù)節(jié)點的度相對很低，也存在少量度值相對很高的節(jié)點（稱為hub），把這類網(wǎng)絡稱為非均勻網(wǎng)絡。 指數(shù)度分布網(wǎng)絡： P（k）ek/，式中0為一常數(shù)。18182.2.3 度分布3.累積度分布 可以用累積度分布函數(shù)來描述度的分布情況，它與度分布的關系為它表示度不小于k的節(jié)點的概率分布。 若度分布為冪律分布，即P（k）k，則相應的累積度分布函數(shù)符合冪指數(shù)為1的冪律分布 若度分布為指數(shù)分布，即P（k）ek/，則相應的累積度分布函數(shù)符合同指數(shù)的指數(shù)分布19192.2.4 實際網(wǎng)絡的統(tǒng)計特征2020返回

11、目錄2.3 無向網(wǎng)絡的靜態(tài)特征2.3.1 聯(lián)合度分布和度度相關性2.3.2 集聚系數(shù)分布和聚度相關性2.3.3 介數(shù)和核度2.3.4 中心性2.3.5 網(wǎng)絡密度2.3.6 連通集團（子圖）及其規(guī)模分布21212.3.1 聯(lián)合度分布和度度相關性1.聯(lián)合度分布 度分布滿足 平均度與度分布具有關系式 聯(lián)合度分布定義為從無向網(wǎng)絡中隨機選擇一條邊，該邊的兩個節(jié)點的度值分別為k1和k2的概率，即式中，M（k1，k2）為度值為k1的節(jié)點和度值為k2的節(jié)點相連的總邊數(shù)，M為網(wǎng)絡總邊數(shù)。 從聯(lián)合度分布可以得出度分布式中， 1（kk2）； 0（kk2）。22222.3.1 聯(lián)合度分布和度度相關性 聯(lián)合節(jié)點度分布所

12、包含的拓撲信息最多，節(jié)點度分布次之，平均節(jié)點度最少。2.基于最近鄰平均度值的度度相關性 度度相關性描述了網(wǎng)絡中度大的節(jié)點和度小的節(jié)點之間的關系。若度大的節(jié)點傾向于和度大的節(jié)點連接，則網(wǎng)絡是度度正相關的；反之，若度大的節(jié)點傾向于和度小的節(jié)點連接，則網(wǎng)絡是度度負相關的。 節(jié)點vi的最近鄰平均度值定義為式中，ki表示節(jié)點vi的度值，aij為鄰接矩陣元素。23232.3.1 聯(lián)合度分布和度度相關性 所有度值為k的節(jié)點的最近鄰平均度值的平均值knn（k）定義為式中，N為節(jié)點總數(shù)，P（k）為度分布函數(shù)。 如果knn（k）是隨著k上升的增函數(shù)，則說明度值大的節(jié)點傾向于和度值大的節(jié)點連接，網(wǎng)絡具有正相關特性，

13、稱之為同配網(wǎng)絡；反之網(wǎng)絡具有負相關特性，稱之為異配網(wǎng)絡。3.基于Pearson相關系數(shù)的度度相關性 Newman利用邊兩端節(jié)點的度的Pearson相關系數(shù)r來描述網(wǎng)絡的度度相關性，具體定義為24242.3.1 聯(lián)合度分布和度度相關性式中，ki，kj分別表示邊eij的兩個節(jié)點vi，vj的度，M表示網(wǎng)絡的總邊數(shù)。 容易證明度度相關系數(shù)r的范圍為：0|r|1。當r0時，網(wǎng)絡是正相關的；當r0時，網(wǎng)絡是不相關的。25252.3.2 集聚系數(shù)分布和聚度相關性1.集聚系數(shù)分布 集聚系數(shù)分布函數(shù)P（C）表示從網(wǎng)絡中任選一節(jié)點，其集聚系數(shù)值為C的概率式中，（x）為單位沖激函數(shù)。2.聚度相關性 局部集聚系數(shù)C（

14、k）定義為度為k的節(jié)點的鄰居之間存在的平均邊數(shù)Mnn（k）與這些鄰居之間存在的最大可能的邊數(shù)的比值，即26262.3.2 集聚系數(shù)分布和聚度相關性 全局集聚系數(shù)C則定義為式中，k2為度的二階矩。 顯然，局部集聚系數(shù)C（k）與k的關系刻畫了網(wǎng)絡的聚度相關性。許多真實網(wǎng)絡如好萊塢電影演員合作網(wǎng)絡、語義網(wǎng)絡中節(jié)點的聚度相關性存在近似的倒數(shù)關系C（k）k1 。把這種倒數(shù)關系的聚度相關性稱為層次性，把具有層次性的網(wǎng)絡稱為層次網(wǎng)絡。27272.3.3 介數(shù)和核度1.介數(shù) 要衡量一個節(jié)點的重要性，其度值當然可以作為一個衡量指標，但又不盡然，例如在社會網(wǎng)絡中，有的節(jié)點的度雖然很小，但它可能是兩個社團的中間聯(lián)絡

15、人，如果去掉該節(jié)點，那么就會導致兩個社團的聯(lián)系中斷，因此該節(jié)點在網(wǎng)絡中起到極其重要的作用。對于這樣的節(jié)點，需要定義另一種衡量指標，這就引出網(wǎng)絡的另一種重要的全局幾何量介數(shù)。 介數(shù)分為節(jié)點介數(shù)和邊介數(shù)兩種，反映了節(jié)點或邊在整個網(wǎng)絡中的作用和影響力。28282.3.3 介數(shù)和核度 節(jié)點的介數(shù)Bi定義為式中，Njl表示節(jié)點vj和vl之間的最短路徑條數(shù)，Njl（i）表示節(jié)點vj和vl之間的最短路徑經(jīng)過節(jié)點vi的條數(shù)。 邊的介數(shù)Bij定義為式中，Nlm表示節(jié)點vl和vm之間的最短路徑條數(shù)，Nlm（eij）表示節(jié)點vl和vm之間的最短路徑經(jīng)過邊eij的條數(shù)。29292.3.3 介數(shù)和核度2.介數(shù)分布和介度

16、相關性 節(jié)點的介數(shù)與度之間有很強的相關性，而且不同類型的網(wǎng)絡，其介數(shù)分布也大不一樣。 介度相關性可以用B（k）k表示，它定義為所有度為k的節(jié)點的介數(shù)平均值隨著k的變化關系。 節(jié)點介數(shù)分布Pv（B）定義為網(wǎng)絡中節(jié)點介數(shù)為B的節(jié)點數(shù)占網(wǎng)絡節(jié)點總數(shù)的比例。 邊介數(shù)分布Pe（B）定義為網(wǎng)絡中邊介數(shù)為B的邊數(shù)占網(wǎng)絡總邊數(shù)的比例。 研究表明，節(jié)點的最大介數(shù)與網(wǎng)絡的同步能力密切相關：節(jié)點的最大介數(shù)越大，網(wǎng)絡的同步能力越弱。30302.3.3 介數(shù)和核度3.核度 一個圖的k核是指反復去掉度值小于k的節(jié)點及其連線后，所剩余的子圖，該子圖的節(jié)點數(shù)就是該核的大小。 若一個節(jié)點屬于k核，而不屬于（k1）核，則此節(jié)點的

17、核度為k。 節(jié)點核度的最大值叫做網(wǎng)絡的核度。 節(jié)點的核度可以說明節(jié)點在核中的深度，核度的最大值自然就對應著網(wǎng)絡結(jié)構中最中心的位置。k核解析可用來描述度分布所不能描述的網(wǎng)絡特征，揭示源于系統(tǒng)特殊結(jié)構的結(jié)構和層次性質(zhì)。31312.3.3 介數(shù)和核度【例例2.22.2】計算下面網(wǎng)絡的一些特性：（1）度分布及平均度；（2）聯(lián)合度分布并驗證 的正確性；（3）各節(jié)點的最近鄰平均度值knn,i；（4）該網(wǎng)絡是否是同配網(wǎng)絡；（5）該網(wǎng)絡是否是正相關網(wǎng)絡；（6）分別求各節(jié)點和各連接邊的介數(shù)；（7）求該網(wǎng)絡的2核，3核及各自核度大小，并計算該網(wǎng)絡的核度。32322.3.3 介數(shù)和核度解：（1）該網(wǎng)絡的度分布如下表

18、所示。因此或（2）根據(jù) 容易得到聯(lián)合度分布如下表所示。 由此可以驗證 的正確性，例如當k1時，該式左邊P（1）=16，而右邊為33332.3.3 介數(shù)和核度（3）利用 得v1v6的最近鄰平均度值knn,i分別為：73、83、83、52、3、52。（4）利用 得度為1、2、3的節(jié)點的最近鄰平均度值的平均值knn（k）分別為：3、52、239。由于隨著k的增加knn（k）下降，所以該網(wǎng)絡是異配網(wǎng)絡。（5）Pearson相關系數(shù)因為r0，說明該網(wǎng)絡為負相關。（6）由圖可知各節(jié)點之間的最短路徑分別為：v1e2v2；v1e3v3；v1e2v2e5v4；v1e1v5；v1e3v3e7v6；v2e4v3；v

19、2e5v4；v2e2v1e1v5；v2e4v3e7v6；v2e5v4e6v6；v3e4v2e5v4；v3e7v6e6v4；v3e3v1e1v5；v3e7v6；v4e5v2e2v1e1v5；v4e6v6；v5e1v1e3v3e7v6。34342.3.3 介數(shù)和核度由此可得v1v6各節(jié)點的介數(shù)Bi為：4、2.5、2.5、0.5、0、0.5。同理可得e1e7各邊的介數(shù)為：4、3、3、1、3、1、3。（7）該網(wǎng)絡的2核，3核如下圖所示，它們核的大小分別為5和3。節(jié)點v1v6的核度分別為3、3、3、2、1、2，所以網(wǎng)絡的核度為3。35352.3.4 中心性1.度中心性 度中心性分為節(jié)點度中心性和網(wǎng)絡度中

20、心性。前者指的是節(jié)點在其與之直接相連的鄰居節(jié)點當中的中心程度，而后者則側(cè)重節(jié)點在整個網(wǎng)絡的中心程度，表征的是整個網(wǎng)絡的集中或集權程度，即整個網(wǎng)絡圍繞一個節(jié)點或一組節(jié)點來組織運行的程度。 節(jié)點vi的度中心性CD（vi）定義為 在所有含N節(jié)點的網(wǎng)絡中，假設網(wǎng)絡G Goptimal使得下式達到最大值式中，ui為網(wǎng)絡G Goptimal的各個節(jié)點，u max表示網(wǎng)絡G Goptimal中擁有最大度中心性的節(jié)點。36362.3.4 中心性 對于含N節(jié)點的某網(wǎng)絡G G，令vmax表示其擁有最大度中心性的節(jié)點，則網(wǎng)絡G G的度中心性CD定義為 當圖G Goptimal為星型網(wǎng)絡時，H值達到最大，即 因此，網(wǎng)

21、絡G G的度中心性CD可簡化為37372.3.4 中心性2.介數(shù)中心性 介數(shù)中心性分為節(jié)點介數(shù)中心性和網(wǎng)絡介數(shù)中心性。 節(jié)點vi的介數(shù)中心性CB（vi）定義為 與度中心性類似，可得HN1（也是星型網(wǎng)絡，中心節(jié)點的介數(shù)中心性為1，其它節(jié)點的介數(shù)中心性為0）。 因此，網(wǎng)絡G G的介數(shù)中心性CB可簡化為38382.3.4 中心性3.接近度中心性 對于連通圖來說，節(jié)點vi的接近度中心性CC（vi）定義為 與度中心性類似，可得H（N1）（N2）（2N3） （也是星型網(wǎng)絡）。 因此，連通網(wǎng)絡G G的接近度中心性CC可簡化為 對于非連通圖來說，上述定義需要做一定的修正，一個比較好的做法是分別計算各個連通分支

22、的中心性，然后根據(jù)各連通分支的階數(shù)進行加權。39392.3.4 中心性4.特征向量中心性AxAxx x 通常，上式的各個特征向量對應不同的特征值。在這里，一個額外的要求是特征向量的每個分量必須是正數(shù)。根據(jù)PerronFrobenius定理，只有最大的特征值對應的特征向量才是中心性測度所需要的。求這個特征向量可采用冪迭代算法。在最后得到的特征向量中，第i個分量xi就是節(jié)點vi的特征向量中心性CE（vi）。40402.3.5 網(wǎng)絡密度 網(wǎng)絡密度指的是一個網(wǎng)絡中各節(jié)點之間聯(lián)絡的緊密程度。網(wǎng)絡G G的網(wǎng)絡密度d（G G）定義為式中，M為網(wǎng)絡中實際擁有的連接數(shù)，N為網(wǎng)絡節(jié)點數(shù)。 網(wǎng)絡密度的取值范圍為0，

23、1，當網(wǎng)絡內(nèi)部完全連通時，網(wǎng)絡密度為1，而實際網(wǎng)絡的密度通常遠小于1，實際網(wǎng)絡中能夠發(fā)現(xiàn)的最大密度值是0.5。 不同規(guī)模網(wǎng)絡的密度無法進行比較。為了解決這一問題，John Scott提出了“絕對密度”公式式中， D表示網(wǎng)絡直徑，R表示半徑，S表示根據(jù)直徑算出的圓周長。41412.3.6 連通集團（子圖）及其規(guī)模分布1.連通、連通集團（子圖）和連通分支（最大連通子圖） 連通集團（子圖）就是指網(wǎng)絡G G中的一個子圖，在這個子圖內(nèi)，任意兩個節(jié)點之間都至少存在一條簡單路徑。 對于非連通圖G G來說，肯定可以將其分解為兩個或兩個以上的連通分支。所謂連通分支就是最大連通子圖，即該連通子圖加入任何其它節(jié)點都

24、將影響該子圖的連通性。圖G G中的每個節(jié)點只能屬于一個連通分支，邊也一樣。顯然，連通圖的連通分支數(shù)為1，而非連通圖的連通分支數(shù)大于1。 把網(wǎng)絡的各連通分支中階數(shù)最大的一個稱為最大連通分支。42422.3.6 連通集團（子圖）及其規(guī)模分布2.連通度 連通圖G G的連通程度通常叫做連通度。連通度有兩種，一種是點連通度，一種是邊連通度。通常一個圖的連通度越好，它所代表的網(wǎng)絡越穩(wěn)定。 點連通度定義為式中，V是圖G G的節(jié)點集合，S為V的真子集，（G GS）表示從圖G G中刪除點集S后得到的子圖G GS的連通分支數(shù)。這里G GS是指刪除S中每一個節(jié)點以及圖G G中與之關聯(lián)的所有邊。由此可見，點連通度就是

25、使G G不連通或成為平凡圖所必須刪除的最少節(jié)點個數(shù)。對于不連通圖或平凡圖，定義（G G）0；若G G為N階完全圖，（G G）N1。43432.3.6 連通集團（子圖）及其規(guī)模分布 邊連通度定義為式中，E是圖G G的邊集合，T為E的真子集，（G GT）表示從圖G G中刪除邊集T后得到的子圖G GT的連通分支數(shù)。這里G GT是指刪除T中每一條邊，而G G中所有節(jié)點全部保留下來。由此可見，邊連通度就是使G G不連通所必須刪除的最少邊數(shù)。對于不連通圖或平凡圖，定義（G G）0；若G G為N階完全圖，（G G）N1。 可以證明，同一個圖的點連通度和邊連通度滿足（G G）（G G）。44442.3.6 連

26、通集團（子圖）及其規(guī)模分布3.連通集團的規(guī)模分布 連通集團的規(guī)模分布反映了網(wǎng)絡G G中的各種規(guī)模的連通分支的數(shù)目分布情況。實證研究表明，對于大量的無標度網(wǎng)絡，連通集團的規(guī)模也存在冪律分布。例如，科學家合作網(wǎng)的連通子圖規(guī)模分布。4545返回 目錄2.4 有向網(wǎng)絡的靜態(tài)特征2.4.1 入度和出度及其分布2.4.2 度度相關性2.4.3 平均距離和效率2.4.4 入集團和出集團的集聚程度2.4.5 介數(shù)和雙向比2.4.6 中心性46462.4.1 入度和出度及其分布1.入度與出度 由于與有向網(wǎng)絡某個節(jié)點相關聯(lián)的弧有指向節(jié)點的，也有背向節(jié)點向外的，因此除了可以統(tǒng)計與某個節(jié)點相關聯(lián)的弧數(shù)，也就是度之外，

27、有必要分開統(tǒng)計兩個方向的弧數(shù)，分別稱為節(jié)點的入度和出度。 節(jié)點vi的入度、出度和有向圖的鄰接矩陣以及度的關系為47472.4.1 入度和出度及其分布 同平均度一樣，也可以求平均入度kin和平均出度kout為2.入度分布和出度分布 入度分布和出度分布分別記為Pin（k）和Pout（k），分別表示網(wǎng)絡中任意取出一個節(jié)點，其入度值和出度值剛好為k的概率。 入（出）度分布與平均入（出）度之間具有如下關系式48482.4.1 入度和出度及其分布3.累積入度分布和累積出度分布 累積入（出）度分布與入（出）度分布的關系為 容易證明入（出）度冪律分布對應的累積分布也是冪律分布，入（出）度指數(shù)分布對應的累積分布

28、也是同指數(shù)的指數(shù)分布。4.聯(lián)合度分布 聯(lián)合度分布有兩種定義方式，第一種定義方式是基于弧的方式，第二種定義方式是基于節(jié)點的方式。49492.4.1 入度和出度及其分布 基于弧的方式：從網(wǎng)絡中隨機選擇一條弧，該弧由入度和出度分別為（jin，jout）的節(jié)點連向入度和出度分別為（kin，kout）的節(jié)點的概率，即式中，M（jin，jout；kin，kout）為由入度和出度分別為jin和jout的節(jié)點連向入度和出度分別為kin和kout的節(jié)點的弧數(shù)，M為網(wǎng)絡總弧數(shù)。注意，聯(lián)合概率Pe（jin，jout；kin，kout）不是對稱的，即Pe（jin，jout；kin，kout）Pe（kin，kout；

29、jin，jout）。 若對上式按照（kin，kout）求和，就得到隨機選取一條弧，該弧起點的度為（jin，jout）的概率50502.4.1 入度和出度及其分布 若對上式按照（jin，jout）求和，就得到隨機選取一條弧，該弧終點的度為（kin，kout）的概率 基于節(jié)點的方式：從網(wǎng)絡中隨機選擇一個節(jié)點，其入度值和出度值分別為kin和kout的概率，即式中，N（kin，kout）為入度值和出度值分別為kin和kout的節(jié)點數(shù)，N為網(wǎng)絡總節(jié)點數(shù)。 Pv（kin，kout）和Pf（kin，kout）、Pt（kin，kout）具有如下關系式51512.4.2 度度相關性 度度相關性也有兩種定義方式，

30、即基于節(jié)點的方式和基于弧的方式。1.基于節(jié)點的入度出度相關性 可以定義節(jié)點的入度為kin的情況下其出度為kout的條件概率為 然后，可以定義基于節(jié)點的入度出度相關性為 更簡便的定義為 如果kvv（kin）kin曲線的斜率小于0，則kin和kout負相關；斜率大于0，則kin和kout正相關；等于0，則kin和kout不相關。52522.4.2 度度相關性2.基于弧的度度相關性 任意選取一條弧，在弧的兩端存在兩個度值，起點的入度和出度，終點的入度和出度，所以存在四種相關性，分別是起點入度終點入度，起點出度終點入度，終點入度起點出度以及終點出度起點出度,分別記做kin-in（kin）kin，kou

31、t-in（kin）kin，kin-out（kout）kout，kout-out（kout）kout。這四種相關性可分別定義如下53532.4.3 平均距離和效率 由于有向網(wǎng)絡里的弧是帶有方向的，所以從節(jié)點vi到vj之間的距離dij和從節(jié)點vj到vi之間的距離dji是不同的。距離dij定義為從節(jié)點vi出發(fā)沿著同一方向到達節(jié)點vj所要經(jīng)歷的弧的最少數(shù)目，而它的倒數(shù)1dij稱為從節(jié)點vi到節(jié)點vj的效率，記為ij。 有向連通簡單網(wǎng)絡的平均距離L定義為所有節(jié)點對之間距離的平均值，定義為 因為效率可以用來描述非連通網(wǎng)絡，所以可以定義有向網(wǎng)絡的效率LC為54542.4.4 入集團和出集團的集聚程度 對于某

32、個節(jié)點vi來說，所有以該節(jié)點為終點的弧的起始節(jié)點及它們之間的連弧構成一個小集團，稱之為入集團；而所有以該節(jié)點為起點的弧的終止節(jié)點及它們之間的連弧構成一個小集團，稱之為出集團。 由于節(jié)點vi的入度為kiin，則連向該節(jié)點的kiin個起始節(jié)點間可能存在的最大弧數(shù)為kiin（kiin1），而實際存在的弧數(shù)為Miin，由此定義為節(jié)點vi的入集聚系數(shù)，然后將該集聚系數(shù)對整個網(wǎng)絡作平均，即可得網(wǎng)絡的入集團的集聚系數(shù)。55552.4.4 入集團和出集團的集聚程度 同理，定義為節(jié)點vi的出集聚系數(shù)，然后將該集聚系數(shù)對整個網(wǎng)絡作平均，即可得網(wǎng)絡的出集團的集聚系數(shù)。56562.4.4 入集團和出集團的集聚程度【例

33、例2.32.3】針對下圖所示網(wǎng)絡分別計算：（1）寫出該網(wǎng)絡的鄰接矩陣、入度分布及出度分布；（2）分別求出該網(wǎng)絡的Pf（kin，kout）、Pt（kin，kout）和Pv（kin，kout）；（3）整個網(wǎng)絡的入集團和出集團的集聚系數(shù)。57572.4.4 入集團和出集團的集聚程度解：（1）該網(wǎng)絡的鄰接矩陣為 入度分布如下表所示 出度分布如下表所示（2）聯(lián)合概率分布Pe（jin，jout；kin，kout）如下表所示58582.4.4 入集團和出集團的集聚程度 由上表可得Pf（jin，jout），如下表所示 Pt（kin，kout）如下表所示 Pv（kin，kout）如下表所示59592.4.4 入

34、集團和出集團的集聚程度（3）以節(jié)點v5為例，其對應的入集團如下圖所示，由此可計算出節(jié)點v5的入集團集聚系數(shù)同理可計算出每個節(jié)點的入集團的集聚系數(shù)為：0、0、0、12、16、0。而每個節(jié)點的出集團的集聚系數(shù)為：12、0、0、0、0、13。因此，可得網(wǎng)絡的入集團和出集團集聚系數(shù)分別為19和536。60602.4.5 介數(shù)和雙向比1.介數(shù) 節(jié)點的介數(shù)Bi定義為式中，Njl表示從節(jié)點vj到vl的最短路徑條數(shù)，Njl（i）表示從節(jié)點vj到vl的最短路徑經(jīng)過節(jié)點vi的條數(shù)。 邊的介數(shù)Bij定義為式中，Nlm表示從節(jié)點vl到vm的最短路徑條數(shù)，Nlm（eij）表示從節(jié)點vl到vm的最短路徑經(jīng)過邊eij（方向

35、相同）的條數(shù)。61612.4.5 介數(shù)和雙向比2.雙向比 雙向比，即兩兩節(jié)點間雙向邊的總數(shù)占網(wǎng)絡所有邊的比例。 假設有向圖中含有MB條雙向邊，則雙向比就是：RBMBM 。 例如下圖所示的有向圖，其雙向比為0.5。62622.4.6 中心性1.入度中心性和出度中心性 節(jié)點vi的入度中心性CD_in（vi）定義為 令vmax表示網(wǎng)絡G G中擁有最大入度中心性的節(jié)點，則網(wǎng)絡G G的入度中心性定義為 節(jié)點vi的出度中心性CD_out（vi）定義為 令vmax表示網(wǎng)絡G G中擁有最大出度中心性的節(jié)點，則網(wǎng)絡G G的出度中心性定義為63632.4.6 中心性2.介數(shù)中心性 節(jié)點vi的介數(shù)中心性CB（vi）

36、定義為 令vmax表示網(wǎng)絡G G中擁有最高介數(shù)中心性的節(jié)點，則網(wǎng)絡G G的介數(shù)中心性CB定義為6464返回 目錄2.5 加權網(wǎng)絡的靜態(tài)特征2.5.1 點權、單位權和權重分布差異性2.5.2 權度相關性和權權相關性2.5.3 距離分布和平均距離2.5.4 加權集聚系數(shù)2.5.5 介數(shù)分布和漏斗效應2.5.6 有向加權網(wǎng)絡的最短路徑問題65652.5.1 點權、單位權和權重分布差異性1.點權 節(jié)點vi的點權Si定義為式中，Ni表示節(jié)點vi的鄰點集合，wij表示連接節(jié)點vi和節(jié)點vj的邊的權重。 對于無向加權網(wǎng)絡，點權Si還可以用鄰接矩陣元素表示為式中，aij為鄰接矩陣元素（若節(jié)點vi與vj無連接則

37、aij0，若有連接則aij1）。 對于有向加權網(wǎng)絡，可定義入權和出權。66662.5.1 點權、單位權和權重分布差異性 入權Siin為以節(jié)點vi為終點的所有弧的邊權之和，而出權Siout為以節(jié)點vi為起點的所有弧的邊權之和，即而點權滿足2.單位權 單位權表示節(jié)點連接的平均權重，它定義為 對于有向加權網(wǎng)絡，也可以分別定義單位入權和單位出權如下67672.5.1 點權、單位權和權重分布差異性3.權重分布的差異性 節(jié)點vi的權重分布差異性Yi表示與節(jié)點vi相連的邊權分布的離散程度，定義為 對于無向加權網(wǎng)絡，可以用鄰接矩陣表示為 差異性與度有如下關系：如果與節(jié)點vi關聯(lián)的邊的權重值差別不大，則Yi1k

38、i；如果權值相差較大，例如只有一條邊的權重起主要作用，則Yi1。 對于有向加權網(wǎng)絡，也可以分別定義入權差異性和出權差異性，即68682.5.2 權度相關性和權權相關性1.基于節(jié)點的權度相關性 基于節(jié)點的權度相關性指的是對于單個節(jié)點來說，其點權和其度之間的相關性。 對于無向網(wǎng)絡，就是S和k的關系，其定義為式中，N為節(jié)點總數(shù)，P（k）為度分布函數(shù)。當邊權與網(wǎng)絡拓撲結(jié)構無關時，通常呈現(xiàn)Svv（k）wk的分布情況，其中w表示所有邊權的平均值；當邊權與網(wǎng)絡拓撲結(jié)構有關時，通常呈現(xiàn)Svv（k）Ak的分布情況（要么指數(shù)1，要么常數(shù)A）。 對于有向網(wǎng)絡，除了S和k的關系，還有Sinkin，Sinkout，So

39、utkin，Soutkout四種相關性。69692.5.2 權度相關性和權權相關性2.基于邊的權度相關性 基于邊的權度相關性類似于無向網(wǎng)絡的度度相關性，它考察的是較大權重的邊是傾向于與度值大的節(jié)點相連，還是傾向于與度值小的節(jié)點相連，還是根本沒有關系。 對于無向加權網(wǎng)絡，類似knn,i ，可定義節(jié)點的加權平均近鄰度為式中，kj表示節(jié)點vj的度值，aij為鄰接矩陣元素。若所有節(jié)點滿足kw_nn,iknn,i，則表明具有較大權重的邊傾向于連接具有較大度值的點。若所有節(jié)點滿足kw_nn,iknn,i，則表明具有較大權重的邊傾向于連接具有較小度值的點。70702.5.2 權度相關性和權權相關性 可定義所

40、有度為k的節(jié)點的加權平均近鄰度的平均值kw_nn（k）為若曲線斜率大于0，表示具有正相關性；若曲線斜率小于0，表示具有負相關性；若曲線斜率為0，表示不相關。 類似地，也可以研究有向網(wǎng)絡基于弧的權度相關性。任意選取一條弧，在弧的兩端各存在兩個度值，所以存在四種相關性，加權平均近鄰入度與入度、加權平均近鄰出度與入度、加權平均近鄰入度與出度、加權平均近鄰出度與出度，分別記做kw_in-in（kin）kin，kw_out-in（kin）kin，kw_in-out（kout）kout，kw_out-out（kout）kout。71712.5.2 權度相關性和權權相關性3.權權相關性 權相關性有兩類，一類

41、是點權點權相關性，一類是單位權單位權相關性，定義方式差不多，這里以點權為例。 對于無向加權網(wǎng)絡，類似knn,i ，可定義節(jié)點的加權平均近鄰權為 于是所有點權為S的節(jié)點的加權平均近鄰權的平均值Snn（S）為72722.5.2 權度相關性和權權相關性 類似地，也可以研究有向網(wǎng)絡基于弧的權權相關性。任意選取一條弧，在弧的兩端各存在兩個權值，所以存在四種相關性，分別是起點入權終點入權，起點出權終點入權，終點入權起點出權以及終點出權起點出權,分別記做Sin-in（Sin）Sin，Sout-in（Sin）Sin，Sin-out（Sout）Sout，Sout-out（Sout）Sout。73732.5.3

42、距離分布和平均距離 若邊eij的權重wij表示相異權，則其長度dijwij；若wij表示相似權，則其長度dijwij。假設節(jié)點vi和vk通過兩條權重分別為wij和wjk的邊相連，則在相異權情況下，vi和vk之間的距離dikwijwjk；而在相似權情況下，vi和vk之間的距離dik1wij1wjk。 加權網(wǎng)絡中的最短路徑是指在兩點之間所有連通的路徑中，相異權權重之和（相似權權重倒數(shù)之和）最小的一條或幾條路徑。距離分布P（d）是指距離為d的節(jié)點對數(shù)占總節(jié)點對數(shù)的比重。 無向連通簡單加權網(wǎng)絡的平均距離L定義為 有向連通簡單加權網(wǎng)絡的平均距離L定義為74742.5.4 加權集聚系數(shù) Barrat定義式

43、 Onnela定義式式中， 表示歸一化權重。 Holme定義式75752.5.4 加權集聚系數(shù)【例例2.42.4】分別計算下圖所示網(wǎng)絡（設權值為相似權）的下述特性：（1）分別求出各節(jié)點的點權、單位權、權重差異性；（2）求出網(wǎng)絡的基于節(jié)點的權度相關性Svv（k）；（3）根據(jù)集聚系數(shù)的Holme定義式，求出各節(jié)點的加權集聚系數(shù)。解：（1）節(jié)點v1v6的點權Si分別為：4、7、13、9、11、8；單位權Ui分別為：2、 73、133、3、114、83；權重差異性Yi分別為：58、37、57169、3581、31121、1332。76762.5.4 加權集聚系數(shù)（2）該網(wǎng)絡的度分布如下表所示 可得基于

44、節(jié)點的權度相關性Svv（k）如下表所示（3）節(jié)點v1v6的加權集聚系數(shù)分別為：23、328、114、29115、19、2976。77772.5.5 介數(shù)分布和漏斗效應 介數(shù)是用來衡量通過網(wǎng)絡中某節(jié)點或某條邊的最短路徑的數(shù)目。在科學家網(wǎng)絡中，介數(shù)反映了在本領域內(nèi)，某位科學家影響力的大小。某一節(jié)點的近鄰節(jié)點介數(shù)分布的兩極分化性質(zhì)稱為漏斗效應，也就是說只和本領域的1個或2個著名成員合作就能夠很容易與合作網(wǎng)絡大部分成員建立最短路徑，而所有這些短路徑都將通過這幾個著名成員。而全部節(jié)點的介數(shù)分布反映的是科學家影響力的層次。邊的介數(shù)反映的是不同科學家之間的交流對學科發(fā)展影響力的不同。同時，利用邊的介數(shù)也可以

45、對科學家做聚類分析。78782.5.6 有向加權網(wǎng)絡的最短路徑問題1.最短路徑問題 算法具體形式包括：已知起始節(jié)點，求最短路徑的問題。已知終止節(jié)點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題。已知起點和終點，求兩節(jié)點之間的最短路徑。全局最短路徑問題，即求圖中所有的最短路徑。2. Dijkstra算法3. Bellman-Ford算法4. Floyd-Warshall算法7979返回 目錄2.6 網(wǎng)絡的其他靜態(tài)特征2.6.1 網(wǎng)絡結(jié)構熵2.6.2 特征譜2.6.3 度秩函數(shù)2.6.4 富人俱樂部系數(shù)80802.6.1 網(wǎng)絡結(jié)構熵 假設網(wǎng)絡中節(jié)點vi的度為ki，則其重要度可定義為對于ki0的節(jié)點不作考慮，可以定義網(wǎng)絡結(jié)構熵為當網(wǎng)絡完全均勻，即Ii1N時，EmaxlnN。當網(wǎng)絡最不均勻，即I112，Ii12（N1）（i1）時，Eminln4（N1）2。 為了消除節(jié)點數(shù)目N對E的影響，可以對網(wǎng)絡結(jié)構熵進行歸一化，定義為網(wǎng)絡標準結(jié)構熵。顯然 。81812.6.1 網(wǎng)絡結(jié)構熵 網(wǎng)絡結(jié)構熵與度分布的關系就如同隨機變量的數(shù)字特征與其概率分布函數(shù)的關系。兩者是互為補充的，網(wǎng)絡結(jié)構熵是由度分布