復(fù)雜網(wǎng)絡(luò)理論及應(yīng)用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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