復雜網(wǎng)絡理論及應用

1、復雜網(wǎng)絡理論及應用Complex Network Theory and Its Application項林英 副教授廈門大學自動化系: xiangly Tel:復雜網(wǎng)絡模型1736年歐拉解決哥尼斯堡七橋問題創(chuàng)立圖論1959年Erdös和Rényi引入隨機圖論規(guī)則網(wǎng)絡隨機網(wǎng)絡2三種規(guī)則網(wǎng)絡和ER隨機網(wǎng)絡的基本拓撲性質(zhì)比較網(wǎng)絡邊數(shù)平均路徑長度聚類系數(shù)度分布全耦合網(wǎng)絡N(N-1)/211delta最近鄰網(wǎng)絡NK/2(N +2)/(2K)3(K-2)/4(K-1)delta星形網(wǎng)絡N-12-2/N0ER隨機網(wǎng)絡pN(N-1)/2lnN/ln<k>p=<k>/

2、(N-1)Poission最近鄰網(wǎng)絡與ER隨機網(wǎng)絡的拓撲性質(zhì)比較4復雜網(wǎng)絡模型網(wǎng)絡邊數(shù)平均路徑長度聚類系數(shù)度分布最近鄰網(wǎng)絡NK/2(N +2)/(2K)3(K-2)/4(K-1)deltaER隨機網(wǎng)絡pN(N-1)/2 lnN/ln<k>p = <k>/(N-1)Poission最近鄰網(wǎng)絡與ER隨機網(wǎng)絡的拓撲性質(zhì)比較5復雜網(wǎng)絡模型網(wǎng)絡邊數(shù)平均路徑長度聚類系數(shù)度分布最近鄰網(wǎng)絡NK/2(N +2)/(2K)3(K-2)/4(K-1)deltaER隨機網(wǎng)絡pN(N-1)/2 lnN/ln<k>p = <k>/(N-1)Poission最近鄰網(wǎng)絡與ER隨

3、機網(wǎng)絡的拓撲性質(zhì)比較最近鄰網(wǎng)絡: 較大的平均路徑長度ER隨機網(wǎng)絡: 較小的平均路徑長度6復雜網(wǎng)絡模型網(wǎng)絡邊數(shù)平均路徑長度聚類系數(shù)度分布最近鄰網(wǎng)絡NK/2(N +2)/(2K)3(K-2)/4(K-1)deltaER隨機網(wǎng)絡pN(N-1)/2 lnN/ln<k>p = <k>/(N-1)Poission最近鄰網(wǎng)絡與ER隨機網(wǎng)絡的拓撲性質(zhì)比較最近鄰網(wǎng)絡: 較大的平均路徑長度ER隨機網(wǎng)絡: 較小的平均路徑長度7復雜網(wǎng)絡模型網(wǎng)絡邊數(shù)平均路徑長度聚類系數(shù)度分布最近鄰網(wǎng)絡NK/2(N +2)/(2K)3(K-2)/4(K-1)deltaER隨機網(wǎng)絡pN(N-1)/2 lnN/ln&

4、lt;k>p = <k>/(N-1)Poission最近鄰網(wǎng)絡與ER隨機網(wǎng)絡的拓撲性質(zhì)比較最近鄰網(wǎng)絡: 較大的平均路徑長度和較大的聚類系數(shù)ER隨機網(wǎng)絡: 較小的平均路徑長度和較小的聚類系數(shù)8復雜網(wǎng)絡模型網(wǎng)絡邊數(shù)平均路徑長度聚類系數(shù)度分布最近鄰網(wǎng)絡NK/2(N +2)/(2K)3(K-2)/4(K-1)deltaER隨機網(wǎng)絡pN(N-1)/2 lnN/ln<k>p = <k>/(N-1)Poission最近鄰網(wǎng)絡與ER隨機網(wǎng)絡的拓撲性質(zhì)比較最近鄰網(wǎng)絡: 較大的平均路徑長度和較大的聚類系數(shù)ER隨機網(wǎng)絡: 較小的平均路徑長度和較小的聚類系數(shù)實際網(wǎng)絡:小世界特

5、性9復雜網(wǎng)絡模型網(wǎng)絡邊數(shù)平均路徑長度聚類系數(shù)度分布最近鄰網(wǎng)絡NK/2(N +2)/(2K)3(K-2)/4(K-1)deltaER隨機網(wǎng)絡pN(N-1)/2 lnN/ln<k>p = <k>/(N-1)Poission最近鄰網(wǎng)絡與ER隨機網(wǎng)絡的拓撲性質(zhì)比較最近鄰網(wǎng)絡: 較大的平均路徑長度和較大的聚類系數(shù)ER隨機網(wǎng)絡: 較小的平均路徑長度和較小的聚類系數(shù)實際網(wǎng)絡: 較小的平均路徑長度和較大的聚類系數(shù)小世界特性10復雜網(wǎng)絡模型網(wǎng)絡邊數(shù)平均路徑長度聚類系數(shù)度分布最近鄰網(wǎng)絡NK/2(N +2)/(2K)3(K-2)/4(K-1)deltaER隨機網(wǎng)絡pN(N-1)/2 lnN/

6、ln<k>p = <k>/(N-1)Poission大L大C小L大C小L小C完全規(guī)則網(wǎng)絡和完全隨機網(wǎng)絡之間可能的11復雜網(wǎng)絡模型第四章復雜網(wǎng)絡模型4.1 規(guī)則網(wǎng)絡模型4.2 隨機網(wǎng)絡模型4.3 小世界網(wǎng)絡模型4.4 無標度網(wǎng)絡模型12復雜網(wǎng)絡模型小世界現(xiàn)象在一千多年前，我國唐朝詩人王勃在送杜少府之任蜀州中的名句“海內(nèi)存知己, 天涯若比鄰”, 已經(jīng)涵蓋了小世界現(xiàn)象從人文和哲學上最先認識到了小世界現(xiàn)象1967年美國學家Milgram提出的“六度分離”假設作了一定的和實驗證實1314小世界網(wǎng)絡networks.Nature,CollectiveDynamicsofsmall-

7、world1998, 393: 440-442.D. J. WattsS. H. StrogatzCornell University復雜網(wǎng)絡模型15小世界網(wǎng)絡networks.Nature,CollectiveDynamicsofsmall-world1998, 393: 440-442. 提出了一種融合規(guī)則網(wǎng)絡和隨機網(wǎng)絡優(yōu)點的小世界網(wǎng)絡模型 (小L大C)1618WS小世界模型的構造算法隨機化重連: 以概率P 對圓環(huán)中的每一條邊進行重新連接。這個過程不能自身連接和重復連接。首先開始于規(guī)則圖形: 初始有數(shù)目固定的 N 個節(jié)點，每個節(jié)點有K 個最近鄰，圓環(huán)。一個規(guī)則的一維19復雜網(wǎng)絡模型P =0

8、0<P <<1P =1復雜網(wǎng)絡模型20P =00<P <<1P =1(a) 規(guī)則網(wǎng)絡21復雜網(wǎng)絡模型P =00<P <<1P =1(a) 規(guī)則網(wǎng)絡(c) 隨機網(wǎng)絡22復雜網(wǎng)絡模型P =00<P <<1P =1(a) 規(guī)則網(wǎng)絡(b) 小世界網(wǎng)絡(c) 隨機網(wǎng)絡23復雜網(wǎng)絡模型P =00<P <<1P =1(a) 規(guī)則網(wǎng)絡(b) 小世界網(wǎng)絡(c) 隨機網(wǎng)絡24WS小世界模型的基本性質(zhì)平均路徑長度: LWS (N/K)f(NKp)聚類系數(shù): CWS 3(K-2)/4(K-1)(1-p)3度分布: Poissio

9、n分布25復雜網(wǎng)絡模型分析 平均路徑長度: LWS (N/K)f(NKp) 聚類系數(shù): CWS 3(K-2)/4(K-1)(1-p)3給定參數(shù) N=1000, K=1026分析 平均路徑長度: LWS (N/K)f(NKp) 聚類系數(shù): CWS 3(K-2)/4(K-1)(1-p)3較小的平均路徑長度L較大的聚類系數(shù)C小世界網(wǎng)絡！給定參數(shù) N=1000, K=1027實際驗證小世界網(wǎng)絡的三個實例Small-Word NetworksSome examples29復雜網(wǎng)絡模型科學家合作網(wǎng)節(jié)點：科學家邊：合作L=49文章或合作研究項目. (2001)M.E.J.(2001) and A.L. Ba

10、rabási復雜網(wǎng)絡模型30電路圖節(jié)點：元器件邊：電子線路L=4R. F. Cancho, Phys. Rev., 64, 046119 (2001)31復雜網(wǎng)絡模型ER隨機圖模型與WS小世界模型的共同點32復雜網(wǎng)絡模型ER隨機圖模型與WS小世界模型的共同點網(wǎng)絡連接度分布是泊松分布，具有同質(zhì)性，在一個平均值處達到并按指數(shù)形式進行衰減。33復雜網(wǎng)絡模型ER隨機圖模型與WS小世界模型的共同點網(wǎng)絡連接度分布是泊松分布，具有同質(zhì)性，在一個平均值處達到并按指數(shù)形式進行衰減。網(wǎng)絡中節(jié)點數(shù)目是固定不變的，是一種靜態(tài)的網(wǎng)絡模型。34復雜網(wǎng)絡模型ER隨機圖模型與WS小世界模型的共同點網(wǎng)絡連接度分布是泊

11、松分布，具有同質(zhì)性，在一個平均值處達到并按指數(shù)形式進行衰減。網(wǎng)絡中節(jié)點數(shù)目是固定不變的，是一種靜態(tài)的網(wǎng)絡模型。 實際網(wǎng)絡？35復雜網(wǎng)絡模型第四章復雜網(wǎng)絡模型4.1 規(guī)則網(wǎng)絡模型4.2 隨機網(wǎng)絡模型4.3 小世界網(wǎng)絡模型4.4 無標度網(wǎng)絡模型36復雜網(wǎng)絡模型無標度網(wǎng)絡networks. Science,Emergence of 286: 509-512.scalinginrandom1999,A.-L. BarabásiR. AlbertNorte Dame University37復雜網(wǎng)絡模型39BA無標度網(wǎng)絡模型的構造算法40復雜網(wǎng)絡模型BA無標度網(wǎng)絡模型的構造算法增長41復雜網(wǎng)絡

12、模型BA無標度網(wǎng)絡模型的構造算法增長優(yōu)先連接42復雜網(wǎng)絡模型BA無標度網(wǎng)絡模型的構造算法增長: 從一個具有m0個節(jié)點的連通網(wǎng)絡開始，在每一個時間步，加入一個新的節(jié)點，并與m(mm0)個網(wǎng)絡中已經(jīng)存在的節(jié)點建立連接；43復雜網(wǎng)絡模型BA無標度網(wǎng)絡模型的構造算法增長: 從一個具有m0個節(jié)點的連通網(wǎng)絡開始，在每一個時間步，加入一個新的節(jié)點，并與m(mm0)個網(wǎng)絡中已經(jīng)存在的節(jié)點建立連接；優(yōu)先連接: 一個新節(jié)點與一個已經(jīng)存在的節(jié)點 i 相連接的概率正比于節(jié)點 i 的度ki :44復雜網(wǎng)絡模型BA無標度網(wǎng)絡的演化參數(shù) m0=M0=3, m=2復雜網(wǎng)絡模型BA無標度網(wǎng)絡的演化參數(shù) m0=M0=3, m=2

13、糾正：t=0! (P273)復雜網(wǎng)絡模型BA無標度網(wǎng)絡模型的基本性質(zhì)平均路徑長度: LBAlnN/lnlnN聚類系數(shù): CBA (lnt)2/t-r度分布: 冪律分布 P(k)k47復雜網(wǎng)絡模型BA無標度網(wǎng)絡模型的基本性質(zhì)度分布: 冪律分布 P(k)k-r網(wǎng)絡連接度分布是冪律分布，具有異質(zhì)性，即少數(shù)節(jié)點有很高的度，但大部分的節(jié)點的度卻很小。網(wǎng)絡中節(jié)點和邊是連續(xù)增長的，是一種動態(tài)的網(wǎng)絡模型。48典型網(wǎng)絡的度分布比較P(k)1<k>k網(wǎng)絡度分布全耦合/最近鄰耦合網(wǎng)絡deltaER隨機網(wǎng)絡PoissionWS小世界網(wǎng)絡PoissionBA無標度網(wǎng)絡冪律Scale-Free Network

14、sSome examples50復雜網(wǎng)絡模型5152WS小世界網(wǎng)絡研究和BA無標度網(wǎng)絡研究之間的共性特征53復雜網(wǎng)絡模型WS小世界網(wǎng)絡研究和BA無標度網(wǎng)絡研究之間的共性特征師生合作完成并在最頂級期刊美國Cornell大學的博士生Watts及其導師Strogatz教授，1998年6月在Nature上；美國Notre Dame大學物理系的Barabási教授及其博士生Albert，1999年10月在Science上。54復雜網(wǎng)絡模型WS小世界網(wǎng)絡研究和BA無標度網(wǎng)絡研究之間的共性特征師生合作完成并在最頂級期刊美國Cornell大學的博士生Watts及其導師Strogatz教授，1998年

15、6月在Nature上；美國Notre Dame大學物理系的Barabási教授及其博士生Albert，1999年10月在Science上。迅速成為網(wǎng)絡科學文獻中的Hub節(jié)點據(jù)Scholar統(tǒng)計，截至2012年1月1日，WS小世界網(wǎng)絡的文章被引用14791次，BA無標度網(wǎng)絡的文章被12472次。55復雜網(wǎng)絡模型WS小世界網(wǎng)絡研究和BA無標度網(wǎng)絡研究之間的共性特征師生合作完成并在最頂級期刊美國Cornell大學的博士生Watts及其導師Strogatz教授，1998年6月在Nature上；美國Notre Dame大學物理系的Barabási教授及其博士生Albert，1999年

16、10月在Science上。迅速成為網(wǎng)絡科學文獻中的Hub節(jié)點據(jù)Scholar統(tǒng)計，截至2012年1月1日，WS小世界網(wǎng)絡的文章被引用14791次，BA無標度網(wǎng)絡的文章被12472次。建模、和實際驗證的文章結構實際網(wǎng)絡的一些特征建立模型并基于實際數(shù)據(jù)加以驗證。兩篇文章中的部分實際網(wǎng)絡的數(shù)據(jù)相同。56復雜網(wǎng)絡模型WS小世界網(wǎng)絡研究和BA無標度網(wǎng)絡研究之間的共性特征師生合作完成并在最頂級期刊美國Cornell大學的博士生Watts及其導師Strogatz教授，1998年6月在Nature上；美國Notre Dame大學物理系的Barabási教授及其博士生Albert，1999年10月在S

17、cience上。迅速成為網(wǎng)絡科學文獻中的Hub節(jié)點據(jù)Scholar統(tǒng)計，截至2012年1月1日，WS小世界網(wǎng)絡的文章被引用14791次，BA無標度網(wǎng)絡的文章被12472次。建模、和實際驗證的文章結構實際網(wǎng)絡的一些特征建立模型并基于實際數(shù)據(jù)加以驗證。兩篇文章中的部分實際網(wǎng)絡的數(shù)據(jù)相同。勇于迎接57復雜網(wǎng)絡模型無標度網(wǎng)絡的發(fā)現(xiàn)：為什么是BA而不是WS?Watts在2003年時深表后悔：的書SixDegrees中在回憶這段經(jīng)歷“當我在1999年4月份的一個周末收到Barabási索要網(wǎng)絡數(shù)據(jù)的郵件時，我還不知道他們想要干什么?！薄拔覀儧]有檢查！我們深信非正態(tài)的度分布是不相關的，因此我們從來沒有想到要看一看到底哪些網(wǎng)絡服從正態(tài)度分布，哪些網(wǎng)絡則從正態(tài)度分布。數(shù)據(jù)在我們手中幾乎有兩年的時間，而我們只需半個小時就可以做完檢查。但是，我們卻從來沒有想過去做?！?8復雜網(wǎng)絡模型復雜網(wǎng)絡模型1998年Watts和Str