复杂网络建模与控制4_3

厦门大学信息科学与技术学院:[e-mail]:13720898017项林英复杂网络建模与控制ModellingandControlofComplexNetworks2012/3/282复杂网络模型1959年Erdös和Rényi引入随机图论1736年欧拉解决哥尼斯堡七桥问题创立图论规则网络随机网络2012/3/28复杂网络模型3三种规则网络和ER随机网络的基本拓扑性质比较网络边数平均路径长度聚类系数度分布全耦合网络N(N-1)/211delta最近邻网络NK/2(N+2)/(2K)3(K-2)/[4(K-1)]delta星形网络N-12-2/N0ER随机网络pN(N-1)/2~lnN/lnkp=k/(N-1)Poission4最近邻网络与ER随机网络的拓扑性质比较网络边数平均路径长度聚类系数度分布最近邻网络NK/2(N+2)/(2K)3(K-2)/[4(K-1)]deltaER随机网络pN(N-1)/2~lnN/lnkp=k/(N-1)Poission5最近邻网络与ER随机网络的拓扑性质比较网络边数平均路径长度聚类系数度分布最近邻网络NK/2(N+2)/(2K)3(K-2)/[4(K-1)]deltaER随机网络pN(N-1)/2~lnN/lnkp=k/(N-1)Poission6最近邻网络与ER随机网络的拓扑性质比较网络边数平均路径长度聚类系数度分布最近邻网络NK/2(N+2)/(2K)3(K-2)/[4(K-1)]deltaER随机网络pN(N-1)/2~lnN/lnkp=k/(N-1)Poission•最近邻网络:较大的平均路径长度•ER随机网络:较小的平均路径长度7最近邻网络与ER随机网络的拓扑性质比较•最近邻网络:较大的平均路径长度•ER随机网络:较小的平均路径长度网络边数平均路径长度聚类系数度分布最近邻网络NK/2(N+2)/(2K)3(K-2)/[4(K-1)]deltaER随机网络pN(N-1)/2~lnN/lnkp=k/(N-1)Poission8最近邻网络与ER随机网络的拓扑性质比较•最近邻网络:较大的平均路径长度和较大的聚类系数•ER随机网络:较小的平均路径长度和较小的聚类系数网络边数平均路径长度聚类系数度分布最近邻网络NK/2(N+2)/(2K)3(K-2)/[4(K-1)]deltaER随机网络pN(N-1)/2~lnN/lnkp=k/(N-1)Poission9最近邻网络与ER随机网络的拓扑性质比较•最近邻网络:较大的平均路径长度和较大的聚类系数•ER随机网络:较小的平均路径长度和较小的聚类系数网络边数平均路径长度聚类系数度分布最近邻网络NK/2(N+2)/(2K)3(K-2)/[4(K-1)]deltaER随机网络pN(N-1)/2~lnN/lnkp=k/(N-1)Poission10最近邻网络与ER随机网络的拓扑性质比较•最近邻网络:较大的平均路径长度和较大的聚类系数•ER随机网络:较小的平均路径长度和较小的聚类系数节点度服从Poisson分布(图像是一条钟形的曲线),因而比较“均匀”，即大部分的节点度相差不多网络边数平均路径长度聚类系数度分布最近邻网络NK/2(N+2)/(2K)3(K-2)/[4(K-1)]deltaER随机网络pN(N-1)/2~lnN/lnkp=k/(N-1)Poission11最近邻网络与ER随机网络的拓扑性质比较•最近邻网络:较大的平均路径长度和较大的聚类系数•ER随机网络:较小的平均路径长度和较小的聚类系数节点度服从Poisson分布(图像是一条钟形的曲线),因而比较“均匀”，即大部分的节点度相差不多实际网络:较小的平均路径长度和较大的聚类系数网络边数平均路径长度聚类系数度分布最近邻网络NK/2(N+2)/(2K)3(K-2)/[4(K-1)]deltaER随机网络pN(N-1)/2~lnN/lnkp=k/(N-1)Poission小世界特性12完全规则网络和完全随机网络之间可能的联系13第四章复杂网络模型4.1规则网络模型4.2随机网络模型4.3小世界网络模型4.4无标度网络模型14小世界现象•在一千多年前，我国唐朝诗人王勃在《送杜少府之任蜀州》中的名句“海内存知己,天涯若比邻”,已经涵盖了小世界现象——中国人从人文和哲学上最先认识到了小世界现象•1967年美国社会学家Milgram提出的“六度分离”假设——作了一定的社会调查和实验证实复杂网络模型1516小世界网络•CollectiveDynamicsof'small-world'networks.Nature,1998,393:440-442.S.H.StrogatzD.J.WattsCornellUniversity复杂网络模型17复杂网络模型1819WS小世界模型的构造算法•首先开始于规则图形:初始有数目固定的N个节点，每个节点有K个最近邻，构成一个规则的一维圆环。•随机化重连:以概率P对圆环中的每一条边进行重新连接。这个过程不能自身连接和重复连接。20P=00P1P=12012/3/28复杂网络模型21P=00P1P=1(a)规则网络(b)小世界网络(c)随机网络22WS小世界模型的基本性质•平均路径长度:•聚类系数:•度分布:LWS≈(N/K)f(NKp)CWS≈3(K-2)/[4(K-1)](1-p)3Poission分布2012/3/28复杂网络模型23仿真分析•平均路径长度:LWS≈(N/K)f(NKp)•聚类系数:CWS≈3(K-2)/[4(K-1)](1-p)3平均路径长度L和聚类系数C关于重连概率p的关系给定参数N=1000,K=102012/3/28复杂网络模型24仿真分析•平均路径长度:LWS≈(N/K)f(NKp)•聚类系数:CWS≈3(K-2)/[4(K-1)](1-p)3较小的平均路径长度L较大的聚类系数C平均路径长度L和聚类系数C关于重连概率p的关系小世界网络！给定参数N=1000,K=1025实际验证小世界网络的三个实例26Small-WordNetworksSomeexamples……27科学家合作网节点：科学家边：合作发表文章或合作研究项目M.E.J.Newman(2001)andA.L.Barabásietal.(2001)L=4~928电路图节点：元器件边：电子线路R.F.Cancho,etal,Phys.Rev.,64,046119(2001)L=429ER随机图模型与WS小世界模型的共同点30ER随机图模型与WS小世界模型的共同点•网络连接度分布是泊松分布，具有同质性，在一个平均值处达到高峰并按指数形式进行衰减。31ER随机图模型与WS小世界模型的共同点•网络连接度分布是泊松分布，具有同质性，在一个平均值处达到高峰并按指数形式进行衰减。•网络中节点数目是固定不变的，是一种静态的网络模型。32ER随机图模型与WS小世界模型的共同点•网络连接度分布是泊松分布，具有同质性，在一个平均值处达到高峰并按指数形式进行衰减。•网络中节点数目是固定不变的，是一种静态的网络模型。•实际网络？33第四章复杂网络模型4.1规则网络模型4.2随机网络模型4.3小世界网络模型4.4无标度网络模型34无标度网络•Emergenceofscalinginrandomnetworks.Science,1999,286:509-512.R.AlbertA.-L.BarabásiNorteDameUniversity复杂网络模型353637BA无标度网络模型的构造算法38BA无标度网络模型的构造算法•增长39BA无标度网络模型的构造算法•增长•优先连接40BA无标度网络模型的构造算法•增长:从一个具有m0个节点的连通网络开始，在每一个时间步，加入一个新的节点，并与m(m≤m0)个网络中已经存在的节点建立连接；41BA无标度网络模型的构造算法•增长:从一个具有m0个节点的连通网络开始，在每一个时间步，加入一个新的节点，并与m(m≤m0)个网络中已经存在的节点建立连接；•优先连接:一个新节点与一个已经存在的节点i相连接的概率正比于节点i的度ki:42BABA无标度网络的演化无标度网络的演化参数m0=M0=3,m=243BA无标度网络模型的基本性质•平均路径长度:•聚类系数:•度分布:LBA～lnN/lnlnNCBA～(lnt)2/t幂律分布P(k)~k-r44BA无标度网络模型的基本性质•平均路径长度:LBA～lnN/lnlnN•聚类系数:CBA～(lnt)2/t•度分布:幂律分布P(k)~k-r•网络连接度分布是幂律分布，具有异质性，即少数节点有很高的度，但大部分的节点的度却很小。•网络中节点和边是连续增长的，是一种动态的网络模型。2012/3/28复杂网络模型45网络度分布全耦合/最近邻耦合网络deltaER随机网络PoissionWS小世界网络PoissionBA无标度网络幂律(a)delta分布(b)Poission分布(c)幂律分布典型网络的度分布比较46Scale-FreeNetworksSomeexamples……复杂网络模型47复杂网络模型4849WS小世界网络研究和BA无标度网络研究之间的共性特征50WS小世界网络研究和BA无标度网络研究之间的共性特征•师生合作完成并发表在最顶级期刊——美国Cornell大学的博士生Watts及其导师Strogatz教授，1998年6月在《Nature》上发表；——美国NotreDame大学物理系的Barabási教授及其博士生Albert，1999年10月在《Science》上发表。51WS小世界网络研究和BA无标度网络研究之间的共性特征•师生合作完成并发表在最顶级期刊——美国Cornell大学的博士生Watts及其导师Strogatz教授，1998年6月在《Nature》上发表；——美国NotreDame大学物理系的Barabási教授及其博士生Albert，1999年10月在《Science》上发表。•迅速成为网络科学文献中的Hub节点——据GoogleScholar统计，截至2012年1月1日，WS小世界网络的文章被引用14791次，BA无标度网络的文章被引用12472次。52WS小世界网络研究和BA无标度网络研究之间的共性特征•师生合作完成并发表在最顶级期刊——美国Cornell大学的博士生Watts及其导师Strogatz教授，1998年6月在《Nature》上发表；——美国NotreDame大学物理系的Barabási教授及其博士生Albert，1999年10月在《Science》上发表。•迅速成为网络科学文献中的Hub节点——据GoogleScholar统计，截至2012年1月1日，WS小世界网络的文章被引用14791次，BA无标度网络的文章被引用12472次。•建模、仿真和实际验证的文章结构——针对实际网络的一些特征建立模型并基于实际数据加以验证。两篇文章中的部分实际网络的数据相同。53WS小世界网络研究和BA无标度网络研究之间的共性特征•师生合作完成并发表在最顶级期刊——美国Cornell大学的博士生Watts及其导师Strogatz教授，1998年6月在《Nature》上发表；——美国NotreDame大学物理系的Barabási教授及其博士生Albert，1999年10月在《Science》上发表。•迅速成为网络科学文献中的Hub节点——据GoogleScholar统计，截至2012年1月1日，WS小世界网络的文章被引用14791次，BA无标度网络的文章被引用12472次。•建模、仿真和实际验证的文章结构——针对实际网络的一些特征建立模型并基于实际数据加以验证。两篇文章中的部分实际网络的数据相同。•勇于迎接挑战54Watts在2003年出版的书《SixDegrees》中在回忆这段经历时深表后悔：“当我在1999年4