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

1、,復雜網(wǎng)絡(luò)基礎(chǔ)理論,網(wǎng)絡(luò)科學理論發(fā)展的三個時期,規(guī)則網(wǎng)絡(luò)理論階段 隨機網(wǎng)絡(luò)理論階段 復雜網(wǎng)絡(luò)理論階段,復雜網(wǎng)絡(luò)的概念 復雜網(wǎng)絡(luò)的特性,復雜網(wǎng)絡(luò)的概念和特性,1.系統(tǒng)和網(wǎng)絡(luò) 2.復雜性 3.復雜系統(tǒng) 4.復雜網(wǎng)絡(luò),復雜網(wǎng)絡(luò)的概念,復雜性 小世界特性 無標度特性 超家族特性,復雜網(wǎng)絡(luò)的特性,IP地址網(wǎng),朋友關(guān)系網(wǎng),概率論基礎(chǔ) 數(shù)理統(tǒng)計基礎(chǔ) 統(tǒng)計假設(shè)及檢驗 一元線性回歸分析,數(shù)理統(tǒng)計基礎(chǔ),圖的基本概念 圖的路和連通性 圖的基本運算 樹與生成樹 圖的矩陣表示,圖論的基本概念,復雜網(wǎng)絡(luò)的研究內(nèi)容和意義,研究的主要內(nèi)容包括：網(wǎng)絡(luò)的幾何性質(zhì)，網(wǎng)絡(luò)的形成機制，網(wǎng)絡(luò)演化的統(tǒng)計規(guī)律，網(wǎng)絡(luò)上的模型性質(zhì)，網(wǎng)絡(luò)的結(jié)構(gòu)穩(wěn)

2、定性，網(wǎng)絡(luò)的演化動力學機制等。 主要研究工作包括以下幾個方面： 1.網(wǎng)絡(luò)的結(jié)構(gòu)和性質(zhì) 2.網(wǎng)絡(luò)宏觀性質(zhì)的微觀生成機制（網(wǎng)絡(luò)建模） 3.網(wǎng)絡(luò)上的動力學行為和網(wǎng)絡(luò)本身的動力學行為 4.復雜網(wǎng)絡(luò)的應(yīng)用 5.復雜網(wǎng)絡(luò)領(lǐng)域的挑戰(zhàn)性問題,復雜網(wǎng)絡(luò)的研究意義 以復雜網(wǎng)絡(luò)的形式來研究復雜系統(tǒng)，可以加深人們對復雜系統(tǒng)結(jié)構(gòu)上的深入了解。利用復雜網(wǎng)絡(luò)的研究成果，也可以更加深刻的認識自然界和社會上的復雜性，對于我們認識自然界和社會上的各種現(xiàn)象和事件有著重要意義。復雜網(wǎng)絡(luò)的研究為我們提供了一種復雜性研究的新視角、新方法，并且提供了一種比較的視野，使得我們可以對各種真實網(wǎng)絡(luò)進行比較、研究和綜合概括。因此，復雜網(wǎng)絡(luò)研究無論

3、在理論上還是實際應(yīng)用中都有著重要意義。,第二章 網(wǎng)絡(luò)拓撲結(jié)構(gòu)與靜態(tài)特征,靜態(tài)特征指給定網(wǎng)絡(luò)的微觀量的統(tǒng)計分布或宏觀統(tǒng)計平均值。 在本章中我們將對網(wǎng)絡(luò)的各種靜態(tài)特征做一小結(jié)。由于有向網(wǎng)絡(luò)與加權(quán)網(wǎng)絡(luò)有其特有的特征量，我們將分開討論無向、有向與加權(quán)網(wǎng)絡(luò)。,網(wǎng)絡(luò)的基本靜態(tài)幾何特征,平均距離 集聚系數(shù) 度分布 實際網(wǎng)絡(luò)的統(tǒng)計特征,平均距離（特征路徑長度）L定義為所有節(jié)點對之間距離的平均值，它描述了網(wǎng)絡(luò)中節(jié)點間的平均分離程度，即網(wǎng)絡(luò)有多小，計算公式為 對于無向簡單圖來說，dijdji且dii0，則上式可簡化為,集聚系數(shù) 對于無向網(wǎng)絡(luò)中節(jié)點Vi集聚系數(shù)定義為 C=2Miki（ki1） 對于有向網(wǎng)絡(luò)來說集聚系

4、數(shù)為 C=Miki（ki1） 根據(jù)鄰接矩陣求集聚系數(shù)公式為：,度分布,大多數(shù)實際網(wǎng)絡(luò)中的節(jié)點的度是滿足一定的概率分布的。定義P（k）為網(wǎng)絡(luò)中度為k的節(jié)點在整個網(wǎng)絡(luò)中所占的比率。 規(guī)則網(wǎng)絡(luò)：由于每個節(jié)點具有相同的度，所以其度分布集中 在一個單一尖峰上，是一種Delta分布。 完全隨機網(wǎng)絡(luò)：度分布具有Poisson分布的形式，每一條 邊的出現(xiàn)概率是相等的，大多數(shù)節(jié)點的度是基本相同的。 無標度網(wǎng)絡(luò)：具有冪指數(shù)形式的度分布：P（k）k 。 指數(shù)度分布網(wǎng)絡(luò)： P（k）ek/，式中0為一常數(shù)。,累積度分布 若度分布為冪律分布，即P（k）k，則相應(yīng)的累積度分布函數(shù)符合冪指數(shù)為1的冪律分布 若度分布為指數(shù)分布

5、，即P（k）ek/，則相應(yīng)的累積度分布函數(shù)符合同指數(shù)的指數(shù)分布,實際網(wǎng)絡(luò)的統(tǒng)計特征,無向網(wǎng)絡(luò)的靜態(tài)特征,聯(lián)合度分布 聯(lián)合度分布定義為從無向網(wǎng)絡(luò)中隨機選擇一條邊，該邊的兩個節(jié)點的度值分別為k1和k2的概率，即 度度相關(guān)性 度度相關(guān)性描述了網(wǎng)絡(luò)中度大的節(jié)點和度小的節(jié)點之間的關(guān)系。若度大的節(jié)點傾向于和度大的節(jié)點連接，則網(wǎng)絡(luò)是度度正相關(guān)的；反之，若度大的節(jié)點傾向于和度小的節(jié)點連接，則網(wǎng)絡(luò)是度度負相關(guān)的。,集聚系數(shù)分布和聚度相關(guān)性,集聚系數(shù)分布 集聚系數(shù)分布函數(shù)P（C）表示從網(wǎng)絡(luò)中任選一節(jié)點，其集 聚系數(shù)值為C的概率 式中，（x）為單位沖激函數(shù)。 聚度相關(guān)性 局部集聚系數(shù)C（k）定義為度為k的節(jié)點的鄰居

6、之間存在的平均邊數(shù)Mnn（k）與這些鄰居之間存在的最大可能的邊數(shù)的比值，即 局部集聚系數(shù)C（k）與k的關(guān)系刻畫了網(wǎng)絡(luò)的聚度相關(guān)性,介數(shù)和核度,介數(shù)分為節(jié)點介數(shù)和邊介數(shù)兩種，反映了節(jié)點或邊在整個網(wǎng)絡(luò)中的作用和影響力。 節(jié)點的介數(shù)Bi定義為 邊的介數(shù)Bij定義為,介度相關(guān)性可以用B（k）k表示，它定義為所有度為 k的節(jié)點的介數(shù)平均值隨著k的變化關(guān)系。 節(jié)點介數(shù)分布Pv（B）定義為網(wǎng)絡(luò)中節(jié)點介數(shù)為B的節(jié)點數(shù)占網(wǎng)絡(luò)節(jié)點總數(shù)的比例。 邊介數(shù)分布Pe（B）定義為網(wǎng)絡(luò)中邊介數(shù)為B的邊數(shù)占網(wǎng)絡(luò)總邊數(shù)的比例。 核度 一個圖的k核是指反復去掉度值小于k的節(jié)點及其連線后，所剩余的子圖，該子圖的節(jié)點數(shù)就是該核的大小。

7、 節(jié)點核度的最大值叫做網(wǎng)絡(luò)的核度。 節(jié)點的核度可以說明節(jié)點在核中的深度，核度的最大值自然就對應(yīng)著網(wǎng)絡(luò)結(jié)構(gòu)中最中心的位置。,度中心性,度中心性分為節(jié)點度中心性和網(wǎng)絡(luò)度中心性。 節(jié)點vi的度中心性CD（vi）定義為 網(wǎng)絡(luò)G的度中心性CD定義為,介數(shù)中心性,介數(shù)中心性分為節(jié)點介數(shù)中心性和網(wǎng)絡(luò)介數(shù)中心性。 節(jié)點vi的介數(shù)中心性CB（vi）定義為 網(wǎng)絡(luò)G的介數(shù)中心性CB可簡化為,網(wǎng)絡(luò)密度 網(wǎng)絡(luò)密度指的是一個網(wǎng)絡(luò)中各節(jié)點之間聯(lián)絡(luò)的緊密程度。網(wǎng)絡(luò) G的網(wǎng)絡(luò)密度d（G）定義為 連通集團（子圖）及其規(guī)模分布 連通集團（子圖）就是指網(wǎng)絡(luò)G中的一個子圖，在這個子圖內(nèi)，任意兩個節(jié)點之間都至少存在一條簡單路徑。 把網(wǎng)絡(luò)

8、的各連通分支中階數(shù)最大的一個稱為最大連通分支 連通圖G的連通程度通常叫做連通度。 點連通度定義為,邊連通度定義為 連通集團的規(guī)模分布反映了網(wǎng)絡(luò)G中的各種規(guī)模的連通分支的數(shù)目分布情況。實證研究表明，對于大量的無標度網(wǎng)絡(luò)，連通集團的規(guī)模也存在冪律分布。例如，科學家合作網(wǎng)的連通子圖規(guī)模分布。,有向網(wǎng)絡(luò)的靜態(tài)特征,入度分布和出度分布 平均入度kin和平均出度kout為 入度分布和出度分布分別記為Pin（k）和Pout（k），分別表示網(wǎng)絡(luò)中任意取出一個節(jié)點，其入度值和出度值剛好為k的概率。 入（出）度分布與平均入（出）度之間具有如下關(guān)系式,累積入度分布和累積出度分布 聯(lián)合度分布 基于弧的方式： 基于節(jié)點

9、的方式,平均距離和效率,平均距離和效率 由于有向網(wǎng)絡(luò)里的弧是帶有方向的，所以從節(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)絡(luò)的平均距離L 因為效率可以用來描述非連通網(wǎng)絡(luò)，所以可以定義有向網(wǎng)絡(luò)的效率LC為,介數(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ù)。,介數(shù),加權(quán)網(wǎng)絡(luò)的靜態(tài)特征,點權(quán) 節(jié)點vi的點權(quán)Si定義為 對于無向加權(quán)網(wǎng)絡(luò)，點權(quán)Si還可以用鄰接矩陣元素表示為 對于有向加權(quán)網(wǎng)絡(luò)可以定義入權(quán)和出權(quán) 單位權(quán),介數(shù)分布和漏斗效應(yīng),介數(shù)是用來衡量通過網(wǎng)絡(luò)中某節(jié)點或某條邊的最短路徑的數(shù)目。在科學家網(wǎng)絡(luò)中