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

1、整理ppt復(fù)雜網(wǎng)絡(luò)概述整理ppt為什么要研究復(fù)雜網(wǎng)絡(luò)？ 關(guān)于復(fù)雜性：大量個體（更典型的是具有適應(yīng)性的主體）所組成的復(fù)雜系統(tǒng)，在沒有中心控制、非完全信息、僅僅存在局域相互作用的條件下，通過個體之間的非線性相互作用，可以在宏觀層次上涌現(xiàn)出一定的結(jié)構(gòu)和功能。整理ppt為什么要研究復(fù)雜網(wǎng)絡(luò)？ 復(fù)雜系統(tǒng)不能夠用分析的方法去研究，必須考慮個體之間的關(guān)聯(lián)和作用，復(fù)雜網(wǎng)絡(luò)是構(gòu)成復(fù)雜系統(tǒng)的基本結(jié)構(gòu)，每個復(fù)雜系統(tǒng)都可以看作是單元或個體之間的相互作用網(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ì)

2、和功能的基礎(chǔ)。 整理ppt為什么要研究復(fù)雜網(wǎng)絡(luò)？ 復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜系統(tǒng)的一種角度和方法，它關(guān)注系統(tǒng)中個體相互關(guān)聯(lián)的作用的拓?fù)浣Y(jié)構(gòu)，是理解復(fù)雜系統(tǒng)性質(zhì)和功能的基礎(chǔ)。整理ppt復(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ò)上的動力學(xué)行為和過程整理ppt復(fù)雜網(wǎng)絡(luò)的表示方法航空網(wǎng)道路交通網(wǎng)城市公共交通網(wǎng)整理ppt復(fù)雜網(wǎng)絡(luò)的表示方法WWW電力網(wǎng)因特網(wǎng)整理ppt復(fù)雜網(wǎng)絡(luò)的表示方法 圖提供了一種用抽象的點和線表示各種實際網(wǎng)絡(luò)的統(tǒng)一方法，因而成為目前研究復(fù)雜網(wǎng)絡(luò)的一種共同的語言。 例

3、子: 國際互聯(lián)網(wǎng): 節(jié)點路由器 連接光纖 科學(xué)引用網(wǎng): 節(jié)點文章 連接文章引用 社會網(wǎng)絡(luò): 節(jié)點個體人 連接人際關(guān)系整理ppt復(fù)雜網(wǎng)絡(luò)的表示方法 按照圖中的邊是否有向和是否有權(quán)，可以有四種類型的圖。整理ppt復(fù)雜網(wǎng)絡(luò)的表示方法 圖的計算機(jī)表示1,( ,)0,( ,)ijijijv vEav vE鄰接矩陣 鄰接矩陣描述了節(jié)點與節(jié)點之間的鄰接關(guān)系，通常會用一個方陣A來表示，方陣中的元素用aij表示。整理ppt復(fù)雜網(wǎng)絡(luò)的表示方法 圖的計算機(jī)表示1,( ,)0,( ,)ijijijv vEav vE整理ppt一、復(fù)雜網(wǎng)絡(luò)的定義 錢學(xué)森給出了復(fù)雜網(wǎng)絡(luò)的一個較嚴(yán)格的定義：具有自組織、自相似、吸引子、小世界

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

5、中每個成員都認(rèn)識其他成員。集群程度的意義是網(wǎng)絡(luò)集團(tuán)化的程度；這是一種網(wǎng)絡(luò)的內(nèi)聚傾向。連通集團(tuán)概念反映的是一個大網(wǎng)絡(luò)中各集聚的小網(wǎng)絡(luò)分布和相互聯(lián)系的狀況。例如，它可以反映這個朋友圈與另一個朋友圈的相互關(guān)系。整理ppt二、復(fù)雜網(wǎng)絡(luò)中的基本概念u度度(degree)(degree)：節(jié)點節(jié)點i i的度的度 k ki i 定義為與該節(jié)點連接的其他節(jié)點的定義為與該節(jié)點連接的其他節(jié)點的數(shù)目數(shù)目, ,對于有向網(wǎng)絡(luò)分為出度和入度。對于有向網(wǎng)絡(luò)分為出度和入度。 直觀上看，一個節(jié)點的度越大就意味著這個節(jié)點在直觀上看，一個節(jié)點的度越大就意味著這個節(jié)點在 某種意義上越某種意義上越“重要重要”（“能力大能力大”）。）。

6、 u網(wǎng)絡(luò)的平均度：網(wǎng)絡(luò)的平均度：網(wǎng)絡(luò)中所有節(jié)點的度和的平均值網(wǎng)絡(luò)中所有節(jié)點的度和的平均值, ,記作記作 ，并且，并且 =2=2M M/ /N N，M M為網(wǎng)絡(luò)中的邊數(shù)，為網(wǎng)絡(luò)中的邊數(shù)，N N為節(jié)點數(shù)。為節(jié)點數(shù)。u度分布函數(shù)度分布函數(shù)p p( (k k):):隨機(jī)選定節(jié)點的度恰好為隨機(jī)選定節(jié)點的度恰好為k k的概率的概率 整理ppt二、復(fù)雜網(wǎng)絡(luò)中的基本概念u度分布函數(shù)度分布函數(shù)p p( (k k):):隨機(jī)選定節(jié)點的度恰好為隨機(jī)選定節(jié)點的度恰好為k k的概率的概率 kkPln)(ln整理ppt二、復(fù)雜網(wǎng)絡(luò)中的基本概念u節(jié)點的聚類系數(shù)（簇系數(shù)）節(jié)點的聚類系數(shù)（簇系數(shù)）：在簡單圖中，在簡單圖中，設(shè)與

7、節(jié)點設(shè)與節(jié)點v v相鄰的節(jié)點有相鄰的節(jié)點有kiki個，則個，則節(jié)點節(jié)點v v的聚類系數(shù)的聚類系數(shù)定義為這定義為這k ki i個個節(jié)點之間存在邊數(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)絡(luò)的聚類系數(shù)網(wǎng)絡(luò)的聚類系數(shù)C：所有節(jié)點所有節(jié)點i的聚類系數(shù)的聚類系數(shù)Ci的平均值。的平均值。（0 C 1） C=0網(wǎng)絡(luò)中所有節(jié)

8、點都是孤立點網(wǎng)絡(luò)中所有節(jié)點都是孤立點 C=1網(wǎng)絡(luò)中任意節(jié)點間都有邊相連網(wǎng)絡(luò)中任意節(jié)點間都有邊相連 網(wǎng)絡(luò)節(jié)點間聯(lián)系的密切程度網(wǎng)絡(luò)節(jié)點間聯(lián)系的密切程度, 體現(xiàn)網(wǎng)絡(luò)的體現(xiàn)網(wǎng)絡(luò)的凝聚力凝聚力整理ppt二、復(fù)雜網(wǎng)絡(luò)中的基本概念u節(jié)點的介數(shù)節(jié)點的介數(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之間

9、的最短路徑條數(shù)，之間的最短路徑條數(shù)，Nlm（eij）表示節(jié)點）表示節(jié)點vl和和vm之間的最短路徑經(jīng)過邊之間的最短路徑經(jīng)過邊eij的條數(shù)的條數(shù)整理ppt二、復(fù)雜網(wǎng)絡(luò)中的基本概念 許多大規(guī)模的實際網(wǎng)絡(luò)都具有許多大規(guī)模的實際網(wǎng)絡(luò)都具有明顯的明顯的聚類效應(yīng)聚類效應(yīng)。事實上，在很多類。事實上，在很多類型的網(wǎng)絡(luò)型的網(wǎng)絡(luò)(如社會關(guān)系網(wǎng)絡(luò)如社會關(guān)系網(wǎng)絡(luò))中，你的中，你的朋友同時也是朋友的概率會隨著網(wǎng)絡(luò)朋友同時也是朋友的概率會隨著網(wǎng)絡(luò)規(guī)模的增加而趨向于規(guī)模的增加而趨向于某個非零常數(shù)某個非零常數(shù)，即當(dāng)即當(dāng)N時，時，C=O(1)。這意味著這。這意味著這些實際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機(jī)的，些實際的復(fù)雜網(wǎng)絡(luò)并不是完全隨機(jī)

10、的，而是在某種程度上具有類似于社會關(guān)而是在某種程度上具有類似于社會關(guān)系網(wǎng)絡(luò)中系網(wǎng)絡(luò)中“物以類聚，人以群分物以類聚，人以群分”的的特性。特性。整理ppt二、復(fù)雜網(wǎng)絡(luò)中的基本概念u 最短路徑最短路徑（Shortest path）:兩個節(jié)點之間邊數(shù)最少兩個節(jié)點之間邊數(shù)最少的路徑，最短路徑的長度稱為兩點間的的路徑，最短路徑的長度稱為兩點間的距離，距離，用用d dij iju 平均路徑長度平均路徑長度（特征路徑長度）（特征路徑長度）L L： 所有節(jié)點對之間的距離的平均值。所有節(jié)點對之間的距離的平均值。 研究發(fā)現(xiàn)：盡管許多實際復(fù)雜網(wǎng)絡(luò)的節(jié)點數(shù)巨大，研究發(fā)現(xiàn)：盡管許多實際復(fù)雜網(wǎng)絡(luò)的節(jié)點數(shù)巨大，網(wǎng)絡(luò)的平均路徑

11、長度卻小的驚人。（小世界效應(yīng)）網(wǎng)絡(luò)的平均路徑長度卻小的驚人。（小世界效應(yīng)）整理ppt三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型整理ppt三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型（a）全局耦合網(wǎng)絡(luò) （b）最近鄰耦合網(wǎng)絡(luò) （c）星形耦合網(wǎng)絡(luò)整理ppt三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型最近鄰耦合網(wǎng)絡(luò)目網(wǎng)路中連通三元組的數(shù)）（網(wǎng)絡(luò)中三角形的數(shù)目3ncC)1(4）2（3KKk2k/m2）2/（12/1mncNNLN一般情況下，聚集系數(shù)較大，平均最短路徑較長。整理ppt三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型整理ppt三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型度分布：kNkppkNkP1)1(1)(MNMppMNMP2)1(2)(邊數(shù)分布：聚類系數(shù)：C=p=/N-1平均路徑長度：ERERDL

12、lnN/ln整理ppt三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型整理ppt三、復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)模型C(p) : 平均聚集系數(shù)平均聚集系數(shù) L(p) : 平均最短路徑平均最短路徑整理pptPageRank算法通過人工進(jìn)行網(wǎng)頁分類并整理出高質(zhì)量的網(wǎng)站計算用戶查詢關(guān)鍵詞與網(wǎng)頁內(nèi)容的相關(guān)程度來返回搜索結(jié)果 算法來源整理pptPageRank算法谷歌的兩位創(chuàng)始人，當(dāng)時還是美國斯坦福大學(xué)研究生的佩奇和布林開始了對網(wǎng)頁排序問題的研究，借鑒了學(xué)術(shù)界評判學(xué)術(shù)論文重要性的通用方法，那就是看論文的引用次數(shù)。由此想到網(wǎng)頁的重要性也可以根據(jù)這種方法來評價。整理pptPageRank算法如果一個網(wǎng)頁被很多其他網(wǎng)頁鏈接到的話說明這個網(wǎng)頁比較重要

13、，也就是PageRank值會相對較高。如果一個PageRank值很高的網(wǎng)頁鏈接到一個其他的網(wǎng)頁，那么被鏈接到的網(wǎng)頁的PageRank值會相應(yīng)地因此而提高。整理pptPageRank算法算法原理PageRank算法總的來說就是預(yù)先給每個網(wǎng)頁一個PR值，PR值物理意義上為一個網(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(）（1i整理pptPageRank算法 算法證明002/13/12/1103/12/1003/1002/1

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

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