復雜網(wǎng)絡基礎理論第二章

1、復雜網(wǎng)絡基礎理論,第二章 網(wǎng)絡拓撲結構與靜態(tài)特征,第二章 網(wǎng)絡拓撲結構與靜態(tài)特征,2.1 引言 2.2 網(wǎng)絡的基本靜態(tài)幾何特征 2.3 無向網(wǎng)絡的靜態(tài)特征 2.4 有向網(wǎng)絡的靜態(tài)特征 2.5 加權網(wǎng)絡的靜態(tài)特征 2.6 網(wǎng)絡的其他靜態(tài)特征 2.7 復雜網(wǎng)絡分析軟件,2,2.1 引言,與圖論的研究有所不同，復雜網(wǎng)絡的研究更側重于從各種實際網(wǎng)絡的現(xiàn)象之上抽象出一般的網(wǎng)絡幾何量，并用這些一般性質指導更多實際網(wǎng)絡的研究，進而通過討論實際網(wǎng)絡上的具體現(xiàn)象發(fā)展網(wǎng)絡模型的一般方法，最后討論網(wǎng)絡本身的形成機制。 統(tǒng)計物理學在模型研究、演化機制與結構穩(wěn)定性方面的豐富的研究經(jīng)驗是統(tǒng)計物理學在復雜網(wǎng)絡研究領域得到廣

2、泛應用的原因；而圖論與社會網(wǎng)絡分析提供的網(wǎng)絡靜態(tài)幾何量及其分析方法是復雜網(wǎng)絡研究的基礎。,3,2.1 引言,靜態(tài)特征指給定網(wǎng)絡的微觀量的統(tǒng)計分布或宏觀統(tǒng)計平均值。 在本章中我們將對網(wǎng)絡的各種靜態(tài)特征做一小結。由于有向網(wǎng)絡與加權網(wǎng)絡有其特有的特征量，我們將分開討論無向、有向與加權網(wǎng)絡。,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,2.2.1 平均距離,1.網(wǎng)絡的直徑與平均距離 網(wǎng)絡中的兩節(jié)點vi和vj之間經(jīng)歷邊數(shù)最少的一條簡單路徑（經(jīng)歷的邊各不相同），稱為測地線。 測地線的邊數(shù)dij稱為兩節(jié)點

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

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

5、 對于有向網(wǎng)絡來說，這ki個節(jié)點間可能存在的最大弧數(shù)為ki（ki1），此時vi的集聚系數(shù)CiMiki（ki1）。 將該集聚系數(shù)對整個網(wǎng)絡作平均，可得網(wǎng)絡的平均集聚系數(shù)為,10,2.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相連的“三角形”數(shù)目，數(shù)值上就等于Mi；Ni

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

7、系數(shù)。 解：首先計算出所有節(jié)點對的距離：d121；d131；d142；d151；d162；d231；d241；d252；d262；d342；d352；d361；d453；d461；d563。由此可得直徑和平均距離為,13,2.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的前三次冪為,14,2.2.2 集聚系數(shù),故

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

9、滿足一定的概率分布的。定義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）對于,17,2.2.3 度分布,任意給定常數(shù)a存在常數(shù)b使得F（x）滿足F（ax）bF（x）。冪律分布是唯一滿足無標度條件的概率分布函數(shù)。許多實

10、際大規(guī)模無標度網(wǎng)絡，其冪指數(shù)通常為23，絕大多數(shù)節(jié)點的度相對很低，也存在少量度值相對很高的節(jié)點（稱為hub），把這類網(wǎng)絡稱為非均勻網(wǎng)絡。 指數(shù)度分布網(wǎng)絡： P（k）ek/，式中0為一常數(shù)。,18,2.2.3 度分布,3.累積度分布 可以用累積度分布函數(shù)來描述度的分布情況，它與度分布的關系為 它表示度不小于k的節(jié)點的概率分布。 若度分布為冪律分布，即P（k）k，則相應的累積度分布函數(shù)符合冪指數(shù)為1的冪律分布 若度分布為指數(shù)分布，即P（k）ek/，則相應的累積度分布函數(shù)符合同指數(shù)的指數(shù)分布,19,2.2.4 實際網(wǎng)絡的統(tǒng)計特征,20,返回 目錄,2.3 無向網(wǎng)絡的靜態(tài)特征,2.3.1 聯(lián)合度分布和

11、度度相關性 2.3.2 集聚系數(shù)分布和聚度相關性 2.3.3 介數(shù)和核度 2.3.4 中心性 2.3.5 網(wǎng)絡密度 2.3.6 連通集團（子圖）及其規(guī)模分布,21,2.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）。,22,2.3.1 聯(lián)合度分布和度度相關性,聯(lián)合節(jié)點度分布所包含的拓撲信息最多，節(jié)點度分布次之，平

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

13、關特性，稱之為異配網(wǎng)絡。 3.基于Pearson相關系數(shù)的度度相關性 Newman利用邊兩端節(jié)點的度的Pearson相關系數(shù)r來描述網(wǎng)絡的度度相關性，具體定義為,24,2.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)絡是不相關的。,25,2.3.2 集聚系數(shù)分布和聚度相關性,1.集聚系數(shù)分布 集聚系數(shù)分布函數(shù)P（C）表示從網(wǎng)絡中任選一節(jié)點，其集聚系數(shù)值為C的概率 式中，（x）為單位沖激函數(shù)。 2.聚度相關性 局部集聚系數(shù)C（k）定義為度為k的節(jié)點

14、的鄰居之間存在的平均邊數(shù)Mnn（k）與這些鄰居之間存在的最大可能的邊數(shù)的比值，即,26,2.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)絡。,27,2.3.3 介數(shù)和核度,1.介數(shù) 要衡量一個節(jié)點的重要性，其度值當然可以作為一個衡量指標，但又不盡然，例如在社會網(wǎng)絡中，有的節(jié)點的度雖然很小，但它可能是兩個社團的中間聯(lián)絡人，如果去掉該節(jié)點

15、，那么就會導致兩個社團的聯(lián)系中斷，因此該節(jié)點在網(wǎng)絡中起到極其重要的作用。對于這樣的節(jié)點，需要定義另一種衡量指標，這就引出網(wǎng)絡的另一種重要的全局幾何量介數(shù)。 介數(shù)分為節(jié)點介數(shù)和邊介數(shù)兩種，反映了節(jié)點或邊在整個網(wǎng)絡中的作用和影響力。,28,2.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ù)。,29,2.3.3 介數(shù)和核度,2.介數(shù)分布和介度相關性 節(jié)點

16、的介數(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)絡的同步能力越弱。,30,2.3.3 介數(shù)和核度,3.核度 一個圖的k核是指反復去掉度值小于k的節(jié)點及其連線后，所剩余的子圖，該子圖的節(jié)點數(shù)就是該核的大小。 若一個節(jié)點屬于k核，而不屬于（k1）核，則此節(jié)點的核度為k。

17、 節(jié)點核度的最大值叫做網(wǎng)絡的核度。 節(jié)點的核度可以說明節(jié)點在核中的深度，核度的最大值自然就對應著網(wǎng)絡結構中最中心的位置。k核解析可用來描述度分布所不能描述的網(wǎng)絡特征，揭示源于系統(tǒng)特殊結構的結構和層次性質。,31,2.3.3 介數(shù)和核度,【例2.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)絡的核度。,32,2.3.3 介數(shù)和核度,解：（1）該網(wǎng)絡的度分布如下表

18、所示。 因此 或 （2）根據(jù) 容易得到聯(lián)合度分布如下表所示。 由此可以驗證 的正確性，例如當k1時，該式左邊P（1）=16，而右邊為,33,2.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；

19、v2e4v3；v2e5v4；v2e2v1e1v5；v2e4v3e7v6；v2e5v4e6v6；v3e4v2e5v4；v3e7v6e6v4；v3e3v1e1v5；v3e7v6；v4e5v2e2v1e1v5；v4e6v6；v5e1v1e3v3e7v6。,34,2.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。,35,2.3.4 中心性,1.度中心性 度中心性分為

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

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

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

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

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

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

26、布情況。實證研究表明，對于大量的無標度網(wǎng)絡，連通集團的規(guī)模也存在冪律分布。例如，科學家合作網(wǎng)的連通子圖規(guī)模分布。,45,返回 目錄,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 中心性,46,2.4.1 入度和出度及其分布,1.入度與出度 由于與有向網(wǎng)絡某個節(jié)點相關聯(lián)的弧有指向節(jié)點的，也有背向節(jié)點向外的，因此除了可以統(tǒng)計與某個節(jié)點相關聯(lián)的弧數(shù)，也就是度之外，有必要分開統(tǒng)計兩個方向的弧數(shù)，分別稱為節(jié)點的入度和出度。 節(jié)點vi的入度、出度和有向圖的鄰接矩陣以

27、及度的關系為,47,2.4.1 入度和出度及其分布,同平均度一樣，也可以求平均入度kin和平均出度kout為 2.入度分布和出度分布 入度分布和出度分布分別記為Pin（k）和Pout（k），分別表示網(wǎng)絡中任意取出一個節(jié)點，其入度值和出度值剛好為k的概率。 入（出）度分布與平均入（出）度之間具有如下關系式,48,2.4.1 入度和出度及其分布,3.累積入度分布和累積出度分布 累積入（出）度分布與入（出）度分布的關系為 容易證明入（出）度冪律分布對應的累積分布也是冪律分布，入（出）度指數(shù)分布對應的累積分布也是同指數(shù)的指數(shù)分布。 4.聯(lián)合度分布 聯(lián)合度分布有兩種定義方式，第一種定義方式是基于弧的方式

28、，第二種定義方式是基于節(jié)點的方式。,49,2.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； jin，jout）。 若對上式按照（kin，kout）求和，就得到隨機選取一條弧，該弧起點

29、的度為（jin，jout）的概率,50,2.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）具有如下關系式,51,2.4.2 度度相關性,度度相關性也有兩種定義方式，即基于節(jié)點的方式和基于弧的方式。 1.基于節(jié)點的入度出度相關性 可以定義節(jié)點的入度為ki

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

31、ut）kout。這四種相關性可分別定義如下,53,2.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為,54,2.4.4 入集團和出集團的集聚程度,對于某個節(jié)點vi來說，所有以該節(jié)點為終點的弧的起始節(jié)點及它們之間的連弧構成一個小集團，稱之

32、為入集團；而所有以該節(jié)點為起點的弧的終止節(jié)點及它們之間的連弧構成一個小集團，稱之為出集團。 由于節(jié)點vi的入度為kiin，則連向該節(jié)點的kiin個起始節(jié)點間可能存在的最大弧數(shù)為kiin（kiin1），而實際存在的弧數(shù)為Miin，由此定義 為節(jié)點vi的入集聚系數(shù)，然后將該集聚系數(shù)對整個網(wǎng)絡作平均，即 可得網(wǎng)絡的入集團的集聚系數(shù)。,55,2.4.4 入集團和出集團的集聚程度,同理，定義 為節(jié)點vi的出集聚系數(shù)，然后將該集聚系數(shù)對整個網(wǎng)絡作平均，即 可得網(wǎng)絡的出集團的集聚系數(shù)。,56,2.4.4 入集團和出集團的集聚程度,【例2.3】針對下圖所示網(wǎng)絡分別計算： （1）寫出該網(wǎng)絡的鄰接矩陣、入度分布及

33、出度分布； （2）分別求出該網(wǎng)絡的Pf（kin，kout）、Pt（kin，kout）和Pv（kin，kout）； （3）整個網(wǎng)絡的入集團和出集團的集聚系數(shù)。,57,2.4.4 入集團和出集團的集聚程度,解：（1）該網(wǎng)絡的鄰接矩陣為 入度分布如下表所示 出度分布如下表所示 （2）聯(lián)合概率分布Pe（jin，jout；kin，kout）如下表所示,58,2.4.4 入集團和出集團的集聚程度,由上表可得Pf（jin，jout），如下表所示 Pt（kin，kout）如下表所示 Pv（kin，kout）如下表所示,59,2.4.4 入集團和出集團的集聚程度,（3）以節(jié)點v5為例，其對應的入集團如下圖所示，

34、由此可計算出節(jié)點v5的入集團集聚系數(shù) 同理可計算出每個節(jié)點的入集團的集聚系數(shù)為：0、0、0、12、16、0。而每個節(jié)點的出集團的集聚系數(shù)為：12、0、0、0、0、13。因此，可得網(wǎng)絡的入集團和出集團集聚系數(shù)分別為19和536。,60,2.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（方向相同）的條數(shù)。,61,2.4.5 介數(shù)和雙向比,2.雙向比 雙

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

36、心性CB定義為,64,返回 目錄,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)絡的最短路徑問題,65,2.5.1 點權、單位權和權重分布差異性,1.點權 節(jié)點vi的點權Si定義為 式中，Ni表示節(jié)點vi的鄰點集合，wij表示連接節(jié)點vi和節(jié)點vj的邊的權重。 對于無向加權網(wǎng)絡，點權Si還可以用鄰接矩陣元素表示為 式中，aij為鄰接矩陣元素（若節(jié)點vi與vj無連接則aij0，若有連接則aij1）。 對于有向加權網(wǎng)絡，可定義入

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

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

39、.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，則表明具有較大權重的邊傾向于連接具有較小度值的點。,70,2.5.2 權度相關性和權權相關性,可定義所有度為k的節(jié)點的加權平均近鄰度的平均值kw_n

40、n（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。,71,2.5.2 權度相關性和權權相關性,3.權權相關性 權相關性有兩類，一類是點權點權相關性，一類是單位權單位權相關性

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

42、表示相異權，則其長度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定義為,74,2.5.4 加權集聚系數(shù),Barrat定義式 Onnela定義式 式中， 表示歸一化權

43、重。 Holme定義式,75,2.5.4 加權集聚系數(shù),【例2.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。,76,2.5.4 加權集聚系數(shù),（2）該網(wǎng)絡的度分布如下表所示 可得基于節(jié)點的權度相關性Svv（k）如下表所

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

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