復(fù)雜網(wǎng)絡(luò)概述

1、復(fù)雜網(wǎng)絡(luò)概述王 馳為什么要研究復(fù)雜網(wǎng)絡(luò)？ 關(guān)于復(fù)雜性：大量個(gè)體（更典型的是具有適應(yīng)性的主體）所組成的復(fù)雜系統(tǒng)，在沒有中心控制、非完全信息、僅僅存在局域相互作用的條件下，通過個(gè)體之間的非線性相互作用，可以在宏觀層次上涌現(xiàn)出一定的結(jié)構(gòu)和功能。為什么要研究復(fù)雜網(wǎng)絡(luò)？ 復(fù)雜系統(tǒng)不能夠用分析的方法去研究，必須考慮個(gè)體之間的關(guān)聯(lián)和作用，復(fù)雜網(wǎng)絡(luò)是構(gòu)成復(fù)雜系統(tǒng)的基本結(jié)構(gòu)，每個(gè)復(fù)雜系統(tǒng)都可以看作是單元或個(gè)體之間的相互作用網(wǎng)絡(luò)；復(fù)雜網(wǎng)絡(luò)在刻畫復(fù)雜性方面的重要性是由于結(jié)構(gòu)決定功能的，理解復(fù)雜系統(tǒng)的行為應(yīng)該從理解系統(tǒng)相互作用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)開始； 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的信息是構(gòu)建系統(tǒng)模型、研究系統(tǒng)性質(zhì)和功能的基礎(chǔ)。 為什么要

2、研究復(fù)雜網(wǎng)絡(luò)？ 復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜系統(tǒng)的一種角度和方法，它關(guān)注系統(tǒng)中個(gè)體相互關(guān)聯(lián)的作用的拓?fù)浣Y(jié)構(gòu)，是理解復(fù)雜系統(tǒng)性質(zhì)和功能的基礎(chǔ)。復(fù)雜網(wǎng)絡(luò)研究所關(guān)心的問題 如何定量刻畫復(fù)雜網(wǎng)絡(luò)？ 網(wǎng)絡(luò)結(jié)構(gòu)的描述及其性質(zhì) 網(wǎng)絡(luò)是如何發(fā)展成現(xiàn)在這種結(jié)構(gòu)的？ 網(wǎng)絡(luò)演化模型 網(wǎng)絡(luò)特定結(jié)構(gòu)的后果是什么？ 網(wǎng)絡(luò)結(jié)構(gòu)的魯棒性 網(wǎng)絡(luò)上的動(dòng)力學(xué)行為和過程復(fù)雜網(wǎng)絡(luò)的表示方法航空網(wǎng)道路交通網(wǎng)城市公共交通網(wǎng)復(fù)雜網(wǎng)絡(luò)的表示方法WWW電力網(wǎng)因特網(wǎng)復(fù)雜網(wǎng)絡(luò)的表示方法 圖提供了一種用抽象的點(diǎn)和線表示各種實(shí)際網(wǎng)絡(luò)的統(tǒng)一方法，因而成為目前研究復(fù)雜網(wǎng)絡(luò)的一種共同的語言。 例子: 國際互聯(lián)網(wǎng): 節(jié)點(diǎn)路由器 連接光纖 科學(xué)引用網(wǎng): 節(jié)點(diǎn)文章 連接文章

3、引用 社會(huì)網(wǎng)絡(luò): 節(jié)點(diǎn)個(gè)體人 連接人際關(guān)系復(fù)雜網(wǎng)絡(luò)的表示方法 按照?qǐng)D中的邊是否有向和是否有權(quán)，可以有四種類型的圖。加權(quán)有向圖加權(quán)無向圖無權(quán)無向圖無權(quán)有向圖復(fù)雜網(wǎng)絡(luò)的表示方法 圖的計(jì)算機(jī)表示1,( ,)0,( ,)ijijijv vEav vE鄰接矩陣 鄰接矩陣描述了節(jié)點(diǎn)與節(jié)點(diǎn)之間的鄰接關(guān)系，通常會(huì)用一個(gè)方陣A來表示，方陣中的元素用aij表示。復(fù)雜網(wǎng)絡(luò)的表示方法 圖的計(jì)算機(jī)表示1,( ,)0,( ,)ijijijv vEav vE一、復(fù)雜網(wǎng)絡(luò)的定義 錢學(xué)森給出了復(fù)雜網(wǎng)絡(luò)的一個(gè)較嚴(yán)格的定義：具有自組織、自相似、吸引子、小世界、無標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò)。 一、復(fù)雜網(wǎng)絡(luò)的定義 小世界特

4、性又被稱之為是六度空間理論或者是六度分割理論。小世界特性指出：社交網(wǎng)絡(luò)中的任何一個(gè)成員和任何一個(gè)陌生人之間所間隔的人不會(huì)超過六個(gè)。小世界特性：一、復(fù)雜網(wǎng)絡(luò)的定義無標(biāo)度特性：現(xiàn)實(shí)世界的網(wǎng)絡(luò)大部分都不是隨機(jī)網(wǎng)絡(luò)，少數(shù)的節(jié)點(diǎn)往往擁有大量的連接，而大部分節(jié)點(diǎn)卻很少，節(jié)點(diǎn)的度數(shù)分布符合冪率分布，而這就被稱為是網(wǎng)絡(luò)的無標(biāo)度特性。將度分布符合冪律分布的復(fù)雜網(wǎng)絡(luò)稱為無標(biāo)度網(wǎng)絡(luò)。一、復(fù)雜網(wǎng)絡(luò)的定義社團(tuán)結(jié)構(gòu)特性：人以類聚，物以群分。復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)往往也呈現(xiàn)出集群特性。例如，社會(huì)網(wǎng)絡(luò)中總是存在熟人圈或朋友圈，其中每個(gè)成員都認(rèn)識(shí)其他成員。集群程度的意義是網(wǎng)絡(luò)集團(tuán)化的程度；這是一種網(wǎng)絡(luò)的內(nèi)聚傾向。連通集團(tuán)概念反映的是

5、一個(gè)大網(wǎng)絡(luò)中各集聚的小網(wǎng)絡(luò)分布和相互聯(lián)系的狀況。例如，它可以反映這個(gè)朋友圈與另一個(gè)朋友圈的相互關(guān)系。二、復(fù)雜網(wǎng)絡(luò)中的基本概念u度度(degree)(degree)：節(jié)點(diǎn)節(jié)點(diǎn)i i的度的度 k ki i 定義為與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的定義為與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目數(shù)目, ,對(duì)于有向網(wǎng)絡(luò)分為出度和入度。對(duì)于有向網(wǎng)絡(luò)分為出度和入度。 直觀上看，一個(gè)節(jié)點(diǎn)的度越大就意味著這個(gè)節(jié)點(diǎn)在直觀上看，一個(gè)節(jié)點(diǎn)的度越大就意味著這個(gè)節(jié)點(diǎn)在 某種意義上越某種意義上越“重要重要”（“能力大能力大”）。）。 u網(wǎng)絡(luò)的平均度：網(wǎng)絡(luò)的平均度：網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度和的平均值網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度和的平均值, ,記作記作 ，并且并且

6、 =2=2M M/ /N N，M M為網(wǎng)絡(luò)中的邊數(shù)，為網(wǎng)絡(luò)中的邊數(shù)，N N為節(jié)點(diǎn)數(shù)。為節(jié)點(diǎn)數(shù)。u度分布函數(shù)度分布函數(shù)p p( (k k):):隨機(jī)選定節(jié)點(diǎn)的度恰好為隨機(jī)選定節(jié)點(diǎn)的度恰好為k k的概率的概率 二、復(fù)雜網(wǎng)絡(luò)中的基本概念u度分布函數(shù)度分布函數(shù)p p( (k k):):隨機(jī)選定節(jié)點(diǎn)的度恰好為隨機(jī)選定節(jié)點(diǎn)的度恰好為k k的概率的概率 kkPln)(ln二、復(fù)雜網(wǎng)絡(luò)中的基本概念u節(jié)點(diǎn)的聚類系數(shù)（簇系數(shù)）節(jié)點(diǎn)的聚類系數(shù)（簇系數(shù)）：在簡(jiǎn)單圖中，在簡(jiǎn)單圖中，設(shè)與節(jié)點(diǎn)設(shè)與節(jié)點(diǎn)v v相鄰的節(jié)點(diǎn)有相鄰的節(jié)點(diǎn)有kiki個(gè)，個(gè)，則則節(jié)點(diǎn)節(jié)點(diǎn)v v的聚類系數(shù)的聚類系數(shù)定義為這定義為這k ki i個(gè)個(gè)節(jié)點(diǎn)之間

7、存在邊數(shù)節(jié)點(diǎn)之間存在邊數(shù)E Ei i與總的可能邊數(shù)與總的可能邊數(shù)k ki i(k(ki i-1)/2-1)/2之比，之比，即：即：C Ci i=2E=2Ei i/ /k ki i(k(ki i-1) -1) ( (包含節(jié)點(diǎn)包含節(jié)點(diǎn)i i的三角形數(shù)目的三角形數(shù)目/ /以節(jié)以節(jié)點(diǎn)點(diǎn)i i為中心的連通三元組的數(shù)目為中心的連通三元組的數(shù)目) )u 網(wǎng)絡(luò)的聚類系數(shù)網(wǎng)絡(luò)的聚類系數(shù)C：所有節(jié)點(diǎn)所有節(jié)點(diǎn)i的聚類系數(shù)的聚類系數(shù)Ci的平均值。的平均值。（0 C 1） C=0網(wǎng)絡(luò)中所有節(jié)點(diǎn)都是孤立點(diǎn)網(wǎng)絡(luò)中所有節(jié)點(diǎn)都是孤立點(diǎn) C=1網(wǎng)絡(luò)中任意節(jié)點(diǎn)間都有邊相連網(wǎng)絡(luò)中任意節(jié)點(diǎn)間都有邊相連 網(wǎng)絡(luò)節(jié)點(diǎn)間聯(lián)系的密切程度網(wǎng)絡(luò)節(jié)點(diǎn)

8、間聯(lián)系的密切程度, 體現(xiàn)網(wǎng)絡(luò)的體現(xiàn)網(wǎng)絡(luò)的凝聚力凝聚力二、復(fù)雜網(wǎng)絡(luò)中的基本概念u節(jié)點(diǎn)節(jié)點(diǎn)的介數(shù)的介數(shù)：u 邊的介數(shù)：邊的介數(shù)：iljljjljlNiNB,所有i/)(式中，式中，Njl表示節(jié)點(diǎn)表示節(jié)點(diǎn)vj和和vl之間的最短路徑條數(shù)，之間的最短路徑條數(shù)，Njl（i）表）表示節(jié)點(diǎn)示節(jié)點(diǎn)vj和和vl之間的最短路徑經(jīng)過節(jié)點(diǎn)之間的最短路徑經(jīng)過節(jié)點(diǎn)vi的條數(shù)。的條數(shù)。 jimlmlmllmijlmijNeNB,;,所有/式中，式中，Nlm表示節(jié)點(diǎn)表示節(jié)點(diǎn)vl和和vm之間的最短路徑條數(shù)，之間的最短路徑條數(shù)，Nlm（eij）表示節(jié)點(diǎn)）表示節(jié)點(diǎn)vl和和vm之間的最短路徑經(jīng)過邊之間的最短路徑經(jīng)過邊eij的條數(shù)的條數(shù)

9、二、復(fù)雜網(wǎng)絡(luò)中的基本概念 許多大規(guī)模的實(shí)際網(wǎng)絡(luò)都具有許多大規(guī)模的實(shí)際網(wǎng)絡(luò)都具有明顯的明顯的聚類效應(yīng)聚類效應(yīng)。事實(shí)上，在很多類。事實(shí)上，在很多類型的網(wǎng)絡(luò)型的網(wǎng)絡(luò)(如社會(huì)關(guān)系網(wǎng)絡(luò)如社會(huì)關(guān)系網(wǎng)絡(luò))中，你的中，你的朋友同時(shí)也是朋友的概率會(huì)隨著網(wǎng)絡(luò)朋友同時(shí)也是朋友的概率會(huì)隨著網(wǎng)絡(luò)規(guī)模的增加而趨向于規(guī)模的增加而趨向于某個(gè)非零常數(shù)某個(gè)非零常數(shù)，即當(dāng)即當(dāng)N時(shí)，時(shí)，C=O(1)。這意味著這。這意味著這些實(shí)際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機(jī)的，些實(shí)際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機(jī)的，而是在某種程度上具有類似于社會(huì)關(guān)而是在某種程度上具有類似于社會(huì)關(guān)系網(wǎng)絡(luò)中系網(wǎng)絡(luò)中“物以類聚，人以群分物以類聚，人以群分”的的特性。特性。二、復(fù)雜網(wǎng)

10、絡(luò)中的基本概念u 最短路徑最短路徑（Shortest path）:兩個(gè)節(jié)點(diǎn)之間邊數(shù)最少兩個(gè)節(jié)點(diǎn)之間邊數(shù)最少的路徑，最短路徑的長(zhǎng)度稱為兩點(diǎn)間的的路徑，最短路徑的長(zhǎng)度稱為兩點(diǎn)間的距離，距離，用用d dij iju 平均路徑長(zhǎng)度平均路徑長(zhǎng)度（特征路徑長(zhǎng)度）（特征路徑長(zhǎng)度）L L： 所有節(jié)點(diǎn)對(duì)之間的距離的平均值。所有節(jié)點(diǎn)對(duì)之間的距離的平均值。 研究發(fā)現(xiàn)：盡管許多實(shí)際復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)巨大，研究發(fā)現(xiàn)：盡管許多實(shí)際復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)巨大，網(wǎng)絡(luò)的平均路徑長(zhǎng)度卻小的驚人。（小世界效應(yīng)）網(wǎng)絡(luò)的平均路徑長(zhǎng)度卻小的驚人。（小世界效應(yīng)）三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型n四種結(jié)構(gòu)模型規(guī)則網(wǎng)絡(luò)規(guī)則網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)小世界網(wǎng)絡(luò)小世界網(wǎng)

11、絡(luò)無標(biāo)度網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò)三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型n規(guī)則網(wǎng)絡(luò)（a）全局耦合網(wǎng)絡(luò) （b）最近鄰耦合網(wǎng)絡(luò) （c）星形耦合網(wǎng)絡(luò)三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型n規(guī)則網(wǎng)絡(luò)拓?fù)湫再|(zhì)最近鄰耦合網(wǎng)絡(luò)目網(wǎng)路中連通三元組的數(shù)）（網(wǎng)絡(luò)中三角形的數(shù)目3ncC)1(4）2（3KKk2k/m2）2/（12/1mncNNLN一般情況下，聚集系數(shù)較大，平均最短路徑較長(zhǎng)。三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型n隨機(jī)網(wǎng)絡(luò)（1）初始化：給定N個(gè)節(jié)點(diǎn)以及連邊概率p（2）隨機(jī)連邊： 選擇一對(duì)沒有邊相連的不同的節(jié)點(diǎn)。 生成一個(gè)隨機(jī)數(shù)r 如果rp,那么在這對(duì)節(jié)點(diǎn)之間添加一條邊；否則就不添加邊。 重復(fù)步驟，直到所有的節(jié)點(diǎn)對(duì)都被選擇過一次。三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型n隨機(jī)網(wǎng)絡(luò)

12、拓?fù)湫再|(zhì)度分布：kNkppkNkP1)1(1)(MNMppMNMP2)1(2)(邊數(shù)分布：聚類系數(shù)：C=p=/N-1平均路徑長(zhǎng)度：ERERDLlnN/ln三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型n小世界網(wǎng)絡(luò)三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型n小世界網(wǎng)絡(luò)C(p) : 平均聚集系數(shù)平均聚集系數(shù) L(p) : 平均最短路徑平均最短路徑PageRank算法通過人工進(jìn)行網(wǎng)頁分類并整理出高質(zhì)量的網(wǎng)站計(jì)算用戶查詢關(guān)鍵詞與網(wǎng)頁內(nèi)容的相關(guān)程度來返回搜索結(jié)果 算法來源PageRank算法谷歌的兩位創(chuàng)始人，當(dāng)時(shí)還是美國斯坦福大學(xué)研究生的佩奇和布林開始了對(duì)網(wǎng)頁排序問題的研究，借鑒了學(xué)術(shù)界評(píng)判學(xué)術(shù)論文重要性的通用方法，那就是看論文的引用次數(shù)。由此想

13、到網(wǎng)頁的重要性也可以根據(jù)這種方法來評(píng)價(jià)。PageRank算法如果一個(gè)網(wǎng)頁被很多其他網(wǎng)頁鏈接到的話說明這個(gè)網(wǎng)頁比較重要，也就是PageRank值會(huì)相對(duì)較高。如果一個(gè)PageRank值很高的網(wǎng)頁鏈接到一個(gè)其他的網(wǎng)頁，那么被鏈接到的網(wǎng)頁的PageRank值會(huì)相應(yīng)地因此而提高。PageRank算法 算法原理PageRank算法總的來說就是預(yù)先給每個(gè)網(wǎng)頁一個(gè)PR值，PR值物理意義上為一個(gè)網(wǎng)頁被訪問概率，所以一般是1/N，其中N為網(wǎng)頁總數(shù)。另外，所有網(wǎng)頁的PR值的總和為1。預(yù)先給定PR值后，通過不斷迭代，直至達(dá)到平穩(wěn)分布為止。PR(A)=PR(B)/2+PR(C)NskPRaskPRjNjji1)1()1

14、(）（1iPageRank算法 算法證明002/13/12/1103/12/1003/1002/10ajinnAPP1TeeNA1ajinnPlim是否存在？如果極限存在，那么它是否與P0的選取無關(guān)？PageRank算法 算法證明nnAPP1狀態(tài)轉(zhuǎn)移矩陣A需要滿足： 1.A為隨機(jī)矩陣。 2.A是不可約的。 3.A是非周期的。作戰(zhàn)體系節(jié)點(diǎn)重要性分析機(jī)械化戰(zhàn)爭(zhēng)時(shí)代，在通信手段和指揮控制手段受限的情況下，作戰(zhàn)體系，形成了一種樹狀結(jié)構(gòu)。隨著指揮信息系統(tǒng)的功能越來越強(qiáng)，作戰(zhàn)體系任何兩個(gè)節(jié)點(diǎn)之間均可以根據(jù)需要建立聯(lián)系，逐步形成網(wǎng)絡(luò)化結(jié)構(gòu)。作戰(zhàn)體系節(jié)點(diǎn)重要性分析 作戰(zhàn)體系結(jié)構(gòu)的網(wǎng)絡(luò)描述依據(jù)復(fù)雜網(wǎng)絡(luò)理論，可以

15、定義作戰(zhàn)體系由節(jié)點(diǎn)集合 V 和 邊 集 合 E 組 成 的 圖 G = (V , E) 。其中， V = v1,v2 ,vn，代表組成作戰(zhàn)體系的指揮控制節(jié)點(diǎn)、預(yù)警偵察節(jié)點(diǎn)（包括戰(zhàn)場(chǎng)態(tài)勢(shì)信息源節(jié)點(diǎn)和目標(biāo)信息源節(jié)點(diǎn)）、攻防交戰(zhàn)節(jié)點(diǎn)等； E =e1,e2 ,em，代表節(jié)點(diǎn)之間信息傳遞關(guān)系。 作戰(zhàn)體系節(jié)點(diǎn)重要性分析 作戰(zhàn)體系節(jié)點(diǎn)重要性的度量指標(biāo)u度度指標(biāo)：指標(biāo)：描述在靜態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)所產(chǎn)生的直接影響力。描述在靜態(tài)網(wǎng)絡(luò)中節(jié)點(diǎn)所產(chǎn)生的直接影響力。 u介介數(shù)指標(biāo)：數(shù)指標(biāo)：描述網(wǎng)絡(luò)中最短路徑描述網(wǎng)絡(luò)中最短路徑通過某節(jié)點(diǎn)通過某節(jié)點(diǎn)的的數(shù)量數(shù)量， 反反映的映的是該節(jié)點(diǎn)是該節(jié)點(diǎn)在網(wǎng)絡(luò)中的樞紐性。在網(wǎng)絡(luò)中的樞紐性。u緊密度指標(biāo)：緊密度指標(biāo)：緊密緊密度指標(biāo)用于刻畫網(wǎng)絡(luò)中的節(jié)點(diǎn)通過網(wǎng)絡(luò)度指標(biāo)用于刻畫網(wǎng)絡(luò)中的節(jié)點(diǎn)通過網(wǎng)絡(luò)到達(dá)網(wǎng)絡(luò)到達(dá)網(wǎng)絡(luò)中其它節(jié)點(diǎn)的難易中其它節(jié)點(diǎn)的難易程度。程度。11c)(NjijdiC作戰(zhàn)體系節(jié)點(diǎn)重要性分析 作戰(zhàn)體系受損程度的度量指標(biāo)u最大連通分支：最大連通分支：最大連通分支的大小指的是相對(duì)大小，即最大連通分支的大小指的是相對(duì)大小，即最大最大連通分支連通分支的節(jié)點(diǎn)數(shù)與所有節(jié)點(diǎn)數(shù)的的節(jié)點(diǎn)數(shù)