復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論 第二章課件

復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論

第二章網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與靜態(tài)特征復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章第二章網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與靜態(tài)特征2.1引言2.2網(wǎng)絡(luò)的基本靜態(tài)幾何特征2.3無向網(wǎng)絡(luò)的靜態(tài)特征2.4有向網(wǎng)絡(luò)的靜態(tài)特征2.5加權(quán)網(wǎng)絡(luò)的靜態(tài)特征2.6網(wǎng)絡(luò)的其他靜態(tài)特征2.7復(fù)雜網(wǎng)絡(luò)分析軟件2復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.1引言與圖論的研究有所不同，復(fù)雜網(wǎng)絡(luò)的研究更側(cè)重于從各種實(shí)際網(wǎng)絡(luò)的現(xiàn)象之上抽象出一般的網(wǎng)絡(luò)幾何量，并用這些一般性質(zhì)指導(dǎo)更多實(shí)際網(wǎng)絡(luò)的研究，進(jìn)而通過討論實(shí)際網(wǎng)絡(luò)上的具體現(xiàn)象發(fā)展網(wǎng)絡(luò)模型的一般方法，最后討論網(wǎng)絡(luò)本身的形成機(jī)制。統(tǒng)計(jì)物理學(xué)在模型研究、演化機(jī)制與結(jié)構(gòu)穩(wěn)定性方面的豐富的研究經(jīng)驗(yàn)是統(tǒng)計(jì)物理學(xué)在復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域得到廣泛應(yīng)用的原因；而圖論與社會網(wǎng)絡(luò)分析提供的網(wǎng)絡(luò)靜態(tài)幾何量及其分析方法是復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ)。3復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.1引言

靜態(tài)特征指給定網(wǎng)絡(luò)的微觀量的統(tǒng)計(jì)分布或宏觀統(tǒng)計(jì)平均值。在本章中我們將對網(wǎng)絡(luò)的各種靜態(tài)特征做一小結(jié)。由于有向網(wǎng)絡(luò)與加權(quán)網(wǎng)絡(luò)有其特有的特征量，我們將分開討論無向、有向與加權(quán)網(wǎng)絡(luò)。返回目錄4復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2網(wǎng)絡(luò)的基本靜態(tài)幾何特征2.2.1平均距離2.2.2集聚系數(shù)2.2.3度分布2.2.4實(shí)際網(wǎng)絡(luò)的統(tǒng)計(jì)特征5復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.1平均距離1.網(wǎng)絡(luò)的直徑與平均距離網(wǎng)絡(luò)中的兩節(jié)點(diǎn)vi和vj之間經(jīng)歷邊數(shù)最少的一條簡單路徑（經(jīng)歷的邊各不相同），稱為測地線。

測地線的邊數(shù)dij稱為兩節(jié)點(diǎn)vi和vj之間的距離（或叫測地線距離）。1／dij稱為節(jié)點(diǎn)vi和vj之間的效率，記為εij。通常效率用來度量節(jié)點(diǎn)間的信息傳遞速度。當(dāng)vi和vj之間沒有路徑連通時，dij＝∞，而εij＝0，所以效率更適合度量非全通網(wǎng)絡(luò)。

網(wǎng)絡(luò)的直徑D定義為所有距離dij中的最大值6復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.1平均距離

平均距離（特征路徑長度）L定義為所有節(jié)點(diǎn)對之間距離的平均值，它描述了網(wǎng)絡(luò)中節(jié)點(diǎn)間的平均分離程度，即網(wǎng)絡(luò)有多小，計(jì)算公式為

對于無向簡單圖來說，dij＝dji且dii＝0，則上式可簡化為

很多實(shí)際網(wǎng)絡(luò)雖然節(jié)點(diǎn)數(shù)巨大，但平均距離卻小得驚人，這就是所謂的小世界效應(yīng)。7復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.1平均距離2.距離與鄰接矩陣的關(guān)系定義對于無權(quán)簡單圖來說，當(dāng)l＝1時，。容易證明無權(quán)簡單圖鄰接矩陣A的l次冪Al的元素

表示節(jié)點(diǎn)vi和vj之間通過l條邊連接的路徑數(shù)。當(dāng)l＝2時，容易推出式中，U表示單位指示函數(shù)，即當(dāng)x＞0，U（x）＝1；否則U（x）＝0。當(dāng)i＝j(luò)時，δij＝1；否則δij＝0。8復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.1平均距離

容易用數(shù)學(xué)歸納法證明據(jù)此，若D為網(wǎng)絡(luò)直徑，則兩節(jié)點(diǎn)vi和vj之間的距離dij可以表示為9復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.2集聚系數(shù)

首先來看節(jié)點(diǎn)的集聚系數(shù)定義。假設(shè)節(jié)點(diǎn)vi與ki個節(jié)點(diǎn)直接連接，那么對于無向網(wǎng)絡(luò)來說，這ki個節(jié)點(diǎn)間可能存在的最大邊數(shù)為ki（ki－1）／2，而實(shí)際存在的邊數(shù)為Mi，由此我們定義Ci＝2Mi／［ki（ki－1）］為節(jié)點(diǎn)vi的集聚系數(shù)。

對于有向網(wǎng)絡(luò)來說，這ki個節(jié)點(diǎn)間可能存在的最大弧數(shù)為ki（ki－1），此時vi的集聚系數(shù)Ci＝Mi／［ki（ki－1）］。

將該集聚系數(shù)對整個網(wǎng)絡(luò)作平均，可得網(wǎng)絡(luò)的平均集聚系數(shù)為10復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.2集聚系數(shù)

顯然，0≤C≤1。當(dāng)C＝0，所有節(jié)點(diǎn)都是孤立節(jié)點(diǎn)，沒有邊連接。當(dāng)C＝1時，網(wǎng)絡(luò)為所有節(jié)點(diǎn)兩兩之間都有邊連接的完全圖。對于完全隨機(jī)網(wǎng)絡(luò)來說，當(dāng)節(jié)點(diǎn)數(shù)很大時，C→O（1／N）。而許多大規(guī)模的實(shí)際網(wǎng)絡(luò)的集聚系數(shù)通常遠(yuǎn)小于1而大于O（1／N)。對于社會網(wǎng)絡(luò)來說，通常隨著N→∞，集聚系數(shù)C→O（1），即趨向一個非零常數(shù)。

節(jié)點(diǎn)vi的集聚系數(shù)也可定義為Ci＝NiΔ／NiΛ。式中NiΔ代表與節(jié)點(diǎn)vi相連的“三角形”數(shù)目，數(shù)值上就等于Mi；NiΛ代表與節(jié)點(diǎn)vi相連的“三元組”數(shù)目，即節(jié)點(diǎn)vi與其它兩個節(jié)點(diǎn)都有連接，即“至少與其他兩個分別認(rèn)識”，數(shù)值上就等于ki（ki－1）／2。11復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.2集聚系數(shù)

如何根據(jù)無向無權(quán)簡單圖的鄰接矩陣A來求節(jié)點(diǎn)vi的集聚系數(shù)Ci？

顯然，鄰接矩陣二次冪A2的對角元素

表示的是與節(jié)點(diǎn)vi相連的邊數(shù)，也就是節(jié)點(diǎn)vi的度ki。而鄰接矩陣三次冪A3的對角元素

＝∑（aij·ajl·ali）（j≠l）表示的是從節(jié)點(diǎn)vi出發(fā)經(jīng)過三條邊回到節(jié)點(diǎn)vi的路徑數(shù)，也就是與節(jié)點(diǎn)vi相連的三角形數(shù)的兩倍（正向走和反向走）。因此，由集聚系數(shù)的定義可知12復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.2集聚系數(shù)【例2.1】計(jì)算下面簡單網(wǎng)絡(luò)的直徑、平均距離和各節(jié)點(diǎn)的集聚系數(shù)。解：首先計(jì)算出所有節(jié)點(diǎn)對的距離：d12＝1；d13＝1；d14＝2；d15＝1；d16＝2；d23＝1；d24＝1；d25＝2；d26＝2；d34＝2；d35＝2；d36＝1；d45＝3；d46＝1；d56＝3。由此可得直徑和平均距離為13復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.2集聚系數(shù)

下面以節(jié)點(diǎn)v1的集聚系數(shù)計(jì)算為例：采用第一種定義可知，節(jié)點(diǎn)v1與3個節(jié)點(diǎn)直接連接，而這3個節(jié)點(diǎn)之間可能存在的最大邊數(shù)為3（3－1）／2，而實(shí)際存在的邊數(shù)為1，由此可得C1＝2／［3（3－1）］＝1／3。

若采用第二種定義可知：與相連的三角形數(shù)為N1Δ＝１，而與v1相連的三元組數(shù)為N1Λ＝3，故C1＝1／3。

也可以利用式

計(jì)算，因?yàn)猷徑泳仃嘇的前三次冪為14復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.2集聚系數(shù)故＝2，

＝3，從而同理可得其他各節(jié)點(diǎn)的集聚系數(shù)為C2＝1／3；C3＝1／3；C4＝0；C5＝0；C6＝0由此很容易算出該網(wǎng)絡(luò)的集聚系數(shù)15復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.3度分布1.節(jié)點(diǎn)的度

在網(wǎng)絡(luò)中，節(jié)點(diǎn)vi的鄰邊數(shù)ki稱為該節(jié)點(diǎn)vi的度。

對網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度求平均，可得到網(wǎng)絡(luò)的平均度＜k＞

無向無權(quán)圖鄰接矩陣A的二次冪A2的對角元素

就是節(jié)點(diǎn)vi的鄰邊數(shù)，即

。實(shí)際上，無向無權(quán)圖鄰接矩陣A的第i行或第i列元素之和也是度。從而無向無權(quán)網(wǎng)絡(luò)的平均度就是A2對角線元素之和除以節(jié)點(diǎn)數(shù)，即＜k＞＝tr（A2）／N。式中，tr（A2）表示矩陣A2的跡，即對角線元素之和。16復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.3度分布2.度分布

大多數(shù)實(shí)際網(wǎng)絡(luò)中的節(jié)點(diǎn)的度是滿足一定的概率分布的。定義P（k）為網(wǎng)絡(luò)中度為k的節(jié)點(diǎn)在整個網(wǎng)絡(luò)中所占的比率。

規(guī)則網(wǎng)絡(luò)：由于每個節(jié)點(diǎn)具有相同的度，所以其度分布集中在一個單一尖峰上，是一種Delta分布。完全隨機(jī)網(wǎng)絡(luò)：度分布具有Poisson分布的形式，每一條邊的出現(xiàn)概率是相等的，大多數(shù)節(jié)點(diǎn)的度是基本相同的，并接近于網(wǎng)絡(luò)平均度＜k＞，遠(yuǎn)離峰值＜k＞，度分布則按指數(shù)形式急劇下降。把這類網(wǎng)絡(luò)稱為均勻網(wǎng)絡(luò)。無標(biāo)度網(wǎng)絡(luò)：具有冪指數(shù)形式的度分布：P（k）∝k?γ。所謂無標(biāo)度是指一個概率分布函數(shù)F（x）對于17復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.3度分布任意給定常數(shù)a存在常數(shù)b使得F（x）滿足F（ax）＝bF（x）。冪律分布是唯一滿足無標(biāo)度條件的概率分布函數(shù)。許多實(shí)際大規(guī)模無標(biāo)度網(wǎng)絡(luò)，其冪指數(shù)通常為2≤γ≤3，絕大多數(shù)節(jié)點(diǎn)的度相對很低，也存在少量度值相對很高的節(jié)點(diǎn)（稱為hub），把這類網(wǎng)絡(luò)稱為非均勻網(wǎng)絡(luò)。

指數(shù)度分布網(wǎng)絡(luò)：P（k）∝e?k/к，式中к＞0為一常數(shù)。18復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.3度分布3.累積度分布

可以用累積度分布函數(shù)來描述度的分布情況，它與度分布的關(guān)系為它表示度不小于k的節(jié)點(diǎn)的概率分布。

若度分布為冪律分布，即P（k）∝k?γ，則相應(yīng)的累積度分布函數(shù)符合冪指數(shù)為γ－1的冪律分布

若度分布為指數(shù)分布，即P（k）∝e?k/к，則相應(yīng)的累積度分布函數(shù)符合同指數(shù)的指數(shù)分布19復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.2.4實(shí)際網(wǎng)絡(luò)的統(tǒng)計(jì)特征返回目錄20復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3無向網(wǎng)絡(luò)的靜態(tài)特征2.3.1聯(lián)合度分布和度－度相關(guān)性2.3.2集聚系數(shù)分布和聚－度相關(guān)性2.3.3介數(shù)和核度2.3.4中心性2.3.5網(wǎng)絡(luò)密度2.3.6連通集團(tuán)（子圖）及其規(guī)模分布21復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.1聯(lián)合度分布和度－度相關(guān)性1.聯(lián)合度分布

度分布滿足

平均度與度分布具有關(guān)系式

聯(lián)合度分布定義為從無向網(wǎng)絡(luò)中隨機(jī)選擇一條邊，該邊的兩個節(jié)點(diǎn)的度值分別為k1和k2的概率，即式中，M（k1，k2）為度值為k1的節(jié)點(diǎn)和度值為k2的節(jié)點(diǎn)相連的總邊數(shù)，M為網(wǎng)絡(luò)總邊數(shù)。

從聯(lián)合度分布可以得出度分布式中，

＝1（k＝k2）；

＝0（k≠k2）。22復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.1聯(lián)合度分布和度－度相關(guān)性

聯(lián)合節(jié)點(diǎn)度分布所包含的拓?fù)湫畔⒆疃?，?jié)點(diǎn)度分布次之，平均節(jié)點(diǎn)度最少。2.基于最近鄰平均度值的度－度相關(guān)性

度－度相關(guān)性描述了網(wǎng)絡(luò)中度大的節(jié)點(diǎn)和度小的節(jié)點(diǎn)之間的關(guān)系。若度大的節(jié)點(diǎn)傾向于和度大的節(jié)點(diǎn)連接，則網(wǎng)絡(luò)是度－度正相關(guān)的；反之，若度大的節(jié)點(diǎn)傾向于和度小的節(jié)點(diǎn)連接，則網(wǎng)絡(luò)是度－度負(fù)相關(guān)的。

節(jié)點(diǎn)vi的最近鄰平均度值定義為式中，ki表示節(jié)點(diǎn)vi的度值，aij為鄰接矩陣元素。23復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.1聯(lián)合度分布和度－度相關(guān)性

所有度值為k的節(jié)點(diǎn)的最近鄰平均度值的平均值knn（k）定義為式中，N為節(jié)點(diǎn)總數(shù)，P（k）為度分布函數(shù)。

如果knn（k）是隨著k上升的增函數(shù)，則說明度值大的節(jié)點(diǎn)傾向于和度值大的節(jié)點(diǎn)連接，網(wǎng)絡(luò)具有正相關(guān)特性，稱之為同配網(wǎng)絡(luò)；反之網(wǎng)絡(luò)具有負(fù)相關(guān)特性，稱之為異配網(wǎng)絡(luò)。3.基于Pearson相關(guān)系數(shù)的度－度相關(guān)性Newman利用邊兩端節(jié)點(diǎn)的度的Pearson相關(guān)系數(shù)r來描述網(wǎng)絡(luò)的度－度相關(guān)性，具體定義為24復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.1聯(lián)合度分布和度－度相關(guān)性式中，ki，kj分別表示邊eij的兩個節(jié)點(diǎn)vi，vj的度，M表示網(wǎng)絡(luò)的總邊數(shù)。

容易證明度－度相關(guān)系數(shù)r的范圍為：0≤|r|≤1。當(dāng)r<0時，網(wǎng)絡(luò)是負(fù)相關(guān)的；當(dāng)r>0時，網(wǎng)絡(luò)是正相關(guān)的；當(dāng)r＝0時，網(wǎng)絡(luò)是不相關(guān)的。25復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.2集聚系數(shù)分布和聚－度相關(guān)性1.集聚系數(shù)分布

集聚系數(shù)分布函數(shù)P（C）表示從網(wǎng)絡(luò)中任選一節(jié)點(diǎn)，其集聚系數(shù)值為C的概率式中，δ（x）為單位沖激函數(shù)。2.聚－度相關(guān)性

局部集聚系數(shù)C（k）定義為度為k的節(jié)點(diǎn)的鄰居之間存在的平均邊數(shù)＜Mnn（k）＞與這些鄰居之間存在的最大可能的邊數(shù)的比值，即26復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.2集聚系數(shù)分布和聚－度相關(guān)性

全局集聚系數(shù)C則定義為式中，＜k2＞為度的二階矩。

顯然，局部集聚系數(shù)C（k）與k的關(guān)系刻畫了網(wǎng)絡(luò)的聚－度相關(guān)性。許多真實(shí)網(wǎng)絡(luò)如好萊塢電影演員合作網(wǎng)絡(luò)、語義網(wǎng)絡(luò)中節(jié)點(diǎn)的聚－度相關(guān)性存在近似的倒數(shù)關(guān)系C（k）∝k?1。把這種倒數(shù)關(guān)系的聚－度相關(guān)性稱為層次性，把具有層次性的網(wǎng)絡(luò)稱為層次網(wǎng)絡(luò)。27復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.3介數(shù)和核度1.介數(shù)

要衡量一個節(jié)點(diǎn)的重要性，其度值當(dāng)然可以作為一個衡量指標(biāo)，但又不盡然，例如在社會網(wǎng)絡(luò)中，有的節(jié)點(diǎn)的度雖然很小，但它可能是兩個社團(tuán)的中間聯(lián)絡(luò)人，如果去掉該節(jié)點(diǎn)，那么就會導(dǎo)致兩個社團(tuán)的聯(lián)系中斷，因此該節(jié)點(diǎn)在網(wǎng)絡(luò)中起到極其重要的作用。對于這樣的節(jié)點(diǎn)，需要定義另一種衡量指標(biāo)，這就引出網(wǎng)絡(luò)的另一種重要的全局幾何量——介數(shù)。

介數(shù)分為節(jié)點(diǎn)介數(shù)和邊介數(shù)兩種，反映了節(jié)點(diǎn)或邊在整個網(wǎng)絡(luò)中的作用和影響力。28復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.3介數(shù)和核度節(jié)點(diǎn)的介數(shù)Bi定義為式中，Njl表示節(jié)點(diǎn)vj和vl之間的最短路徑條數(shù)，Njl（i）表示節(jié)點(diǎn)vj和vl之間的最短路徑經(jīng)過節(jié)點(diǎn)vi的條數(shù)。

邊的介數(shù)Bij定義為式中，Nlm表示節(jié)點(diǎn)vl和vm之間的最短路徑條數(shù)，Nlm（eij）表示節(jié)點(diǎn)vl和vm之間的最短路徑經(jīng)過邊eij的條數(shù)。29復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.3介數(shù)和核度2.介數(shù)分布和介－度相關(guān)性

節(jié)點(diǎn)的介數(shù)與度之間有很強(qiáng)的相關(guān)性，而且不同類型的網(wǎng)絡(luò)，其介數(shù)分布也大不一樣。

介－度相關(guān)性可以用B（k）～k表示，它定義為所有度為k的節(jié)點(diǎn)的介數(shù)平均值隨著k的變化關(guān)系。

節(jié)點(diǎn)介數(shù)分布Pv（B）定義為網(wǎng)絡(luò)中節(jié)點(diǎn)介數(shù)為B的節(jié)點(diǎn)數(shù)占網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的比例。

邊介數(shù)分布Pe（B）定義為網(wǎng)絡(luò)中邊介數(shù)為B的邊數(shù)占網(wǎng)絡(luò)總邊數(shù)的比例。

研究表明，節(jié)點(diǎn)的最大介數(shù)與網(wǎng)絡(luò)的同步能力密切相關(guān)：節(jié)點(diǎn)的最大介數(shù)越大，網(wǎng)絡(luò)的同步能力越弱。30復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.3介數(shù)和核度3.核度

一個圖的k－核是指反復(fù)去掉度值小于k的節(jié)點(diǎn)及其連線后，所剩余的子圖，該子圖的節(jié)點(diǎn)數(shù)就是該核的大小。

若一個節(jié)點(diǎn)屬于k－核，而不屬于（k＋1）－核，則此節(jié)點(diǎn)的核度為k。

節(jié)點(diǎn)核度的最大值叫做網(wǎng)絡(luò)的核度。

節(jié)點(diǎn)的核度可以說明節(jié)點(diǎn)在核中的深度，核度的最大值自然就對應(yīng)著網(wǎng)絡(luò)結(jié)構(gòu)中最中心的位置。k－核解析可用來描述度分布所不能描述的網(wǎng)絡(luò)特征，揭示源于系統(tǒng)特殊結(jié)構(gòu)的結(jié)構(gòu)和層次性質(zhì)。31復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.3介數(shù)和核度【例2.2】計(jì)算下面網(wǎng)絡(luò)的一些特性：（1）度分布及平均度；（2）聯(lián)合度分布[并驗(yàn)證

的正確性]；（3）各節(jié)點(diǎn)的最近鄰平均度值knn,i；（4）該網(wǎng)絡(luò)是否是同配網(wǎng)絡(luò)；（5）該網(wǎng)絡(luò)是否是正相關(guān)網(wǎng)絡(luò)；（6）分別求各節(jié)點(diǎn)和各連接邊的介數(shù)；（7）求該網(wǎng)絡(luò)的2－核，3－核及各自核度大小，并計(jì)算該網(wǎng)絡(luò)的核度。32復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.3介數(shù)和核度解：（1）該網(wǎng)絡(luò)的度分布如下表所示。因此或（2）根據(jù)

容易得到聯(lián)合度分布如下表所示。

由此可以驗(yàn)證

的正確性，例如當(dāng)k＝1時，該式左邊P（1）=1／6，而右邊為33復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.3介數(shù)和核度（3）利用

得v1～v6的最近鄰平均度值knn,i分別為：7／3、8／3、8／3、5／2、3、5／2。（4）利用

得度為1、2、3的節(jié)點(diǎn)的最近鄰平均度值的平均值knn（k）分別為：3、5／2、23／9。由于隨著k的增加knn（k）下降，所以該網(wǎng)絡(luò)是異配網(wǎng)絡(luò)。（5）Pearson相關(guān)系數(shù)因?yàn)閞＜0，說明該網(wǎng)絡(luò)為負(fù)相關(guān)。（6）由圖可知各節(jié)點(diǎn)之間的最短路徑分別為：v1e2v2；v1e3v3；v1e2v2e5v4；v1e1v5；v1e3v3e7v6；v2e4v3；v2e5v4；v2e2v1e1v5；v2e4v3e7v6；v2e5v4e6v6；v3e4v2e5v4；v3e7v6e6v4；v3e3v1e1v5；v3e7v6；v4e5v2e2v1e1v5；v4e6v6；v5e1v1e3v3e7v6。34復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.3介數(shù)和核度由此可得v1～v6各節(jié)點(diǎn)的介數(shù)Bi為：4、2.5、2.5、0.5、0、0.5。同理可得e1～e7各邊的介數(shù)為：4、3、3、1、3、1、3。（7）該網(wǎng)絡(luò)的2－核，3－核如下圖所示，它們核的大小分別為5和3。節(jié)點(diǎn)v1～v6的核度分別為3、3、3、2、1、2，所以網(wǎng)絡(luò)的核度為3。35復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.4中心性1.度中心性

度中心性分為節(jié)點(diǎn)度中心性和網(wǎng)絡(luò)度中心性。前者指的是節(jié)點(diǎn)在其與之直接相連的鄰居節(jié)點(diǎn)當(dāng)中的中心程度，而后者則側(cè)重節(jié)點(diǎn)在整個網(wǎng)絡(luò)的中心程度，表征的是整個網(wǎng)絡(luò)的集中或集權(quán)程度，即整個網(wǎng)絡(luò)圍繞一個節(jié)點(diǎn)或一組節(jié)點(diǎn)來組織運(yùn)行的程度。

節(jié)點(diǎn)vi的度中心性CD（vi）定義為

在所有含N節(jié)點(diǎn)的網(wǎng)絡(luò)中，假設(shè)網(wǎng)絡(luò)Goptimal使得下式達(dá)到最大值式中，ui為網(wǎng)絡(luò)Goptimal的各個節(jié)點(diǎn)，umax表示網(wǎng)絡(luò)Goptimal中擁有最大度中心性的節(jié)點(diǎn)。36復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.4中心性

對于含N節(jié)點(diǎn)的某網(wǎng)絡(luò)G，令vmax表示其擁有最大度中心性的節(jié)點(diǎn)，則網(wǎng)絡(luò)G的度中心性CD定義為

當(dāng)圖Goptimal為星型網(wǎng)絡(luò)時，H值達(dá)到最大，即

因此，網(wǎng)絡(luò)G的度中心性CD可簡化為37復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.4中心性2.介數(shù)中心性介數(shù)中心性分為節(jié)點(diǎn)介數(shù)中心性和網(wǎng)絡(luò)介數(shù)中心性。

節(jié)點(diǎn)vi的介數(shù)中心性CB（vi）定義為與度中心性類似，可得H＝N－1（也是星型網(wǎng)絡(luò)，中心節(jié)點(diǎn)的介數(shù)中心性為1，其它節(jié)點(diǎn)的介數(shù)中心性為0）。因此，網(wǎng)絡(luò)G的介數(shù)中心性CB可簡化為38復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.4中心性3.接近度中心性對于連通圖來說，節(jié)點(diǎn)vi的接近度中心性CC（vi）定義為與度中心性類似，可得H＝［（N－1）（N－2）／（2N－3）］（也是星型網(wǎng)絡(luò)）。因此，連通網(wǎng)絡(luò)G的接近度中心性CC可簡化為對于非連通圖來說，上述定義需要做一定的修正，一個比較好的做法是分別計(jì)算各個連通分支的中心性，然后根據(jù)各連通分支的階數(shù)進(jìn)行加權(quán)。39復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.4中心性4.特征向量中心性Ax＝λx

通常，上式的各個特征向量對應(yīng)不同的特征值λ。在這里，一個額外的要求是特征向量的每個分量必須是正數(shù)。根據(jù)Perron–Frobenius定理，只有最大的特征值對應(yīng)的特征向量才是中心性測度所需要的。求這個特征向量可采用冪迭代算法。在最后得到的特征向量中，第i個分量xi就是節(jié)點(diǎn)vi的特征向量中心性CE（vi）。40復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.5網(wǎng)絡(luò)密度

網(wǎng)絡(luò)密度指的是一個網(wǎng)絡(luò)中各節(jié)點(diǎn)之間聯(lián)絡(luò)的緊密程度。網(wǎng)絡(luò)G的網(wǎng)絡(luò)密度d（G）定義為式中，M為網(wǎng)絡(luò)中實(shí)際擁有的連接數(shù)，N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。

網(wǎng)絡(luò)密度的取值范圍為［0，1］，當(dāng)網(wǎng)絡(luò)內(nèi)部完全連通時，網(wǎng)絡(luò)密度為1，而實(shí)際網(wǎng)絡(luò)的密度通常遠(yuǎn)小于1，實(shí)際網(wǎng)絡(luò)中能夠發(fā)現(xiàn)的最大密度值是0.5。

不同規(guī)模網(wǎng)絡(luò)的密度無法進(jìn)行比較。為了解決這一問題，JohnScott提出了“絕對密度”公式式中，D表示網(wǎng)絡(luò)直徑，R表示半徑，S表示根據(jù)直徑算出的圓周長。41復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.6連通集團(tuán)（子圖）及其規(guī)模分布1.連通、連通集團(tuán)（子圖）和連通分支（最大連通子圖）

連通集團(tuán)（子圖）就是指網(wǎng)絡(luò)G中的一個子圖，在這個子圖內(nèi)，任意兩個節(jié)點(diǎn)之間都至少存在一條簡單路徑。

對于非連通圖G來說，肯定可以將其分解為兩個或兩個以上的連通分支。所謂連通分支就是最大連通子圖，即該連通子圖加入任何其它節(jié)點(diǎn)都將影響該子圖的連通性。圖G中的每個節(jié)點(diǎn)只能屬于一個連通分支，邊也一樣。顯然，連通圖的連通分支數(shù)為1，而非連通圖的連通分支數(shù)大于1。

把網(wǎng)絡(luò)的各連通分支中階數(shù)最大的一個稱為最大連通分支。42復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.6連通集團(tuán)（子圖）及其規(guī)模分布2.連通度

連通圖G的連通程度通常叫做連通度。連通度有兩種，一種是點(diǎn)連通度，一種是邊連通度。通常一個圖的連通度越好，它所代表的網(wǎng)絡(luò)越穩(wěn)定。點(diǎn)連通度定義為式中，V是圖G的節(jié)點(diǎn)集合，S為V的真子集，ω（G－S）表示從圖G中刪除點(diǎn)集S后得到的子圖G－S的連通分支數(shù)。這里G－S是指刪除S中每一個節(jié)點(diǎn)以及圖G中與之關(guān)聯(lián)的所有邊。由此可見，點(diǎn)連通度就是使G不連通或成為平凡圖所必須刪除的最少節(jié)點(diǎn)個數(shù)。對于不連通圖或平凡圖，定義к（G）＝0；若G為N階完全圖，к（G）＝N－1。43復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.6連通集團(tuán)（子圖）及其規(guī)模分布

邊連通度定義為式中，E是圖G的邊集合，T為E的真子集，ω（G－T）表示從圖G中刪除邊集T后得到的子圖G－T的連通分支數(shù)。這里G－T是指刪除T中每一條邊，而G中所有節(jié)點(diǎn)全部保留下來。由此可見，邊連通度就是使G不連通所必須刪除的最少邊數(shù)。對于不連通圖或平凡圖，定義λ（G）＝0；若G為N階完全圖，λ（G）＝N－1。

可以證明，同一個圖的點(diǎn)連通度和邊連通度滿足к（G）≤λ（G）。44復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.3.6連通集團(tuán)（子圖）及其規(guī)模分布3.連通集團(tuán)的規(guī)模分布

連通集團(tuán)的規(guī)模分布反映了網(wǎng)絡(luò)G中的各種規(guī)模的連通分支的數(shù)目分布情況。實(shí)證研究表明，對于大量的無標(biāo)度網(wǎng)絡(luò)，連通集團(tuán)的規(guī)模也存在冪律分布。例如，科學(xué)家合作網(wǎng)的連通子圖規(guī)模分布。返回目錄45復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4有向網(wǎng)絡(luò)的靜態(tài)特征2.4.1入度和出度及其分布2.4.2度－度相關(guān)性2.4.3平均距離和效率2.4.4入集團(tuán)和出集團(tuán)的集聚程度2.4.5介數(shù)和雙向比2.4.6中心性46復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.1入度和出度及其分布1.入度與出度

由于與有向網(wǎng)絡(luò)某個節(jié)點(diǎn)相關(guān)聯(lián)的弧有指向節(jié)點(diǎn)的，也有背向節(jié)點(diǎn)向外的，因此除了可以統(tǒng)計(jì)與某個節(jié)點(diǎn)相關(guān)聯(lián)的弧數(shù)，也就是度之外，有必要分開統(tǒng)計(jì)兩個方向的弧數(shù)，分別稱為節(jié)點(diǎn)的入度和出度。

節(jié)點(diǎn)vi的入度、出度和有向圖的鄰接矩陣以及度的關(guān)系為47復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.1入度和出度及其分布

同平均度一樣，也可以求平均入度＜kin＞和平均出度＜kout＞為2.入度分布和出度分布

入度分布和出度分布分別記為Pin（k）和Pout（k），分別表示網(wǎng)絡(luò)中任意取出一個節(jié)點(diǎn)，其入度值和出度值剛好為k的概率。

入（出）度分布與平均入（出）度之間具有如下關(guān)系式48復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.1入度和出度及其分布3.累積入度分布和累積出度分布

累積入（出）度分布與入（出）度分布的關(guān)系為

容易證明入（出）度冪律分布對應(yīng)的累積分布也是冪律分布，入（出）度指數(shù)分布對應(yīng)的累積分布也是同指數(shù)的指數(shù)分布。4.聯(lián)合度分布聯(lián)合度分布有兩種定義方式，第一種定義方式是基于弧的方式，第二種定義方式是基于節(jié)點(diǎn)的方式。49復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.1入度和出度及其分布基于弧的方式：從網(wǎng)絡(luò)中隨機(jī)選擇一條弧，該弧由入度和出度分別為（jin，jout）的節(jié)點(diǎn)連向入度和出度分別為（kin，kout）的節(jié)點(diǎn)的概率，即式中，M（jin，jout；kin，kout）為由入度和出度分別為jin和jout的節(jié)點(diǎn)連向入度和出度分別為kin和kout的節(jié)點(diǎn)的弧數(shù)，M為網(wǎng)絡(luò)總弧數(shù)。注意，聯(lián)合概率Pe（jin，jout；kin，kout）不是對稱的，即Pe（jin，jout；kin，kout）≠Pe（kin，kout；jin，jout）。

若對上式按照（kin，kout）求和，就得到隨機(jī)選取一條弧，該弧起點(diǎn)的度為（jin，jout）的概率50復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.1入度和出度及其分布

若對上式按照（jin，jout）求和，就得到隨機(jī)選取一條弧，該弧終點(diǎn)的度為（kin，kout）的概率基于節(jié)點(diǎn)的方式：從網(wǎng)絡(luò)中隨機(jī)選擇一個節(jié)點(diǎn)，其入度值和出度值分別為kin和kout的概率，即式中，N（kin，kout）為入度值和出度值分別為kin和kout的節(jié)點(diǎn)數(shù)，N為網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)。Pv（kin，kout）和Pf（kin，kout）、Pt（kin，kout）具有如下關(guān)系式51復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.2度－度相關(guān)性

度－度相關(guān)性也有兩種定義方式，即基于節(jié)點(diǎn)的方式和基于弧的方式。1.基于節(jié)點(diǎn)的入度－出度相關(guān)性

可以定義節(jié)點(diǎn)的入度為kin的情況下其出度為kout的條件概率為

然后，可以定義基于節(jié)點(diǎn)的入度－出度相關(guān)性為

更簡便的定義為

如果kvv（kin）～kin曲線的斜率小于0，則kin和kout負(fù)相關(guān)；斜率大于0，則kin和kout正相關(guān)；等于0，則kin和kout不相關(guān)。52復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.2度－度相關(guān)性2.基于弧的度－度相關(guān)性

任意選取一條弧，在弧的兩端存在兩個度值，起點(diǎn)的入度和出度，終點(diǎn)的入度和出度，所以存在四種相關(guān)性，分別是起點(diǎn)入度～終點(diǎn)入度，起點(diǎn)出度～終點(diǎn)入度，終點(diǎn)入度～起點(diǎn)出度以及終點(diǎn)出度～起點(diǎn)出度,分別記做kin-in（kin）～kin，kout-in（kin）～kin，kin-out（kout）～kout，kout-out（kout）～kout。這四種相關(guān)性可分別定義如下53復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.3平均距離和效率

由于有向網(wǎng)絡(luò)里的弧是帶有方向的，所以從節(jié)點(diǎn)vi到vj之間的距離dij和從節(jié)點(diǎn)vj到vi之間的距離dji是不同的。距離dij定義為從節(jié)點(diǎn)vi出發(fā)沿著同一方向到達(dá)節(jié)點(diǎn)vj所要經(jīng)歷的弧的最少數(shù)目，而它的倒數(shù)1／dij稱為從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的效率，記為εij。

有向連通簡單網(wǎng)絡(luò)的平均距離L定義為所有節(jié)點(diǎn)對之間距離的平均值，定義為

因?yàn)樾士梢杂脕砻枋龇沁B通網(wǎng)絡(luò)，所以可以定義有向網(wǎng)絡(luò)的效率LC為54復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.4入集團(tuán)和出集團(tuán)的集聚程度

對于某個節(jié)點(diǎn)vi來說，所有以該節(jié)點(diǎn)為終點(diǎn)的弧的起始節(jié)點(diǎn)及它們之間的連弧構(gòu)成一個小集團(tuán)，稱之為入集團(tuán)；而所有以該節(jié)點(diǎn)為起點(diǎn)的弧的終止節(jié)點(diǎn)及它們之間的連弧構(gòu)成一個小集團(tuán)，稱之為出集團(tuán)。

由于節(jié)點(diǎn)vi的入度為kiin，則連向該節(jié)點(diǎn)的kiin個起始節(jié)點(diǎn)間可能存在的最大弧數(shù)為kiin（kiin－1），而實(shí)際存在的弧數(shù)為Miin，由此定義為節(jié)點(diǎn)vi的入集聚系數(shù)，然后將該集聚系數(shù)對整個網(wǎng)絡(luò)作平均，即可得網(wǎng)絡(luò)的入集團(tuán)的集聚系數(shù)。55復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.4入集團(tuán)和出集團(tuán)的集聚程度

同理，定義為節(jié)點(diǎn)vi的出集聚系數(shù)，然后將該集聚系數(shù)對整個網(wǎng)絡(luò)作平均，即可得網(wǎng)絡(luò)的出集團(tuán)的集聚系數(shù)。56復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.4入集團(tuán)和出集團(tuán)的集聚程度【例2.3】針對下圖所示網(wǎng)絡(luò)分別計(jì)算：（1）寫出該網(wǎng)絡(luò)的鄰接矩陣、入度分布及出度分布；（2）分別求出該網(wǎng)絡(luò)的Pf（kin，kout）、Pt（kin，kout）和Pv（kin，kout）；（3）整個網(wǎng)絡(luò)的入集團(tuán)和出集團(tuán)的集聚系數(shù)。57復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.4入集團(tuán)和出集團(tuán)的集聚程度解：（1）該網(wǎng)絡(luò)的鄰接矩陣為

入度分布如下表所示

出度分布如下表所示（2）聯(lián)合概率分布Pe（jin，jout；kin，kout）如下表所示58復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.4入集團(tuán)和出集團(tuán)的集聚程度

由上表可得Pf（jin，jout），如下表所示

Pt（kin，kout）如下表所示

Pv（kin，kout）如下表所示59復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.4入集團(tuán)和出集團(tuán)的集聚程度（3）以節(jié)點(diǎn)v5為例，其對應(yīng)的入集團(tuán)如下圖所示，由此可計(jì)算出節(jié)點(diǎn)v5的入集團(tuán)集聚系數(shù)同理可計(jì)算出每個節(jié)點(diǎn)的入集團(tuán)的集聚系數(shù)為：0、0、0、1／2、1／6、0。而每個節(jié)點(diǎn)的出集團(tuán)的集聚系數(shù)為：1／2、0、0、0、0、1／3。因此，可得網(wǎng)絡(luò)的入集團(tuán)和出集團(tuán)集聚系數(shù)分別為1／9和5／36。60復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.5介數(shù)和雙向比1.介數(shù)

節(jié)點(diǎn)的介數(shù)Bi定義為式中，Njl表示從節(jié)點(diǎn)vj到vl的最短路徑條數(shù)，Njl（i）表示從節(jié)點(diǎn)vj到vl的最短路徑經(jīng)過節(jié)點(diǎn)vi的條數(shù)。

邊的介數(shù)Bij定義為式中，Nlm表示從節(jié)點(diǎn)vl到vm的最短路徑條數(shù)，Nlm（eij）表示從節(jié)點(diǎn)vl到vm的最短路徑經(jīng)過邊eij（方向相同）的條數(shù)。61復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.5介數(shù)和雙向比2.雙向比

雙向比，即兩兩節(jié)點(diǎn)間雙向邊的總數(shù)占網(wǎng)絡(luò)所有邊的比例。

假設(shè)有向圖中含有MB條雙向邊，則雙向比就是：RB＝MB／M。

例如下圖所示的有向圖，其雙向比為0.5。62復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.6中心性1.入度中心性和出度中心性

節(jié)點(diǎn)vi的入度中心性CD_in（vi）定義為

令vmax表示網(wǎng)絡(luò)G中擁有最大入度中心性的節(jié)點(diǎn)，則網(wǎng)絡(luò)G的入度中心性定義為

節(jié)點(diǎn)vi的出度中心性CD_out（vi）定義為

令vmax表示網(wǎng)絡(luò)G中擁有最大出度中心性的節(jié)點(diǎn)，則網(wǎng)絡(luò)G的出度中心性定義為63復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.4.6中心性2.介數(shù)中心性

節(jié)點(diǎn)vi的介數(shù)中心性CB（vi）定義為

令vmax表示網(wǎng)絡(luò)G中擁有最高介數(shù)中心性的節(jié)點(diǎn)，則網(wǎng)絡(luò)G的介數(shù)中心性CB定義為返回目錄64復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5加權(quán)網(wǎng)絡(luò)的靜態(tài)特征2.5.1點(diǎn)權(quán)、單位權(quán)和權(quán)重分布差異性2.5.2權(quán)－度相關(guān)性和權(quán)－權(quán)相關(guān)性2.5.3距離分布和平均距離2.5.4加權(quán)集聚系數(shù)2.5.5介數(shù)分布和漏斗效應(yīng)2.5.6有向加權(quán)網(wǎng)絡(luò)的最短路徑問題65復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.1點(diǎn)權(quán)、單位權(quán)和權(quán)重分布差異性1.點(diǎn)權(quán)

節(jié)點(diǎn)vi的點(diǎn)權(quán)Si定義為式中，Ni表示節(jié)點(diǎn)vi的鄰點(diǎn)集合，wij表示連接節(jié)點(diǎn)vi和節(jié)點(diǎn)vj的邊的權(quán)重。

對于無向加權(quán)網(wǎng)絡(luò)，點(diǎn)權(quán)Si還可以用鄰接矩陣元素表示為式中，aij為鄰接矩陣元素（若節(jié)點(diǎn)vi與vj無連接則aij＝0，若有連接則aij＝1）。

對于有向加權(quán)網(wǎng)絡(luò)，可定義入權(quán)和出權(quán)。66復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.1點(diǎn)權(quán)、單位權(quán)和權(quán)重分布差異性

入權(quán)Siin為以節(jié)點(diǎn)vi為終點(diǎn)的所有弧的邊權(quán)之和，而出權(quán)Siout為以節(jié)點(diǎn)vi為起點(diǎn)的所有弧的邊權(quán)之和，即而點(diǎn)權(quán)滿足2.單位權(quán)

單位權(quán)表示節(jié)點(diǎn)連接的平均權(quán)重，它定義為對于有向加權(quán)網(wǎng)絡(luò)，也可以分別定義單位入權(quán)和單位出權(quán)如下67復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.1點(diǎn)權(quán)、單位權(quán)和權(quán)重分布差異性3.權(quán)重分布的差異性

節(jié)點(diǎn)vi的權(quán)重分布差異性Yi表示與節(jié)點(diǎn)vi相連的邊權(quán)分布的離散程度，定義為

對于無向加權(quán)網(wǎng)絡(luò)，可以用鄰接矩陣表示為

差異性與度有如下關(guān)系：如果與節(jié)點(diǎn)vi關(guān)聯(lián)的邊的權(quán)重值差別不大，則Yi∝1／ki；如果權(quán)值相差較大，例如只有一條邊的權(quán)重起主要作用，則Yi≈1。

對于有向加權(quán)網(wǎng)絡(luò)，也可以分別定義入權(quán)差異性和出權(quán)差異性，即68復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.2權(quán)－度相關(guān)性和權(quán)－權(quán)相關(guān)性1.基于節(jié)點(diǎn)的權(quán)－度相關(guān)性

基于節(jié)點(diǎn)的權(quán)－度相關(guān)性指的是對于單個節(jié)點(diǎn)來說，其點(diǎn)權(quán)和其度之間的相關(guān)性。

對于無向網(wǎng)絡(luò)，就是S和k的關(guān)系，其定義為式中，N為節(jié)點(diǎn)總數(shù)，P（k）為度分布函數(shù)。當(dāng)邊權(quán)與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)無關(guān)時，通常呈現(xiàn)Svv（k）≈＜w＞·k的分布情況，其中＜w＞表示所有邊權(quán)的平均值；當(dāng)邊權(quán)與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有關(guān)時，通常呈現(xiàn)Svv（k）≈A·kβ的分布情況（要么指數(shù)β≠1，要么常數(shù)A≠<w>）。

對于有向網(wǎng)絡(luò)，除了S和k的關(guān)系，還有Sin～kin，Sin～kout，Sout～kin，Sout～kout四種相關(guān)性。69復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.2權(quán)－度相關(guān)性和權(quán)－權(quán)相關(guān)性2.基于邊的權(quán)－度相關(guān)性

基于邊的權(quán)－度相關(guān)性類似于無向網(wǎng)絡(luò)的度－度相關(guān)性，它考察的是較大權(quán)重的邊是傾向于與度值大的節(jié)點(diǎn)相連，還是傾向于與度值小的節(jié)點(diǎn)相連，還是根本沒有關(guān)系。

對于無向加權(quán)網(wǎng)絡(luò)，類似knn,i，可定義節(jié)點(diǎn)的加權(quán)平均近鄰度為式中，kj表示節(jié)點(diǎn)vj的度值，aij為鄰接矩陣元素。若所有節(jié)點(diǎn)滿足kw_nn,i＞knn,i，則表明具有較大權(quán)重的邊傾向于連接具有較大度值的點(diǎn)。若所有節(jié)點(diǎn)滿足kw_nn,i＜knn,i，則表明具有較大權(quán)重的邊傾向于連接具有較小度值的點(diǎn)。70復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.2權(quán)－度相關(guān)性和權(quán)－權(quán)相關(guān)性

可定義所有度為k的節(jié)點(diǎn)的加權(quán)平均近鄰度的平均值kw_nn（k）為若曲線斜率大于0，表示具有正相關(guān)性；若曲線斜率小于0，表示具有負(fù)相關(guān)性；若曲線斜率為0，表示不相關(guān)。

類似地，也可以研究有向網(wǎng)絡(luò)基于弧的權(quán)－度相關(guān)性。任意選取一條弧，在弧的兩端各存在兩個度值，所以存在四種相關(guān)性，加權(quán)平均近鄰入度與入度、加權(quán)平均近鄰出度與入度、加權(quán)平均近鄰入度與出度、加權(quán)平均近鄰出度與出度，分別記做kw_in-in（kin）～kin，kw_out-in（kin）～kin，kw_in-out（kout）～kout，kw_out-out（kout）～kout。71復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.2權(quán)－度相關(guān)性和權(quán)－權(quán)相關(guān)性3.權(quán)－權(quán)相關(guān)性

權(quán)相關(guān)性有兩類，一類是點(diǎn)權(quán)－點(diǎn)權(quán)相關(guān)性，一類是單位權(quán)－單位權(quán)相關(guān)性，定義方式差不多，這里以點(diǎn)權(quán)為例。

對于無向加權(quán)網(wǎng)絡(luò)，類似knn,i，可定義節(jié)點(diǎn)的加權(quán)平均近鄰權(quán)為

于是所有點(diǎn)權(quán)為S的節(jié)點(diǎn)的加權(quán)平均近鄰權(quán)的平均值Snn（S）為72復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.2權(quán)－度相關(guān)性和權(quán)－權(quán)相關(guān)性

類似地，也可以研究有向網(wǎng)絡(luò)基于弧的權(quán)－權(quán)相關(guān)性。任意選取一條弧，在弧的兩端各存在兩個權(quán)值，所以存在四種相關(guān)性，分別是起點(diǎn)入權(quán)～終點(diǎn)入權(quán)，起點(diǎn)出權(quán)～終點(diǎn)入權(quán)，終點(diǎn)入權(quán)～起點(diǎn)出權(quán)以及終點(diǎn)出權(quán)～起點(diǎn)出權(quán),分別記做Sin-in（Sin）～Sin，Sout-in（Sin）～Sin，Sin-out（Sout）～Sout，Sout-out（Sout）～Sout。73復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.3距離分布和平均距離

若邊eij的權(quán)重wij表示相異權(quán)，則其長度dij＝wij；若wij表示相似權(quán)，則其長度dij＝１／wij。假設(shè)節(jié)點(diǎn)vi和vk通過兩條權(quán)重分別為wij和wjk的邊相連，則在相異權(quán)情況下，vi和vk之間的距離dik＝wij＋wjk；而在相似權(quán)情況下，vi和vk之間的距離dik＝1／wij＋1／wjk。

加權(quán)網(wǎng)絡(luò)中的最短路徑是指在兩點(diǎn)之間所有連通的路徑中，相異權(quán)權(quán)重之和（相似權(quán)權(quán)重倒數(shù)之和）最小的一條或幾條路徑。距離分布P（d）是指距離為d的節(jié)點(diǎn)對數(shù)占總節(jié)點(diǎn)對數(shù)的比重。

無向連通簡單加權(quán)網(wǎng)絡(luò)的平均距離L定義為

有向連通簡單加權(quán)網(wǎng)絡(luò)的平均距離L定義為74復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.4加權(quán)集聚系數(shù)Barrat定義式Onnela定義式式中，表示歸一化權(quán)重。

Holme定義式75復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.4加權(quán)集聚系數(shù)【例2.4】分別計(jì)算下圖所示網(wǎng)絡(luò)（設(shè)權(quán)值為相似權(quán)）的下述特性：（1）分別求出各節(jié)點(diǎn)的點(diǎn)權(quán)、單位權(quán)、權(quán)重差異性；（2）求出網(wǎng)絡(luò)的基于節(jié)點(diǎn)的權(quán)－度相關(guān)性Svv（k）；（3）根據(jù)集聚系數(shù)的Holme定義式，求出各節(jié)點(diǎn)的加權(quán)集聚系數(shù)。解：（1）節(jié)點(diǎn)v1～v6的點(diǎn)權(quán)Si分別為：4、7、13、9、11、8；單位權(quán)Ui分別為：2、7／3、13／3、3、11／4、8／3；權(quán)重差異性Yi分別為：5／8、3／7、57／169、35／81、31／121、13／32。76復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.4加權(quán)集聚系數(shù)（2）該網(wǎng)絡(luò)的度分布如下表所示可得基于節(jié)點(diǎn)的權(quán)－度相關(guān)性Svv（k）如下表所示（3）節(jié)點(diǎn)v1～v6的加權(quán)集聚系數(shù)分別為：2／3、3／28、1／14、29／115、1／9、29／76。77復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.5介數(shù)分布和漏斗效應(yīng)

介數(shù)是用來衡量通過網(wǎng)絡(luò)中某節(jié)點(diǎn)或某條邊的最短路徑的數(shù)目。在科學(xué)家網(wǎng)絡(luò)中，介數(shù)反映了在本領(lǐng)域內(nèi)，某位科學(xué)家影響力的大小。某一節(jié)點(diǎn)的近鄰節(jié)點(diǎn)介數(shù)分布的兩極分化性質(zhì)稱為漏斗效應(yīng)，也就是說只和本領(lǐng)域的1個或2個著名成員合作就能夠很容易與合作網(wǎng)絡(luò)大部分成員建立最短路徑，而所有這些短路徑都將通過這幾個著名成員。而全部節(jié)點(diǎn)的介數(shù)分布反映的是科學(xué)家影響力的層次。邊的介數(shù)反映的是不同科學(xué)家之間的交流對學(xué)科發(fā)展影響力的不同。同時，利用邊的介數(shù)也可以對科學(xué)家做聚類分析。78復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.5.6有向加權(quán)網(wǎng)絡(luò)的最短路徑問題1.最短路徑問題

算法具體形式包括：①已知起始節(jié)點(diǎn)，求最短路徑的問題。②已知終止節(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。③已知起點(diǎn)和終點(diǎn)，求兩節(jié)點(diǎn)之間的最短路徑。④全局最短路徑問題，即求圖中所有的最短路徑。2.Dijkstra算法3.Bellman-Ford算法4.Floyd-Warshall算法返回目錄79復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.6網(wǎng)絡(luò)的其他靜態(tài)特征2.6.1網(wǎng)絡(luò)結(jié)構(gòu)熵2.6.2特征譜2.6.3度秩函數(shù)2.6.4富人俱樂部系數(shù)80復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.6.1網(wǎng)絡(luò)結(jié)構(gòu)熵

假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)vi的度為ki，則其重要度可定義為對于ki＝0的節(jié)點(diǎn)不作考慮，可以定義網(wǎng)絡(luò)結(jié)構(gòu)熵為當(dāng)網(wǎng)絡(luò)完全均勻，即Ii＝1／N時，Emax＝lnN。當(dāng)網(wǎng)絡(luò)最不均勻，即I1＝1／2，Ii＝1／［2（N－1）］（i＞1）時，Emin＝［ln4（N－1）］／2。

為了消除節(jié)點(diǎn)數(shù)目N對E的影響，可以對網(wǎng)絡(luò)結(jié)構(gòu)熵進(jìn)行歸一化，定義為網(wǎng)絡(luò)標(biāo)準(zhǔn)結(jié)構(gòu)熵。顯然

。81復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論第二章2.6.1網(wǎng)絡(luò)結(jié)構(gòu)熵

網(wǎng)絡(luò)結(jié)構(gòu)熵與度分布的關(guān)系就如同隨