1、LOGO復雜網絡基礎理論復雜網絡基礎理論網絡科學理論發展的三個時期網絡科學理論發展的三個時期u規則網絡理論階段規則網絡理論階段u隨機網絡理論階段隨機網絡理論階段u復雜網絡理論階段復雜網絡理論階段u復雜網絡的概念復雜網絡的概念u復雜網絡的特性復雜網絡的特性復雜網絡的概念和特性復雜網絡的概念和特性u1.系統和網絡系統和網絡u2.復雜性復雜性u3.復雜系統復雜系統u4.復雜網絡復雜網絡復雜網絡的概念復雜網絡的概念u復雜性復雜性u小世界特性小世界特性u無標度特性無標度特性u超家族特性超家族特性復雜網絡的特性復雜網絡的特性IP地址地址網網朋友朋友關關系系網網u概率論基礎概率論基礎u數理統計基礎數理統計基

2、礎u統計假設及檢驗統計假設及檢驗u一元線性回歸分析一元線性回歸分析數理統計基礎數理統計基礎u圖的基本概念圖的基本概念u圖的路和連通性圖的路和連通性u圖的基本運算圖的基本運算u樹與生成樹樹與生成樹u圖的矩陣表示圖的矩陣表示圖論的基本概念圖論的基本概念研究的主要內容包括：網絡的幾何性質，網絡研究的主要內容包括：網絡的幾何性質，網絡的形成機制，網絡演化的統計規律，網絡上的模的形成機制，網絡演化的統計規律，網絡上的模型性質，網絡的結構穩定性，網絡的演化動力學型性質，網絡的結構穩定性，網絡的演化動力學機制等。機制等。 主要研究工作包括以下幾個方面：主要研究工作包括以下幾個方面： 1. 1.網絡的結構和性

3、質網絡的結構和性質 2. 2.網絡宏觀性質的微觀生成機制（網絡建模）網絡宏觀性質的微觀生成機制（網絡建模） 3. 3.網絡上的動力學行為和網絡本身的動力學行網絡上的動力學行為和網絡本身的動力學行為為 4. 4.復雜網絡的應用復雜網絡的應用 5. 5.復雜網絡領域的挑戰性問題復雜網絡領域的挑戰性問題u復雜網絡的研究意義復雜網絡的研究意義 以復雜網絡的形式來研究復雜系統，可以加深人以復雜網絡的形式來研究復雜系統，可以加深人們對復雜系統結構上的深入了解。利用復雜網絡的們對復雜系統結構上的深入了解。利用復雜網絡的研究成果，也可以更加深刻的認識自然界和社會上研究成果，也可以更加深刻的認識自然界和社會上的

4、復雜性，對于我們認識自然界和社會上的各種現的復雜性，對于我們認識自然界和社會上的各種現象和事件有著重要意義。復雜網絡的研究為我們提象和事件有著重要意義。復雜網絡的研究為我們提供了一種復雜性研究的新視角、新方法，并且提供供了一種復雜性研究的新視角、新方法，并且提供了一種比較的視野，使得我們可以對各種真實網絡了一種比較的視野，使得我們可以對各種真實網絡進行比較、研究和綜合概括。因此，復雜網絡研究進行比較、研究和綜合概括。因此，復雜網絡研究無論在理論上還是實際應用中都有著重要意義。無論在理論上還是實際應用中都有著重要意義。第二章第二章 網絡拓撲結構與靜態特征網絡拓撲結構與靜態特征u 靜態特征指給定網

5、絡的微觀量的統計分布或宏觀靜態特征指給定網絡的微觀量的統計分布或宏觀統計平均值。統計平均值。u在本章中我們將對網絡的各種靜態特征做一小結在本章中我們將對網絡的各種靜態特征做一小結。由于有向網絡與加權網絡有其特有的特征量，我。由于有向網絡與加權網絡有其特有的特征量，我們將分開討論無向、有向與加權網絡。們將分開討論無向、有向與加權網絡。網絡的基本靜態幾何特征網絡的基本靜態幾何特征u平均距離平均距離u集聚系數集聚系數u度分布度分布u實際網絡的統計特征實際網絡的統計特征u平均距離平均距離（特征路徑長度）（特征路徑長度）L定義為所有節點對之間距離的定義為所有節點對之間距離的平均值，它描述了網絡中節點間的

6、平均分離程度，即網絡有多平均值，它描述了網絡中節點間的平均分離程度，即網絡有多小，計算公式小，計算公式為為u 對于無向簡單圖來說，對于無向簡單圖來說，dijdji且且dii0，則，則上上式可簡化為式可簡化為u 集聚系數集聚系數 對于無向網絡中節點對于無向網絡中節點Vi集聚系數定義為集聚系數定義為 C=2Miki（ki1） 對于有向網絡來說集聚系數為對于有向網絡來說集聚系數為 C=Miki（ki1） 根據鄰接矩陣求集聚系數公式為：根據鄰接矩陣求集聚系數公式為：度分布度分布u大多數實際網絡中的節點的度是滿足一定的概率分布的。定大多數實際網絡中的節點的度是滿足一定的概率分布的。定義義P（k）為網絡中

7、度為）為網絡中度為k的節點在整個網絡中所占的比率的節點在整個網絡中所占的比率。 規則規則網絡：網絡：由于每個節點具有相同的度，所以其度分布集中由于每個節點具有相同的度，所以其度分布集中 在一個單一尖峰上，是一種在一個單一尖峰上，是一種Delta分布分布。 完全隨機網絡：完全隨機網絡：度分布具有度分布具有Poisson分布的形式，每一條分布的形式，每一條 邊的出現概率是相等的，大多數節點的度是基本相同的邊的出現概率是相等的，大多數節點的度是基本相同的。 無標度網絡：無標度網絡：具有冪指數形式的度分布：具有冪指數形式的度分布：P（k）k 。 指數度分布網絡：指數度分布網絡： P（k）ek/，式中式

8、中0為一常數為一常數。u累積度分布累積度分布 若度分布為冪律分布，即若度分布為冪律分布，即P（k）k，則相應的累積度，則相應的累積度分布函數符合冪指數為分布函數符合冪指數為1的冪律分布的冪律分布 若度分布為指數分布，即若度分布為指數分布，即P（k）ek/，則則相應的累積相應的累積度分布函數符合同指數的指數分布度分布函數符合同指數的指數分布 實際網絡的統計特征實際網絡的統計特征無向網絡的靜態特征無向網絡的靜態特征u 聯合度分布聯合度分布 聯合度分布定義為從無向網絡中隨機選擇一條邊，該邊的聯合度分布定義為從無向網絡中隨機選擇一條邊，該邊的兩個節點的度值分別為兩個節點的度值分別為k1和和k2的概率，

9、即的概率，即u度度相關性度度相關性 度度相關性描述了網絡中度大的節點和度小的節點之間度度相關性描述了網絡中度大的節點和度小的節點之間的關系。若度大的節點傾向于和度大的節點連接，則網絡是度的關系。若度大的節點傾向于和度大的節點連接，則網絡是度度正相關的；反之，若度大的節點傾向于和度小的節點連接度正相關的；反之，若度大的節點傾向于和度小的節點連接，則網絡是度度負相關的。，則網絡是度度負相關的。 集聚系數分布和聚度相關性集聚系數分布和聚度相關性u集聚系數分布集聚系數分布 集聚系數分布函數集聚系數分布函數P（C）表示從網絡中任選一節點，其集）表示從網絡中任選一節點，其集 聚系數值為聚系數值為C的概率的

10、概率式中式中，（x）為單位沖激函數。）為單位沖激函數。u聚度相關性聚度相關性 局部集聚系數局部集聚系數C（k）定義為度為）定義為度為k的節點的鄰居之間存在的節點的鄰居之間存在的平均邊數的平均邊數Mnn（k）與這些鄰居之間存在的最大可能的）與這些鄰居之間存在的最大可能的邊數的比值，即邊數的比值，即 局部集聚系數局部集聚系數C（k）與）與k的關系刻畫了網絡的聚度相關性的關系刻畫了網絡的聚度相關性介數和核度介數和核度 介數分為節點介數和邊介數兩種，反映了節點或邊在整個介數分為節點介數和邊介數兩種，反映了節點或邊在整個網絡中的作用和影響力。網絡中的作用和影響力。 節點的介數節點的介數Bi定義為定義為

11、邊的介數邊的介數Bij定義為定義為 介度相關性可以用介度相關性可以用B（k）k表示，它定義為所有度為表示，它定義為所有度為 k的節點的介數平均值隨著的節點的介數平均值隨著k的變化關系的變化關系。 節點介數分布節點介數分布Pv（B）定義為網絡中節點介數為）定義為網絡中節點介數為B的節點數的節點數占網絡節點總數的比例占網絡節點總數的比例。 邊介數分布邊介數分布Pe（B）定義為網絡中邊介數為）定義為網絡中邊介數為B的邊數占網絡的邊數占網絡總邊數的比例。總邊數的比例。核度核度 一個圖的一個圖的k核是指反復去掉度值小于核是指反復去掉度值小于k的節點及其連線后的節點及其連線后，所剩余的子圖，該子圖的節點數

12、就是該核的大小。，所剩余的子圖，該子圖的節點數就是該核的大小。 節點核度的最大值叫做網絡的核度。節點核度的最大值叫做網絡的核度。 節點節點的的核度可以說明節點在核中的深度，核度核度可以說明節點在核中的深度，核度的的最大值自然最大值自然就對應著網絡結構中最中心的位置。就對應著網絡結構中最中心的位置。度中心性度中心性u 度中心性分為節點度中心性分為節點度度中心性中心性和和網絡網絡度度中心性。中心性。節點節點vi的度中心性的度中心性CD（vi）定義為定義為 網絡網絡G的度中心性的度中心性CD定義定義為為介數中心性介數中心性u 介數介數中心性分為節點中心性分為節點介數介數中心性中心性和和網絡網絡介數介

13、數中心性。中心性。節點節點vi的介數中心性的介數中心性CB（vi）定義為）定義為網絡網絡G的介數中心性的介數中心性CB可簡化為可簡化為網絡密度網絡密度 網絡密度指的是一個網絡中各節點之間聯絡的緊密程度。網絡密度指的是一個網絡中各節點之間聯絡的緊密程度。網網絡絡 G的網絡密度的網絡密度d（G）定義為定義為 連通集團（子圖）及其規模分布連通集團（子圖）及其規模分布 連通集團（子圖）就是指網絡連通集團（子圖）就是指網絡G中的一個子圖，在這個子圖中的一個子圖，在這個子圖內，任意兩個節點之間都至少存在一條簡單路徑。內，任意兩個節點之間都至少存在一條簡單路徑。 把網絡的各連通分支中階數最大的一個稱為最大連

14、通分支把網絡的各連通分支中階數最大的一個稱為最大連通分支 連通圖連通圖G的連通程度通常叫做連通度。的連通程度通常叫做連通度。 點連通度定義為點連通度定義為u 邊連通度定義為邊連通度定義為 連通集團的規模分布反映了網絡連通集團的規模分布反映了網絡G中的各種規模的連通分支中的各種規模的連通分支的數目分布情況。實證研究表明，對于大量的的數目分布情況。實證研究表明，對于大量的無標度無標度網絡，連網絡，連通集團的規模也存在冪律分布。通集團的規模也存在冪律分布。例如，科學家合作網的連通子例如，科學家合作網的連通子圖規模分布。圖規模分布。有向網絡的靜態特征有向網絡的靜態特征u 入度分布和出度分布入度分布和出

15、度分布 平均入度平均入度kin和平均出度和平均出度kout為為 入度分布和出度分布分別記為入度分布和出度分布分別記為Pin（k）和）和Pout（k），分別），分別表示網絡中任意取出一個節點，其入度值和出度值剛好為表示網絡中任意取出一個節點，其入度值和出度值剛好為k的的概率。概率。 入（出）度分布與平均入（出）度之間具有如下關系式入（出）度分布與平均入（出）度之間具有如下關系式u 累積入度分布和累積出度分布累積入度分布和累積出度分布u 聯合度分布聯合度分布基于弧的方式：基于弧的方式：基于節點的方式基于節點的方式平均距離和效率平均距離和效率平均距離和效率平均距離和效率 由于有向網絡里的弧是帶有方向

16、的，所以從節點由于有向網絡里的弧是帶有方向的，所以從節點vi到到vj之間之間的距離的距離dij和從節點和從節點vj到到vi之間的距離之間的距離dji是不同的。距離是不同的。距離dij定定義為從節點義為從節點vi出發沿著同一方向到達節點出發沿著同一方向到達節點vj所要經歷的弧的最所要經歷的弧的最少數目，而它的倒數少數目，而它的倒數1dij稱為從節點稱為從節點vi到節點到節點vj的效率，記的效率，記為為ij。 有向連通簡單網絡的平均距離有向連通簡單網絡的平均距離L 因為效率可以用來描述非連通網絡，所以可以定義有向網因為效率可以用來描述非連通網絡，所以可以定義有向網絡的效率絡的效率LC為為介數介數

17、節點的介數節點的介數Bi定義定義為為 式中，式中，Njl表示從節點表示從節點vj到到vl的最短路徑條數，的最短路徑條數，Njl（i）表示）表示從節點從節點vj到到vl的最短路徑的最短路徑經經過節點過節點vi的條數。的條數。 邊的介數邊的介數Bij定義為定義為 式中，式中，Nlm表示從節點表示從節點vl到到vm的最短路徑條數，的最短路徑條數，Nlm（eij）表示從節點）表示從節點vl到到vm的最短路徑經過邊的最短路徑經過邊eij（方向相同）的（方向相同）的條數。條數。介數介數加權網絡的靜態特征加權網絡的靜態特征點權點權 節點節點vi的點權的點權Si定義為定義為 對于無向加權網絡，點權對于無向加權網絡，點權Si還可以用鄰接矩陣元素表示為還可以用鄰接矩陣元素表示為 對于有向加權網絡對于有向加權網絡可以定義入權和出權可以定義入權和出權單位權單位權介數分布和漏斗效應介數分布和漏斗效應 介數是用來衡量通過網絡中某節點或某條邊的最短路徑的介數是用來衡量通過網絡中某節點或某條邊的最短路徑的數目。在科學家網絡中，