非生长性时间累积无标度网络模型解析课件

非生长性时间累积无标度网络模型

报告人：韩筱璞（中国科学院等离子体物理研究所）合作者：谢彦波（中国科学技术大学近代物理系）非生长性时间累积无标度网络模型报告人：韩筱璞1主要内容研究背景模型规则描述模型的方程描述与数值模拟总结与讨论主要内容研究背景2传统的网络研究规则网络、随机网络较均匀的结构低集聚系数传统的网络研究规则网络、随机网络3大量的实际网络极不均匀的结构幂率形式的度分布小平均距离高集聚系数无标度特性小世界特性例如：大量的合作网、WWW、因特网、性接触网、电话呼叫网等大量的实际网络极不均匀的结构无标度特性例如：大量的合作网4重要的无标度网络模型-BA模型BA模型(Barabási,Albert,1999)：存在问题:网络生长优先连接(Πi~ki)富者更富

得到度分布幂指数为-3网络规模必须不停生长各个体都知道其他个体的度

连边是固定的只能得到整数幂指数重要的无标度网络模型-BA模型BA模型(Barabási,5典型非生长性网络模型Park,Lai,andYe,2005Ohkubo,Yasuda,andTanaka,2005Xie,Zhou,andWang,2006主要结论：网络生长不是产生无标度特性的必需条件通过系统的自组织产生无标度特性典型非生长性网络模型Park,Lai,andYe,26时间累积图中节点1于t2时刻被感染节点2于t1时刻和节点1相连接，但不可能被节点1所传染但根据时间累积后的网络结构，节点2则可能被节点1所传染t1t2t31243111222333444对一些网络，在某个瞬时结构是相对均匀的，但统计较长时间的累积网络则可表现出无标度性时间累积特性可能影响系统的动力学特性，如下例时间累积图中节点1于t2时刻被感染t1t2t312431117时间累积网络的意义当一个网络中的连边断开后又恢复连接的概率较小时，该网络的动力学特性与时间累积后的得到的网络相比将有较大差异在传播过程中，该类网络中可能出现一些度（经过时间累积后）很大，或者与其相联的节点的度很大，但被感染的可能性非常小的节点在一些社会网络，特别是性接触网络中，这种特性比较明显时间累积网络的意义当一个网络中的连边断开后又恢复连接的概率较8建模主要针对的问题网络规模生长十分缓慢可以忽略连接过程中个体之间不知道对方的连边数通过时间累积可生成无标度网络建模主要针对的问题网络规模生长十分缓慢可以忽略9模型A-节点规则总节点数N固定节点的寿命给定为Tl初始时刻各节点年龄均布于[0，Tl]内每有一个节点死亡，就会有一个新的初始年龄为0、时间累积度为0的孤立的节点取代它模型A-节点规则总节点数N固定10模型A-连接规则节点在每一时步以可变的概率x处于活跃态，并随机选择主动或被动选择主动的节点随机选择一个选择被动的节点申请连接选择被动的节点在所有向自己申请的主动节点中随机选择一个建立连边建立了新连边的节点的旧连边会自动断开模型A-连接规则节点在每一时步以可变的概率x处于活跃态，并随11模型A-节点状态的改变处于活跃态并且成功建立连边的节点，下一时步处于活跃态的概率x将增大一个定值x’(0<x’<<1)但x不能达到或超过1处于了活跃态但未能建立新的连边的节点下一时步处于活跃态的概率x会减小x’但不能小于或等于0

各节点的初始的x值均为x0(0<x0<<1)

模型A-节点状态的改变处于活跃态并且成功建立连边的节点，下一12在模型A的基础上引入节点的吸引度每个节点都有一个随机的吸引度值各节点的吸引度保持不变在主动节点选择被动节点申请时，和被动节点选择主动节点连接时，其申请概率或连接概率均和被选择方的吸引度值线性相关吸引度值较高的节点有更大的可能成功连接模型B-吸引度的引入在模型A的基础上引入节点的吸引度模型B-吸引度的引入13x(t+1)=x(t)+x’,~

k(t+1)=k(t)+1

withprobabilityx(t)g(x(t)+x’<1)

0(x(t)+x’≥1)

x(t+1)=x(t)–x’,~

k(t+1)=k(t)

withprobabilityx(t)(1–g)(x(t)>x0)0(x(t)=x0)x(t+1)=x(t),~

k(t+1)=k(t)

withprobability1–x(t)(x(t)>x0)1–x0g(x(t)=x0)x(t+1)=x(t),~

k(t+1)=k(t)+1

withprobabilityx(t)g(x(t)+x’≥1)0(x(t)+x’<1)其中g=1–e-1为节点处于活跃态时可成功连接的概率，k为时间累积后节点的度模型A的时间演化0x(t)(1–g)x(t)gx(t)1x(t+1)=x(t)+x’,~k14模型A的主方程令Q(k,n,t)表示节点在t时刻x=x0+nx’且度为k的概率；nm为最大可能的n值，满足x0+nmx’<1且x0+(nm+1)x’≥1，1≤n<nm时：Q(k,n,t+1)–Q(k,n,t)=g[x0+(n–1)x’]Q(k–1,n–1,t)–(x0+nx’)Q(k,n,t)+(1–g)[x0+(n+1)x’]Q(k,n+1,t),n=0时：Q(k,n,t+1)–Q(k,n,t)=–gx0Q(k,n,t)+(1–g)(x0+x’)Q(k,n+1,t),n=nm时：Q(k,n,t+1)–Q(k,n,t)

=g[x0+(n–1)x’]Q(k–1,n–1,t)–(x0+nx’)Q(k,n,t)

+g(x0+nx’)Q(k–1,n,t).统计时间范围为Tl时的累积度分布：模型A的主方程令Q(k,n,t)表示节点在t时刻x15主方程的数值解和数值模拟结果主方程的数值解和数值模拟结果16不同参数下模型A和B的数值模拟结果x0=0.001x’=0.003x0=0.001x’=0.005x0=0.003x’=0.005模型A模型BT=200T=200T=2000T=2000Tl

=2000不同参数下模型A和B的数值模拟结果x0=0.001x017模型的特点和意义网络规模不变，节点进行匀速的更新节点的连接概率和它的度之间没有确定的关系连接概率与连接成功次数和失败次数的差异相关瞬时网络结构较为均匀，每个节点至多同时连接一条连边，类似于单配网络(EamesandKeeling,2004)当一条连边断开后，又重新连接的概率非常小（不同于现有的一些传播模型中的网络）经过较长时间的累积后出现无标度特性该类时间累积网络的传播特性需要进一步研究有助于理解更多的无标度特性的生成机制模型的特点和意义网络规模不变，节点进行匀速的更新18感谢您的关注HanXiao-Puhxpuhotep@感谢您的关注HanXiao-Pu19非生长性时间累积无标度网络模型

报告人：韩筱璞（中国科学院等离子体物理研究所）合作者：谢彦波（中国科学技术大学近代物理系）非生长性时间累积无标度网络模型报告人：韩筱璞20主要内容研究背景模型规则描述模型的方程描述与数值模拟总结与讨论主要内容研究背景21传统的网络研究规则网络、随机网络较均匀的结构低集聚系数传统的网络研究规则网络、随机网络22大量的实际网络极不均匀的结构幂率形式的度分布小平均距离高集聚系数无标度特性小世界特性例如：大量的合作网、WWW、因特网、性接触网、电话呼叫网等大量的实际网络极不均匀的结构无标度特性例如：大量的合作网23重要的无标度网络模型-BA模型BA模型(Barabási,Albert,1999)：存在问题:网络生长优先连接(Πi~ki)富者更富

得到度分布幂指数为-3网络规模必须不停生长各个体都知道其他个体的度

连边是固定的只能得到整数幂指数重要的无标度网络模型-BA模型BA模型(Barabási,24典型非生长性网络模型Park,Lai,andYe,2005Ohkubo,Yasuda,andTanaka,2005Xie,Zhou,andWang,2006主要结论：网络生长不是产生无标度特性的必需条件通过系统的自组织产生无标度特性典型非生长性网络模型Park,Lai,andYe,225时间累积图中节点1于t2时刻被感染节点2于t1时刻和节点1相连接，但不可能被节点1所传染但根据时间累积后的网络结构，节点2则可能被节点1所传染t1t2t31243111222333444对一些网络，在某个瞬时结构是相对均匀的，但统计较长时间的累积网络则可表现出无标度性时间累积特性可能影响系统的动力学特性，如下例时间累积图中节点1于t2时刻被感染t1t2t3124311126时间累积网络的意义当一个网络中的连边断开后又恢复连接的概率较小时，该网络的动力学特性与时间累积后的得到的网络相比将有较大差异在传播过程中，该类网络中可能出现一些度（经过时间累积后）很大，或者与其相联的节点的度很大，但被感染的可能性非常小的节点在一些社会网络，特别是性接触网络中，这种特性比较明显时间累积网络的意义当一个网络中的连边断开后又恢复连接的概率较27建模主要针对的问题网络规模生长十分缓慢可以忽略连接过程中个体之间不知道对方的连边数通过时间累积可生成无标度网络建模主要针对的问题网络规模生长十分缓慢可以忽略28模型A-节点规则总节点数N固定节点的寿命给定为Tl初始时刻各节点年龄均布于[0，Tl]内每有一个节点死亡，就会有一个新的初始年龄为0、时间累积度为0的孤立的节点取代它模型A-节点规则总节点数N固定29模型A-连接规则节点在每一时步以可变的概率x处于活跃态，并随机选择主动或被动选择主动的节点随机选择一个选择被动的节点申请连接选择被动的节点在所有向自己申请的主动节点中随机选择一个建立连边建立了新连边的节点的旧连边会自动断开模型A-连接规则节点在每一时步以可变的概率x处于活跃态，并随30模型A-节点状态的改变处于活跃态并且成功建立连边的节点，下一时步处于活跃态的概率x将增大一个定值x’(0<x’<<1)但x不能达到或超过1处于了活跃态但未能建立新的连边的节点下一时步处于活跃态的概率x会减小x’但不能小于或等于0

各节点的初始的x值均为x0(0<x0<<1)

模型A-节点状态的改变处于活跃态并且成功建立连边的节点，下一31在模型A的基础上引入节点的吸引度每个节点都有一个随机的吸引度值各节点的吸引度保持不变在主动节点选择被动节点申请时，和被动节点选择主动节点连接时，其申请概率或连接概率均和被选择方的吸引度值线性相关吸引度值较高的节点有更大的可能成功连接模型B-吸引度的引入在模型A的基础上引入节点的吸引度模型B-吸引度的引入32x(t+1)=x(t)+x’,~

k(t+1)=k(t)+1

withprobabilityx(t)g(x(t)+x’<1)

0(x(t)+x’≥1)

x(t+1)=x(t)–x’,~

k(t+1)=k(t)

withprobabilityx(t)(1–g)(x(t)>x0)0(x(t)=x0)x(t+1)=x(t),~

k(t+1)=k(t)

withprobability1–x(t)(x(t)>x0)1–x0g(x(t)=x0)x(t+1)=x(t),~

k(t+1)=k(t)+1

withprobabilityx(t)g(x(t)+x’≥1)0(x(t)+x’<1)其中g=1–e-1为节点处于活跃态时可成功连接的概率，k为时间累积后节点的度模型A的时间演化0x(t)(1–g)x(t)gx(t)1x(t+1)=x(t)+x’,~k33模型A的主方程令Q(k,n,t)表示节点在t时刻x=x0+nx’且度为k的概率；nm为最大可能的n值，满足x0+nmx’<1且x0+(nm+1)x’≥1，1≤n<nm时：Q(k,n,t+1)–Q(k,n,t)=g[x0+(n–1)x’]Q(k–1,n–1,t)–(x0+nx’)Q(k,n,t)+(1–g)[x0+(n+1)x’]Q(k,n+1,t),n=0时：Q(k,n,t+1)–Q(k,n,t)=–gx0Q(k,n,t)+(1–g)(