度相關性測度

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

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

3、對對m = 1時時BA模型模型發(fā)現(xiàn)非平凡相關模型模型發(fā)現(xià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)絡網(wǎng)絡結構及其結構及其)聯(lián)合度分布聯(lián)合度分布7 鄰結點平均度鄰結點平均度5cited by 593FPastor-Satorras等人等人引入引入條件概率條件概率 表示度相關性表示度

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

5、Vi Vd ddEr gddE12,NDd dd9 某些網(wǎng)絡度相關系數(shù)某些網(wǎng)絡度相關系數(shù)610 無標度程度無標度程度8cited by 236FLi等人則引入無標度程度等人則引入無標度程度 表示由于結點之間連線不同而具有相表示由于結點之間連線不同而具有相同度序列的網(wǎng)絡同度序列的網(wǎng)絡(簡單無向連通圖簡單無向連通圖)全體。全體。 計算計算 ，令，令 表示表示 中中的的 最大值，定義測度最大值，定義測度 (無限之比能穩(wěn)定嗎無限之比能穩(wěn)定嗎) 來來衡量網(wǎng)絡衡量網(wǎng)絡 的無標度程度。大稱為的無標度程度。大稱為“無標無標度的度的” ；小為；小為“標度豐富的標度豐富的” 。F相關系數(shù)第一項精確等于相關系數(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)絡不像前面指數(shù)網(wǎng)絡F 泊松逼近正態(tài)泊松逼近正態(tài)F 容易看出差異容易看出差異 m=1時聯(lián)合度分布時聯(lián)合度分布 冪律再現(xiàn)難以應對冪律再現(xiàn)難以應對討論討論: BA模型的聯(lián)合度分布模型的聯(lián)合度分布4(1)12(1)( , )(1)()(1)(2)(1)()(1)(2)llP k lk kkl klklk klkl klkl 12 討論討論: BA模型的度相關系數(shù)模

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

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

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

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

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

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

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

14、，冪律，度指數(shù)。一維分布，冪律，度指數(shù)。 但是度相關性等其它測度還需要理清。但是度相關性等其它測度還需要理清。二維分布？二維分布？F網(wǎng)絡動力學網(wǎng)絡動力學(動力系統(tǒng)動力系統(tǒng)) Barabsi說說共性是存在的，我們只是還沒有發(fā)現(xiàn)能共性是存在的，我們只是還沒有發(fā)現(xiàn)能夠解釋它們普遍性的框架。夠解釋它們普遍性的框架。這是我們需要攻克的下一個前沿問題。這是我們需要攻克的下一個前沿問題。 23 參考文獻參考文獻1 P. Holme, B. J. Kim, Phys. Rev. E 65, 026107(2002) 2史定華，周暉杰，史定華，周暉杰，復雜系統(tǒng)與復雜性科學復雜系統(tǒng)與復雜性科學，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