復雜網(wǎng)絡概述

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

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

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

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

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

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

7、存在邊數(shù)節(jié)點之間存在邊數(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é)點包含節(jié)點i i的三角形數(shù)目的三角形數(shù)目/ /以節(jié)以節(jié)點點i i為中心的連通三元組的數(shù)目為中心的連通三元組的數(shù)目) )u 網(wǎng)絡的聚類系數(shù)網(wǎng)絡的聚類系數(shù)C：所有節(jié)點所有節(jié)點i的聚類系數(shù)的聚類系數(shù)Ci的平均值。的平均值。（0 C 1） C=0網(wǎng)絡中所有節(jié)點都是孤立點網(wǎng)絡中所有節(jié)點都是孤立點 C=1網(wǎng)絡中任意節(jié)點間都有邊相連網(wǎng)絡中任意節(jié)點間都有邊相連 網(wǎng)絡節(jié)點間聯(lián)系的密切程度網(wǎng)絡節(jié)點

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

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

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

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

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

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

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

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