度相關(guān)性測度

1、15:141度相關(guān)性測度度相關(guān)性測度 20102010年年1010月月1717日日上海大學(xué)上海大學(xué) 史定華史定華寧波大學(xué)寧波大學(xué) 周暉杰周暉杰 2 內(nèi)容提要內(nèi)容提要F度相關(guān)的度相關(guān)的重要性重要性F聯(lián)合度分布聯(lián)合度分布F鄰結(jié)點平均度鄰結(jié)點平均度F度相關(guān)系數(shù)度相關(guān)系數(shù)F無標(biāo)度程度無標(biāo)度程度F測度測度合理性合理性討論討論F度混合系數(shù)度混合系數(shù)3 度相關(guān)的重要性度相關(guān)的重要性F 網(wǎng)絡(luò)度分布太宏觀網(wǎng)絡(luò)度分布太宏觀網(wǎng)絡(luò)網(wǎng)絡(luò)度分布度分布完全相同，其拓?fù)浣Y(jié)構(gòu)可完全不同完全相同，其拓?fù)浣Y(jié)構(gòu)可完全不同1. Holme-Kim(BA)模型模型1可調(diào)群集系數(shù)可調(diào)群集系數(shù)2. 復(fù)制模型和自然數(shù)整除復(fù)制模型和自然數(shù)整除2

2、隨機(jī)與確定隨機(jī)與確定3. 保度重連會改變特征值保度重連會改變特征值Chen局部與整體局部與整體F 網(wǎng)絡(luò)拓?fù)浣M織結(jié)構(gòu)網(wǎng)絡(luò)拓?fù)浣M織結(jié)構(gòu) 指標(biāo)：指標(biāo)：群集系數(shù)，平均路徑，介數(shù)等群集系數(shù)，平均路徑，介數(shù)等 度相關(guān)性度相關(guān)性動力學(xué)最關(guān)心鄰域結(jié)構(gòu)動力學(xué)最關(guān)心鄰域結(jié)構(gòu)4 兩個模型度分布比較兩個模型度分布比較F自然數(shù)整除網(wǎng)絡(luò)自然數(shù)整除網(wǎng)絡(luò)確定確定F度分布完全一致度分布完全一致隨機(jī)隨機(jī)11kkNpp21( )(1)(2)inP kkkk5 聯(lián)合度分布聯(lián)合度分布FDorogovtsev等人定義等人定義3 其中其中 是網(wǎng)絡(luò)是網(wǎng)絡(luò)的鄰接矩陣的鄰接矩陣 FKrapivsky等人的結(jié)果等人的結(jié)果4cited by 335

3、對對m = 1時時BA模型模型發(fā)現(xiàn)非平凡相關(guān)模型模型發(fā)現(xiàn)非平凡相關(guān)上式最重要的意義是上式最重要的意義是 ,2,11( , ;)ijNk kijkli jP k l NaN( , )P k l4( 1)12( 1)( , )(1)()(1)(2)(1)()(1)(2)llPk lk kk l k lk lk k lk l k lk l ( , )( ) ( )P k lP k P l ijAa6 (三種指數(shù)三種指數(shù)網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)及其結(jié)構(gòu)及其)聯(lián)合度分布聯(lián)合度分布7 鄰結(jié)點平均度鄰結(jié)點平均度5cited by 593FPastor-Satorras等人等人引入引入條件概率條件概率 表示度相關(guān)性表示度

4、相關(guān)性F實際計算實際計算采用鄰結(jié)點采用鄰結(jié)點平均度，若平均度，若冪律冪律 ，則由，則由指數(shù)指數(shù)確定確定(| )cP kk8 度相關(guān)系數(shù)度相關(guān)系數(shù)6,7cited by 1082FNewman采用相關(guān)系數(shù)來刻畫采用相關(guān)系數(shù)來刻畫 V是網(wǎng)絡(luò)是網(wǎng)絡(luò)g的結(jié)點集，的結(jié)點集，E是連線集，結(jié)點度序列是連線集，結(jié)點度序列 。度相關(guān)系數(shù)。度相關(guān)系數(shù)(需方差存在需方差存在)為為F或等價地或等價地212( , )( , )2221122( , )( , )()( )()()ijiji jEi jEijiji jEi jEddEddEr gddEddE2212( , )2321122( )ijii jEi Viii

5、Vi Vd ddEr gddE12,NDd dd9 某些網(wǎng)絡(luò)度相關(guān)系數(shù)某些網(wǎng)絡(luò)度相關(guān)系數(shù)610 無標(biāo)度程度無標(biāo)度程度8cited by 236FLi等人則引入無標(biāo)度程度等人則引入無標(biāo)度程度 表示由于結(jié)點之間連線不同而具有相表示由于結(jié)點之間連線不同而具有相同度序列的網(wǎng)絡(luò)同度序列的網(wǎng)絡(luò)(簡單無向連通圖簡單無向連通圖)全體。全體。 計算計算 ，令，令 表示表示 中中的的 最大值，定義測度最大值，定義測度 (無限之比能穩(wěn)定嗎無限之比能穩(wěn)定嗎) 來來衡量網(wǎng)絡(luò)衡量網(wǎng)絡(luò) 的無標(biāo)度程度。大稱為的無標(biāo)度程度。大稱為“無標(biāo)無標(biāo)度的度的” ；小為；小為“標(biāo)度豐富的標(biāo)度豐富的” 。F相關(guān)系數(shù)第一項精確等于相關(guān)系數(shù)第一

6、項精確等于 ( )G D( , )( )iji jEs gd dmaxs( )G D( )s gmax( )( )S gs gsg( )s gE11 F 由于冪律遞減特性由于冪律遞減特性 F 聯(lián)合分布無法判斷聯(lián)合分布無法判斷F 不像前面指數(shù)網(wǎng)絡(luò)不像前面指數(shù)網(wǎng)絡(luò)F 泊松逼近正態(tài)泊松逼近正態(tài)F 容易看出差異容易看出差異 m=1時聯(lián)合度分布時聯(lián)合度分布 冪律再現(xiàn)難以應(yīng)對冪律再現(xiàn)難以應(yīng)對討論討論: BA模型的聯(lián)合度分布模型的聯(lián)合度分布4(1)12(1)( , )(1)()(1)(2)(1)()(1)(2)llP k lk kkl klklk klkl klkl 12 討論討論: BA模型的度相關(guān)系數(shù)模

7、型的度相關(guān)系數(shù) F模擬模擬網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模 從從100到到 10000個個結(jié)點結(jié)點平均度從平均度從 2到到14的的網(wǎng)絡(luò)網(wǎng)絡(luò)模擬結(jié)果模擬結(jié)果 13 討論討論: BA模型的無標(biāo)度程度模型的無標(biāo)度程度 F模擬模擬網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模 從從100到到 10000個個結(jié)點結(jié)點平均度從平均度從 2到到14的的網(wǎng)絡(luò)網(wǎng)絡(luò)模擬結(jié)果模擬結(jié)果 14 測度合理性討論測度合理性討論總結(jié)總結(jié)F聯(lián)合度分布是度相關(guān)性的最完整的刻畫聯(lián)合度分布是度相關(guān)性的最完整的刻畫 只對只對BA模型有結(jié)果；模型有結(jié)果；沒有沒有簡單簡單數(shù)量指標(biāo)數(shù)量指標(biāo)。 F鄰結(jié)點平均度考慮了鄰結(jié)點度鄰結(jié)點平均度考慮了鄰結(jié)點度 若若不是冪律不是冪律無法判斷；無法判斷

8、；BA模型模型不相關(guān)！不相關(guān)！F相關(guān)系數(shù)由于規(guī)范化具有誤導(dǎo)性相關(guān)系數(shù)由于規(guī)范化具有誤導(dǎo)性 數(shù)值大小數(shù)值大小依賴網(wǎng)絡(luò)規(guī)模依賴網(wǎng)絡(luò)規(guī)模； BA模型模型不相關(guān)！不相關(guān)！F無標(biāo)度程度穩(wěn)定性沒有涉及無標(biāo)度程度穩(wěn)定性沒有涉及 數(shù)值大小也數(shù)值大小也依賴網(wǎng)絡(luò)規(guī)模依賴網(wǎng)絡(luò)規(guī)模； BA模型模型不大不大15 度相關(guān)性度相關(guān)性有有更佳測度嗎更佳測度嗎? ?F網(wǎng)絡(luò)拓?fù)錅y度網(wǎng)絡(luò)拓?fù)錅y度Barabsi說從說從度分布到度相關(guān)性度分布到度相關(guān)性, 不同拓?fù)涮卣鞯膹V不同拓?fù)涮卣鞯膹V泛存在性被作為研究不同現(xiàn)象以及做出預(yù)測的跳板。泛存在性被作為研究不同現(xiàn)象以及做出預(yù)測的跳板。F測度的合理性測度的合理性 網(wǎng)絡(luò)度分布網(wǎng)絡(luò)度分布度指數(shù)獨立

9、于網(wǎng)絡(luò)規(guī)模，這是優(yōu)點也是缺點度指數(shù)獨立于網(wǎng)絡(luò)規(guī)模，這是優(yōu)點也是缺點 度相關(guān)性度相關(guān)性現(xiàn)有指標(biāo)依賴于網(wǎng)絡(luò)規(guī)模，聯(lián)合度分布對冪律不敏感現(xiàn)有指標(biāo)依賴于網(wǎng)絡(luò)規(guī)模，聯(lián)合度分布對冪律不敏感 更佳測度更佳測度不不依賴于網(wǎng)絡(luò)規(guī)模，能給出局部結(jié)構(gòu)的度相關(guān)性依賴于網(wǎng)絡(luò)規(guī)模，能給出局部結(jié)構(gòu)的度相關(guān)性16 度混合系數(shù)度混合系數(shù)一種新的測度一種新的測度F 原則原則同配得正異配為負(fù)同配得正異配為負(fù)F 算法算法先算結(jié)點后算網(wǎng)絡(luò)先算結(jié)點后算網(wǎng)絡(luò)1. 將網(wǎng)絡(luò)結(jié)點按平均度分為兩個集合將網(wǎng)絡(luò)結(jié)點按平均度分為兩個集合2. 大于平均度結(jié)點與大于平均度結(jié)點連線為正大于平均度結(jié)點與大于平均度結(jié)點連線為正1否則為負(fù)否則為負(fù)13. 小于平均度

10、結(jié)點與小于平均度結(jié)點連線為正小于平均度結(jié)點與小于平均度結(jié)點連線為正1否則為負(fù)否則為負(fù)14. 計算每個計算每個結(jié)點結(jié)點的的混合系數(shù)混合系數(shù)求和除以度數(shù)求和除以度數(shù)5. 將結(jié)點混合系數(shù)平均得將結(jié)點混合系數(shù)平均得網(wǎng)絡(luò)混合系數(shù)網(wǎng)絡(luò)混合系數(shù)17 BA模型的度混合系數(shù)模型的度混合系數(shù) F模擬模擬網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模 從從100到到 10000個個結(jié)點結(jié)點平均度從平均度從 2到到14的的網(wǎng)絡(luò)網(wǎng)絡(luò)模擬結(jié)果模擬結(jié)果 18 度混合系數(shù)度混合系數(shù)與連線數(shù)關(guān)系與連線數(shù)關(guān)系 10000個結(jié)點，平均度從個結(jié)點，平均度從2到到60的結(jié)果的結(jié)果 與網(wǎng)絡(luò)與網(wǎng)絡(luò)規(guī)模無關(guān)規(guī)模無關(guān)與平均度與平均度成反比成反比尚缺少尚缺少度的信息度的信息

11、問題并問題并沒有解決沒有解決19 隨機(jī)失效與蓄意攻擊隨機(jī)失效與蓄意攻擊9F特性特性穩(wěn)健穩(wěn)健脆弱脆弱 F解釋解釋結(jié)點異質(zhì)結(jié)點異質(zhì)F質(zhì)疑質(zhì)疑網(wǎng)絡(luò)核心網(wǎng)絡(luò)核心 縱坐標(biāo)網(wǎng)絡(luò)直徑縱坐標(biāo)網(wǎng)絡(luò)直徑d；橫坐標(biāo)除去結(jié)點比例；橫坐標(biāo)除去結(jié)點比例f 20 度混合系數(shù)的應(yīng)用度混合系數(shù)的應(yīng)用F罩門罩門 hub結(jié)點結(jié)點 誤解：誤解：無標(biāo)度網(wǎng)結(jié)點異質(zhì)，所以穩(wěn)健而又脆弱無標(biāo)度網(wǎng)結(jié)點異質(zhì)，所以穩(wěn)健而又脆弱F質(zhì)疑質(zhì)疑 標(biāo)度程度標(biāo)度程度 例子：例子：雖然因特網(wǎng)無標(biāo)度，但是顯示標(biāo)度豐富雖然因特網(wǎng)無標(biāo)度，但是顯示標(biāo)度豐富F探討探討 網(wǎng)絡(luò)核心網(wǎng)絡(luò)核心 結(jié)構(gòu)：結(jié)構(gòu)：攻擊結(jié)點，即網(wǎng)絡(luò)核心形成的攻擊結(jié)點，即網(wǎng)絡(luò)核心形成的局部局部結(jié)構(gòu)，結(jié)構(gòu)，與

12、全局結(jié)構(gòu)不同。度混合系數(shù)可以測量，例如與全局結(jié)構(gòu)不同。度混合系數(shù)可以測量，例如0.1%， IBA(核心核心)=0.080; IAS(核心核心)= ？ 猜測猜測 0。盡管盡管BA模型和因特網(wǎng)都標(biāo)度豐富，但核心結(jié)構(gòu)不同模型和因特網(wǎng)都標(biāo)度豐富，但核心結(jié)構(gòu)不同!21 進(jìn)一步研究的問題進(jìn)一步研究的問題F度相關(guān)測度度相關(guān)測度(更多信息更多信息) 考慮結(jié)點度的相關(guān)測度考慮結(jié)點度的相關(guān)測度-M(g) MBA(網(wǎng)絡(luò)網(wǎng)絡(luò))= 0.312 MBA(核心核心)= 0.718動力學(xué)相關(guān)性測度動力學(xué)相關(guān)性測度-利用核函數(shù)利用核函數(shù)F相關(guān)性過程相關(guān)性過程(相互作用相互作用) 考慮考慮 結(jié)點度的演化結(jié)點度的演化 結(jié)點的動力學(xué)

13、結(jié)點的動力學(xué)兩者相互影響是我們需要攻克的難題。兩者相互影響是我們需要攻克的難題。 ()()( )()()iiijj Oijj OdkdkM idkdk( ), ( )iiK tX t( )iK t( )iX t22 總結(jié)：總結(jié)：網(wǎng)絡(luò)拓?fù)鋵W(xué)和動力學(xué)網(wǎng)絡(luò)拓?fù)鋵W(xué)和動力學(xué)10F網(wǎng)絡(luò)拓?fù)鋵W(xué)網(wǎng)絡(luò)拓?fù)鋵W(xué)(隨機(jī)過程隨機(jī)過程) Barabsi說說除非探討其網(wǎng)絡(luò)拓?fù)?，否則沒有辦法去除非探討其網(wǎng)絡(luò)拓?fù)?，否則沒有辦法去理解復(fù)雜系統(tǒng)。理解復(fù)雜系統(tǒng)。如何探討？有限維分布族。如何探討？有限維分布族。 網(wǎng)絡(luò)度分布研究已有較好的基礎(chǔ)，特別是動力學(xué)指網(wǎng)絡(luò)度分布研究已有較好的基礎(chǔ)，特別是動力學(xué)指數(shù)抓住了要害。數(shù)抓住了要害。一維分布

14、，冪律，度指數(shù)。一維分布，冪律，度指數(shù)。 但是度相關(guān)性等其它測度還需要理清。但是度相關(guān)性等其它測度還需要理清。二維分布？二維分布？F網(wǎng)絡(luò)動力學(xué)網(wǎng)絡(luò)動力學(xué)(動力系統(tǒng)動力系統(tǒng)) Barabsi說說共性是存在的，我們只是還沒有發(fā)現(xiàn)能共性是存在的，我們只是還沒有發(fā)現(xiàn)能夠解釋它們普遍性的框架。夠解釋它們普遍性的框架。這是我們需要攻克的下一個前沿問題。這是我們需要攻克的下一個前沿問題。 23 參考文獻(xiàn)參考文獻(xiàn)1 P. Holme, B. J. Kim, Phys. Rev. E 65, 026107(2002) 2史定華，周暉杰，史定華，周暉杰，復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，20103 S. N. Dorogovtsev, J. F. F. Mendes, Oxford University Press, 2003 4 P. L. Krapivsky, S. Redner, Phys. Rev. E 63, 066123(2001) 5 R. Pastor-Satorras et al., Phys. Rev. Lett. 87, 258701(2001) 6 M. E. J. Newman, Phys. R