復雜網絡概述

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

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

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

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

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

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

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

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

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

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

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

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

13、到網頁的重要性也可以根據這種方法來評價。PageRank算法如果一個網頁被很多其他網頁鏈接到的話說明這個網頁比較重要，也就是PageRank值會相對較高。如果一個PageRank值很高的網頁鏈接到一個其他的網頁，那么被鏈接到的網頁的PageRank值會相應地因此而提高。PageRank算法 算法原理PageRank算法總的來說就是預先給每個網頁一個PR值，PR值物理意義上為一個網頁被訪問概率，所以一般是1/N，其中N為網頁總數。另外，所有網頁的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é)點之間均可以根據需要建立聯(lián)系，逐步形成網絡化結構。作戰(zhàn)體系節(jié)點重要性分析 作戰(zhàn)體系結構的網絡描述依據復雜網絡理論，可以

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)網絡中節(jié)點所產生的直接影響力。描述在靜態(tài)網絡中節(jié)點所產生的直接影響力。 u介介數指標：數指標：描述網絡中最短路徑描述網絡中最短路徑通過某節(jié)點通過某節(jié)點的的數量數量， 反反映的映的是該節(jié)點是該節(jié)點在網絡中的樞紐性。在網絡中的樞紐性。u緊密度指標：緊密度指標：緊密緊密度指標用于刻畫網絡中的節(jié)點通過網絡度指標用于刻畫網絡中的節(jié)點通過網絡到達網絡到達網絡中其它節(jié)點的難易中其它節(jié)點的難易程度。程度。11c)(NjijdiC作戰(zhàn)體系節(jié)點重要性分析 作戰(zhàn)體系受損程度的度量指標u最大連通分支：最大連通分支：最大連通分支的大小指的是相對大小，即最大連通分支的大小指的是相對大小，即最大最大連通分支連通分支的節(jié)點數與所有節(jié)點數的的節(jié)點數