度相关性测度

1、15:141度相关性测度度相关性测度 20102010年年1010月月1717日日上海大学上海大学 史定华史定华宁波大学宁波大学 周晖杰周晖杰 2 内容提要内容提要F度相关的度相关的重要性重要性F联合度分布联合度分布F邻结点平均度邻结点平均度F度相关系数度相关系数F无标度程度无标度程度F测度测度合理性合理性讨论讨论F度混合系数度混合系数3 度相关的重要性度相关的重要性F 网络度分布太宏观网络度分布太宏观网络网络度分布度分布完全相同，其拓扑结构可完全不同完全相同，其拓扑结构可完全不同1. Holme-Kim(BA)模型模型1可调群集系数可调群集系数2. 复制模型和自然数整除复制模型和自然数整除2

2、随机与确定随机与确定3. 保度重连会改变特征值保度重连会改变特征值Chen局部与整体局部与整体F 网络拓扑组织结构网络拓扑组织结构 指标：指标：群集系数，平均路径，介数等群集系数，平均路径，介数等 度相关性度相关性动力学最关心邻域结构动力学最关心邻域结构4 两个模型度分布比较两个模型度分布比较F自然数整除网络自然数整除网络确定确定F度分布完全一致度分布完全一致随机随机11kkNpp21( )(1)(2)inP kkkk5 联合度分布联合度分布FDorogovtsev等人定义等人定义3 其中其中 是网络是网络的邻接矩阵的邻接矩阵 FKrapivsky等人的结果等人的结果4cited by 335

3、对对m = 1时时BA模型模型发现非平凡相关模型模型发现非平凡相关上式最重要的意义是上式最重要的意义是 ,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 (三种指数三种指数网络网络结构及其结构及其)联合度分布联合度分布7 邻结点平均度邻结点平均度5cited by 593FPastor-Satorras等人等人引入引入条件概率条件概率 表示度相关性表示度

4、相关性F实际计算实际计算采用邻结点采用邻结点平均度，若平均度，若幂律幂律 ，则由，则由指数指数确定确定(| )cP kk8 度相关系数度相关系数6,7cited by 1082FNewman采用相关系数来刻画采用相关系数来刻画 V是网络是网络g的结点集，的结点集，E是连线集，结点度序列是连线集，结点度序列 。度相关系数。度相关系数(需方差存在需方差存在)为为F或等价地或等价地212( , )( , )2221122( , )( , )()( )()()ijiji jEi jEijiji jEi jEddEddEr gddEddE2212( , )2321122( )ijii jEi Viii

5、Vi Vd ddEr gddE12,NDd dd9 某些网络度相关系数某些网络度相关系数610 无标度程度无标度程度8cited by 236FLi等人则引入无标度程度等人则引入无标度程度 表示由于结点之间连线不同而具有相表示由于结点之间连线不同而具有相同度序列的网络同度序列的网络(简单无向连通图简单无向连通图)全体。全体。 计算计算 ，令，令 表示表示 中中的的 最大值，定义测度最大值，定义测度 (无限之比能稳定吗无限之比能稳定吗) 来来衡量网络衡量网络 的无标度程度。大称为的无标度程度。大称为“无标无标度的度的” ；小为；小为“标度丰富的标度丰富的” 。F相关系数第一项精确等于相关系数第一

6、项精确等于 ( )G D( , )( )iji jEs gd dmaxs( )G D( )s gmax( )( )S gs gsg( )s gE11 F 由于幂律递减特性由于幂律递减特性 F 联合分布无法判断联合分布无法判断F 不像前面指数网络不像前面指数网络F 泊松逼近正态泊松逼近正态F 容易看出差异容易看出差异 m=1时联合度分布时联合度分布 幂律再现难以应对幂律再现难以应对讨论讨论: BA模型的联合度分布模型的联合度分布4(1)12(1)( , )(1)()(1)(2)(1)()(1)(2)llP k lk kkl klklk klkl klkl 12 讨论讨论: BA模型的度相关系数模

7、型的度相关系数 F模拟模拟网络规模网络规模 从从100到到 10000个个结点结点平均度从平均度从 2到到14的的网络网络模拟结果模拟结果 13 讨论讨论: BA模型的无标度程度模型的无标度程度 F模拟模拟网络规模网络规模 从从100到到 10000个个结点结点平均度从平均度从 2到到14的的网络网络模拟结果模拟结果 14 测度合理性讨论测度合理性讨论总结总结F联合度分布是度相关性的最完整的刻画联合度分布是度相关性的最完整的刻画 只对只对BA模型有结果；模型有结果；没有没有简单简单数量指标数量指标。 F邻结点平均度考虑了邻结点度邻结点平均度考虑了邻结点度 若若不是幂律不是幂律无法判断；无法判断

8、；BA模型模型不相关！不相关！F相关系数由于规范化具有误导性相关系数由于规范化具有误导性 数值大小数值大小依赖网络规模依赖网络规模； BA模型模型不相关！不相关！F无标度程度稳定性没有涉及无标度程度稳定性没有涉及 数值大小也数值大小也依赖网络规模依赖网络规模； BA模型模型不大不大15 度相关性度相关性有有更佳测度吗更佳测度吗? ?F网络拓扑测度网络拓扑测度Barabsi说从说从度分布到度相关性度分布到度相关性, 不同拓扑特征的广不同拓扑特征的广泛存在性被作为研究不同现象以及做出预测的跳板。泛存在性被作为研究不同现象以及做出预测的跳板。F测度的合理性测度的合理性 网络度分布网络度分布度指数独立

9、于网络规模，这是优点也是缺点度指数独立于网络规模，这是优点也是缺点 度相关性度相关性现有指标依赖于网络规模，联合度分布对幂律不敏感现有指标依赖于网络规模，联合度分布对幂律不敏感 更佳测度更佳测度不不依赖于网络规模，能给出局部结构的度相关性依赖于网络规模，能给出局部结构的度相关性16 度混合系数度混合系数一种新的测度一种新的测度F 原则原则同配得正异配为负同配得正异配为负F 算法算法先算结点后算网络先算结点后算网络1. 将网络结点按平均度分为两个集合将网络结点按平均度分为两个集合2. 大于平均度结点与大于平均度结点连线为正大于平均度结点与大于平均度结点连线为正1否则为负否则为负13. 小于平均度

10、结点与小于平均度结点连线为正小于平均度结点与小于平均度结点连线为正1否则为负否则为负14. 计算每个计算每个结点结点的的混合系数混合系数求和除以度数求和除以度数5. 将结点混合系数平均得将结点混合系数平均得网络混合系数网络混合系数17 BA模型的度混合系数模型的度混合系数 F模拟模拟网络规模网络规模 从从100到到 10000个个结点结点平均度从平均度从 2到到14的的网络网络模拟结果模拟结果 18 度混合系数度混合系数与连线数关系与连线数关系 10000个结点，平均度从个结点，平均度从2到到60的结果的结果 与网络与网络规模无关规模无关与平均度与平均度成反比成反比尚缺少尚缺少度的信息度的信息

11、问题并问题并没有解决没有解决19 随机失效与蓄意攻击随机失效与蓄意攻击9F特性特性稳健稳健脆弱脆弱 F解释解释结点异质结点异质F质疑质疑网络核心网络核心 纵坐标网络直径纵坐标网络直径d；横坐标除去结点比例；横坐标除去结点比例f 20 度混合系数的应用度混合系数的应用F罩门罩门 hub结点结点 误解：误解：无标度网结点异质，所以稳健而又脆弱无标度网结点异质，所以稳健而又脆弱F质疑质疑 标度程度标度程度 例子：例子：虽然因特网无标度，但是显示标度丰富虽然因特网无标度，但是显示标度丰富F探讨探讨 网络核心网络核心 结构：结构：攻击结点，即网络核心形成的攻击结点，即网络核心形成的局部局部结构，结构，与

12、全局结构不同。度混合系数可以测量，例如与全局结构不同。度混合系数可以测量，例如0.1%， IBA(核心核心)=0.080; IAS(核心核心)= ？ 猜测猜测 0。尽管尽管BA模型和因特网都标度丰富，但核心结构不同模型和因特网都标度丰富，但核心结构不同!21 进一步研究的问题进一步研究的问题F度相关测度度相关测度(更多信息更多信息) 考虑结点度的相关测度考虑结点度的相关测度-M(g) MBA(网络网络)= 0.312 MBA(核心核心)= 0.718动力学相关性测度动力学相关性测度-利用核函数利用核函数F相关性过程相关性过程(相互作用相互作用) 考虑考虑 结点度的演化结点度的演化 结点的动力学

13、结点的动力学两者相互影响是我们需要攻克的难题。两者相互影响是我们需要攻克的难题。 ()()( )()()iiijj Oijj OdkdkM idkdk( ), ( )iiK tX t( )iK t( )iX t22 总结：总结：网络拓扑学和动力学网络拓扑学和动力学10F网络拓扑学网络拓扑学(随机过程随机过程) Barabsi说说除非探讨其网络拓扑，否则没有办法去除非探讨其网络拓扑，否则没有办法去理解复杂系统。理解复杂系统。如何探讨？有限维分布族。如何探讨？有限维分布族。 网络度分布研究已有较好的基础，特别是动力学指网络度分布研究已有较好的基础，特别是动力学指数抓住了要害。数抓住了要害。一维分布

14、，幂律，度指数。一维分布，幂律，度指数。 但是度相关性等其它测度还需要理清。但是度相关性等其它测度还需要理清。二维分布？二维分布？F网络动力学网络动力学(动力系统动力系统) Barabsi说说共性是存在的，我们只是还没有发现能共性是存在的，我们只是还没有发现能够解释它们普遍性的框架。够解释它们普遍性的框架。这是我们需要攻克的下一个前沿问题。这是我们需要攻克的下一个前沿问题。 23 参考文献参考文献1 P. Holme, B. J. Kim, Phys. Rev. E 65, 026107(2002) 2史定华，周晖杰，史定华，周晖杰，复杂系统与复杂性科学复杂系统与复杂性科学，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