无标度加权网络建模分析
|
摘要
复杂网络可以描述自然界和社会中的各种大规模系统。诸如万维网、因特网、国际机场网、细胞网、生态网、科学家合作网等等都可以用复杂网络来刻画。其中网络节点表示系统的元素,两点间的边表示元素间的相互关系。
实证研究揭示了实际网络的显著特点,许多现实网络的度分布P(k)具有幂律分布,即P(k)～k~(-r)(对于大k)。这种网络常称为无标度网络,其度分布具有重尾部特征。为了揭示这类网络的演化机制,Barabasi与Albert提出了著名的BA模型,该模型发现了许多实际网络在演化过程中的重要机制:增长与择优连接。此后,人们提出了一系列的无标度网络演化模型,并对网络模型的性质作了更加深入的研究。
复杂网络的演化模型备受关注。其中加权网络模型是一个重要的研究领域。所谓加权网络即对网络中每条边赋予一个权重值。因为在实际情形中,系统元素间的相互作用程度往往也有强弱之分,加权网络在这方面更贴近实际。例如;在科学协作网中,用两个作者之间合作的文章数来表示边的权重,反映作者间的合作程度;在国际机场网中,边的权重可以表示两个机场之间的客流量,反映机场间的往来程度。
本文主要研究具有随机权重的加权网络,提出三个加权网络的演化模型,并加以理论分析:
(1)提出—个权重演化的加权网络模型。每个时间间隔增加一个新点,按照依强度择优的原则,新点与系统中的m个旧点连接,同时产生m条新边。对每条新边赋予一个随机权重ω,具有分布密度ρ(ω)。同时在系统原有连线中,随机选择n条不同的边,对它们增加一个随机权重值△ω。研究表明,该模型生成的网络权重分布具有幂律尾部特征。
(2)提出一个具有多重随机权重的加权网络模型。网络中边的权重取自三种不同的随机分布。首先,把网络节点分为A-type与B-type,每个时间间隔增加一个新点,新点以一定概率为A-type或B-type。同时产生m条新边择优连接系统中的旧点,并对新产生的连线赋予一个随机权重.A-type节点与B-type节点间的连线权重服从分布密度ρ_0(ω)(ω≥0);A-type节点与A-type节点间的连线权重服从ρ_1(ω)(ω≥0);B-type节点与B-type节点间的连线权重服从ρ_2(ω)(ω≥0)。由此演化的网络中边的权重来自三个不同的分布类型,分别取决于连线的节点间的不
同类型.研究表明,该模型生成网络的权重分布与度分布都具有幂律尾部特征。
(3)提出一个基于适应度的无标度加权网络模型。假设每个点都有一个适应度x,代表节点本身的能力水平。因各个个体能力不尽相同,考虑x是个随机变量,服从某种分布。那么两点间连线的权重可以取决于这两点的适应度,假设是关于适应度的函数。分析了网络的特性之后,证明网络的强度分布以及度分布都具有幂律尾部。
In recent years, complex networks is a useful model to describe a wide range of systems in nature and society, which has attracted much more attention.Many models like Web, Internet, world wide airport networks, cellular networks, ecological networks, scientific collaboration networks, etc,can be depicted by the networks, where the nodes are the elements of system and edges represent the interaction between them.
Empirical research results show that many of these real networks are scale-free:the degree distribution has a power-law tail, i.e., P(k)～Ak~(-α) for large k, where A,αare constant.To investigate the mechanisms responsible for the properties Barabasi and Albert proposed BA model in 1999, which introduce the concepts of growing networks and preferential attachment. In the wake of their works,many more Scale-free models are proposed to interpret the complex networks.
One major aspect of the research is weighted network,in which each link in the system is assigned a weight. It is well known that in many fields the interaction strength can vary widely.So weighted network is a better model to describe. For example,in a collaboration networks,the weight of a link between co-authors measures the strength of the collaboration such as the number of jointly-authored publications. In the airline transportation network(WAN),the weight of a link between two airports gives the passenger capacity on this route.
In this paper, we focus on weighted networks and propose three evolving network models that can produce weighted scale-free networks and analyze the networks by the combined numerical and analytical approach:
(1)We propose a model of weighted networks where weights of links evolve with time. At each time step,a new node is added with some edges that link the new node to exiting nodes preferentially. Meanwhile these new edges have weights drawn from certain distributionρ(ω)(ω≥0).Then some edges are randomly selected, and add some weightΔωalso drawn from the same distribution.We calculate the distribution density of the weight and do some simulation as a testimony. In this course we attain a power-law tail whereγ> 2.
(2)A weighted network model with multi stochastic weights is proposed, where the weights of links are drawn from several different distributions.Nodes in the system are divided into two types:A-type and B-type.At each time step,a new node either A or B-type is added to the system,with m new edges connecting the existing nodes .Meanwhile, each new created edge is assigned certain random weight. The weight between A-type node and B-type node is drawn fromρ_0(ω)(ω≥0);within A-type nides fromρ_1(ω)(ω≥0);within B-type nodes fromρ_0(ω)(ω≥0).Thus the weight of each link is from three different distributions,relying on the types of nodes.Analytical results show that the model can produce a network with the power-law distributions of strength and degree.
(3)We propose a weighted network based on the intrinsic fitness. In the model, each vertex has a fitness drawn from certain distribution,weights of links depending on the fitness of both ends. Then we calculate the distribution of the weight and the degree with the mean-field theory. In this course we attain a power-law distribution and deduce the common formula ofγ.
实证研究揭示了实际网络的显著特点,许多现实网络的度分布P(k)具有幂律分布,即P(k)～k~(-r)(对于大k)。这种网络常称为无标度网络,其度分布具有重尾部特征。为了揭示这类网络的演化机制,Barabasi与Albert提出了著名的BA模型,该模型发现了许多实际网络在演化过程中的重要机制:增长与择优连接。此后,人们提出了一系列的无标度网络演化模型,并对网络模型的性质作了更加深入的研究。
复杂网络的演化模型备受关注。其中加权网络模型是一个重要的研究领域。所谓加权网络即对网络中每条边赋予一个权重值。因为在实际情形中,系统元素间的相互作用程度往往也有强弱之分,加权网络在这方面更贴近实际。例如;在科学协作网中,用两个作者之间合作的文章数来表示边的权重,反映作者间的合作程度;在国际机场网中,边的权重可以表示两个机场之间的客流量,反映机场间的往来程度。
本文主要研究具有随机权重的加权网络,提出三个加权网络的演化模型,并加以理论分析:
(1)提出—个权重演化的加权网络模型。每个时间间隔增加一个新点,按照依强度择优的原则,新点与系统中的m个旧点连接,同时产生m条新边。对每条新边赋予一个随机权重ω,具有分布密度ρ(ω)。同时在系统原有连线中,随机选择n条不同的边,对它们增加一个随机权重值△ω。研究表明,该模型生成的网络权重分布具有幂律尾部特征。
(2)提出一个具有多重随机权重的加权网络模型。网络中边的权重取自三种不同的随机分布。首先,把网络节点分为A-type与B-type,每个时间间隔增加一个新点,新点以一定概率为A-type或B-type。同时产生m条新边择优连接系统中的旧点,并对新产生的连线赋予一个随机权重.A-type节点与B-type节点间的连线权重服从分布密度ρ_0(ω)(ω≥0);A-type节点与A-type节点间的连线权重服从ρ_1(ω)(ω≥0);B-type节点与B-type节点间的连线权重服从ρ_2(ω)(ω≥0)。由此演化的网络中边的权重来自三个不同的分布类型,分别取决于连线的节点间的不
同类型.研究表明,该模型生成网络的权重分布与度分布都具有幂律尾部特征。
(3)提出一个基于适应度的无标度加权网络模型。假设每个点都有一个适应度x,代表节点本身的能力水平。因各个个体能力不尽相同,考虑x是个随机变量,服从某种分布。那么两点间连线的权重可以取决于这两点的适应度,假设是关于适应度的函数。分析了网络的特性之后,证明网络的强度分布以及度分布都具有幂律尾部。
In recent years, complex networks is a useful model to describe a wide range of systems in nature and society, which has attracted much more attention.Many models like Web, Internet, world wide airport networks, cellular networks, ecological networks, scientific collaboration networks, etc,can be depicted by the networks, where the nodes are the elements of system and edges represent the interaction between them.
Empirical research results show that many of these real networks are scale-free:the degree distribution has a power-law tail, i.e., P(k)～Ak~(-α) for large k, where A,αare constant.To investigate the mechanisms responsible for the properties Barabasi and Albert proposed BA model in 1999, which introduce the concepts of growing networks and preferential attachment. In the wake of their works,many more Scale-free models are proposed to interpret the complex networks.
One major aspect of the research is weighted network,in which each link in the system is assigned a weight. It is well known that in many fields the interaction strength can vary widely.So weighted network is a better model to describe. For example,in a collaboration networks,the weight of a link between co-authors measures the strength of the collaboration such as the number of jointly-authored publications. In the airline transportation network(WAN),the weight of a link between two airports gives the passenger capacity on this route.
In this paper, we focus on weighted networks and propose three evolving network models that can produce weighted scale-free networks and analyze the networks by the combined numerical and analytical approach:
(1)We propose a model of weighted networks where weights of links evolve with time. At each time step,a new node is added with some edges that link the new node to exiting nodes preferentially. Meanwhile these new edges have weights drawn from certain distributionρ(ω)(ω≥0).Then some edges are randomly selected, and add some weightΔωalso drawn from the same distribution.We calculate the distribution density of the weight and do some simulation as a testimony. In this course we attain a power-law tail whereγ> 2.
(2)A weighted network model with multi stochastic weights is proposed, where the weights of links are drawn from several different distributions.Nodes in the system are divided into two types:A-type and B-type.At each time step,a new node either A or B-type is added to the system,with m new edges connecting the existing nodes .Meanwhile, each new created edge is assigned certain random weight. The weight between A-type node and B-type node is drawn fromρ_0(ω)(ω≥0);within A-type nides fromρ_1(ω)(ω≥0);within B-type nodes fromρ_0(ω)(ω≥0).Thus the weight of each link is from three different distributions,relying on the types of nodes.Analytical results show that the model can produce a network with the power-law distributions of strength and degree.
(3)We propose a weighted network based on the intrinsic fitness. In the model, each vertex has a fitness drawn from certain distribution,weights of links depending on the fitness of both ends. Then we calculate the distribution of the weight and the degree with the mean-field theory. In this course we attain a power-law distribution and deduce the common formula ofγ.
引文
[1]Erd(o|¨)s P,Penyi A.On the evolution of random graphs.Publ.Math.Inst.Hung.Acad.Sci.,1960,5:17-61.
[2]Watts D J,Strogatz S H.Collective dynamics of small-world networks.Nature,1998,393:440.
[3]M.E.J.Newman,Models of small world(A Review).cond-mat/0001118v2,2000 May 9.
[4]A L,Barabasi,Albert R.Emergence of scaling in random networks.Science,1999,286:509-512.
[5]Barabasi A L,Albert R,Jeong H.Mean-field theory for scale-free random networks.Physica A,1999,272:173-187.
[6]Barabasi A L,Albert R.Topology of evolving networks:local events and universality.Physical Rev Lett,1999,85:5234-5237.
[7]R.Albert,A.-L.Barabasi.Statistical mechanics of complex networks.Rev.Mod.Phys,2002,74:47-97.
[8]R.Albert,A.-L.Barabasi,E.Bonabau.Scale free networks.Scientific American,2003May:50-59.
[9]M.E.J.Newman.The structure and function of complex networks.SIAM REVIEW (Society for Industrial and Applied Mathematics),2003,45:167-256.
[10]Dorogovtsev S N,Mendes J F F,Samukhin A N.Structure of growing networks with preferential linking.Phys.Rev.Lett.,2000,85(21):4633-4636.
[11]Krapivsky P L,Redner S,Leyvraz F.Connectivity of Growing Random Networks.Phys.Rev.Lett.,2000,85:4629-4632.
[12]Dorogovtsev S N,Mendes J F F.Evolution of networks.Advances in physics,2001,90:123-143
[13]S.H.Yook,A.-L.Barabasi.Weighted Evolving Networks.Phys.Rev.Lett.,2001,86:5835-5838
[14]T.Antal,P.L.Krapivsky.Weight-driven growing networks.P.R.E,2005,71:026103.
[15]Barrat A,Barthelemy,Vespignani A.Modeling the evolution of weighted networks.Phys.R.E,2004,70:066149.
[16]Wang W X,Wang B H,Hu B,Yan G,Ou Q.General Dynamics of Topology and Traffic on Weighted Technological Networks.Phys.Rev.Lett.,2005,94:188702.
[17]Barrat A,Barthelemy M,Pastor-Satorras,Vespignani A.The architecture of complex weighted networks.PNAS,2004,70:3747-3752
[18]S H Chen(陈盛辉),Q H Chen(陈庆华).A Weighted Network Model Based on the Preferential Selection of Edges.Applied Mathematical Sciences,2007,Vol.1:1145-1156.
[19]徐道炜,陈庆华.一个非匹配的加权网络.莆田学院学报,2007,Vol.14,No2
[20]Tomer Kalisky,Sameet Sreenivasan,Lidia A.Braunstein,Sergey V.Buldyrev.Scalefree networks emerging from weighted random graphs.Phys.Rev.E,2006,025103:1-4.
[21]陈盛辉.具有高集群的加权无标度网络建模分析(福建师范大学硕士学位论文),2007.4.
[22]徐道炜.无标度网络拓扑和动力学研究(福建师范大学硕士学位论文),2007.4.
[23]G.Caldarelli,A.Capocci,P.De Los Rios,A.Munoz.Scale-Free Networks from Varying Intrinsic Fitness.Phys.Rev.Letters,2002,258702:1-4.
[24]Krapivsky P L,Redner S.Organization of growing random networks.Phys.Rev.E,2001,066123:63.
[25]陈庆华.无标度网络的相关性和联合度分布.福建师范大学学报(自然科学版),2006,22(1):1-6.
[26]Brrat A,Barthelemy M,Pastor-satorras R,Vespignani A.The architecture of complex weighted networks.Proc.Natl.Acad.Sci.U.S.A.,2004,101:3747-3752.
[27]Li xiang,Chert G R.A local-world evolving network model.Physic A,2003,328:274-286.
[28]Saram(a|¨)ki J,Kaski K.Scale-free networks generated by random walkers.Physic A,2004,341:80-86.
[29]Li C G,Chen G R.Network connection strengths:Another power-law?.condmat,2003,:0311333.
[30]Garlaschelli D,Battiston S,Castri M,Servedio V D P,Caldarelli G.The scale-free topology of market investments.cond-mat,2003,:0310503.
[31]Yook S H,Jeong H,Barabasi A L,Tu Y.Weighted evolving networks.Phys.Rev.Lett.,2001,86:5835-5838.
[32]Barabasi A L,Albert R,Jeong H.Me,n-field theory for scale-free random networks.Physic A,1999,272:173-187.
[33]Zheng D,Trimper S,Zheng B,Hui P M.Weighted scale-free networks with stochastic weight assignments.Phys.Rev.E,2003,67:040102.
[34]Bianconi G,Barsbasi A L.Competition and multiscaling in evolving networks.Europhys.Lett.,2001,54:436-442.
[35]Barrat A,Barthelemy M,Vespignani A.Weighted Evolving Networks:Coupling Topology and Weight Dynamics.Phys.Rev.Lett,2004,92:228701.
[36]Barrat A,Barthelemy M,Vespignani A.Modeling the evolution of weighted networks.Phys.Rev.E,2004,70:066149.
[37]Wang W X,Wang B H,Hu B,Yan G,Ou Q.General Dynamics of Topology and Traffic on Weighted Technological Networks.Phys.Rev.Lett,2005,94:188702.
[38]Wang W X,Hu B,Zhou T,Wang B H,Xie Y B.Mutual selection model for weighted networks.Phys.Rev.E,2005,72:046140.
[39]Chen Q H,Shi D H.Markov chains theory for scale-free networks.Physic A,2006,360:121-133.
[40]Shi D H,Chen Q H,Liu L.Markov chain-based numerical method for degree distributions of growing networks.Phys.Rev.E,2005,71:036140.
[41]Noh J D,Rieger H.Random Walks on Complex Networks.Phys.Rev.Lett,2004,92:118701;
[42]Evans T S,Saramaki J P.Scale-free networks from self-organization.Phys.Rev.E,2005,72:026138.
[43]Liu Z H,Lai Y C,Ye N,Dasgupta P.Connectivity distribution and attack tolerance of general networks with both preferential and random attachments.Physics Letters A,2002,303:337-344.
[44]Barabasi A L,Ravasz E,Vicsek T.Deterministic scale-free networks.Physic A,2001,299:559-564.
[45]Ravasz E,Barabasi A L.Hierarchical organization in complex networks.Phys.Rev.E,2003,67:026112.
[46]Dorogovtsev S N,Goltsev A V.Mendes J F F.Pseudofractral scale-free web.Phys.Rev.E,2002,65:066122.
[47]Bollobas B.Random Graphs.2nd ed.New York:Academic Press,2001:1-80
[48]史定华.随机模型的密度演化方法.第一版.北京:科学出版社,1999:1-100
[49]何声武.随机过程引论.北京:高等教育出版社,1999:1-95.
[50]钱敏平.龚光鲁.应用随机过程.北京:北京大学出版社,1998:1-97
[51]陈希孺.数理统计引论.北京:科学出版社,1999:23-80.
[52]茆诗松,王静龙等.高等数理统计.北京:高等教育出版社,1998:1-90
[2]Watts D J,Strogatz S H.Collective dynamics of small-world networks.Nature,1998,393:440.
[3]M.E.J.Newman,Models of small world(A Review).cond-mat/0001118v2,2000 May 9.
[4]A L,Barabasi,Albert R.Emergence of scaling in random networks.Science,1999,286:509-512.
[5]Barabasi A L,Albert R,Jeong H.Mean-field theory for scale-free random networks.Physica A,1999,272:173-187.
[6]Barabasi A L,Albert R.Topology of evolving networks:local events and universality.Physical Rev Lett,1999,85:5234-5237.
[7]R.Albert,A.-L.Barabasi.Statistical mechanics of complex networks.Rev.Mod.Phys,2002,74:47-97.
[8]R.Albert,A.-L.Barabasi,E.Bonabau.Scale free networks.Scientific American,2003May:50-59.
[9]M.E.J.Newman.The structure and function of complex networks.SIAM REVIEW (Society for Industrial and Applied Mathematics),2003,45:167-256.
[10]Dorogovtsev S N,Mendes J F F,Samukhin A N.Structure of growing networks with preferential linking.Phys.Rev.Lett.,2000,85(21):4633-4636.
[11]Krapivsky P L,Redner S,Leyvraz F.Connectivity of Growing Random Networks.Phys.Rev.Lett.,2000,85:4629-4632.
[12]Dorogovtsev S N,Mendes J F F.Evolution of networks.Advances in physics,2001,90:123-143
[13]S.H.Yook,A.-L.Barabasi.Weighted Evolving Networks.Phys.Rev.Lett.,2001,86:5835-5838
[14]T.Antal,P.L.Krapivsky.Weight-driven growing networks.P.R.E,2005,71:026103.
[15]Barrat A,Barthelemy,Vespignani A.Modeling the evolution of weighted networks.Phys.R.E,2004,70:066149.
[16]Wang W X,Wang B H,Hu B,Yan G,Ou Q.General Dynamics of Topology and Traffic on Weighted Technological Networks.Phys.Rev.Lett.,2005,94:188702.
[17]Barrat A,Barthelemy M,Pastor-Satorras,Vespignani A.The architecture of complex weighted networks.PNAS,2004,70:3747-3752
[18]S H Chen(陈盛辉),Q H Chen(陈庆华).A Weighted Network Model Based on the Preferential Selection of Edges.Applied Mathematical Sciences,2007,Vol.1:1145-1156.
[19]徐道炜,陈庆华.一个非匹配的加权网络.莆田学院学报,2007,Vol.14,No2
[20]Tomer Kalisky,Sameet Sreenivasan,Lidia A.Braunstein,Sergey V.Buldyrev.Scalefree networks emerging from weighted random graphs.Phys.Rev.E,2006,025103:1-4.
[21]陈盛辉.具有高集群的加权无标度网络建模分析(福建师范大学硕士学位论文),2007.4.
[22]徐道炜.无标度网络拓扑和动力学研究(福建师范大学硕士学位论文),2007.4.
[23]G.Caldarelli,A.Capocci,P.De Los Rios,A.Munoz.Scale-Free Networks from Varying Intrinsic Fitness.Phys.Rev.Letters,2002,258702:1-4.
[24]Krapivsky P L,Redner S.Organization of growing random networks.Phys.Rev.E,2001,066123:63.
[25]陈庆华.无标度网络的相关性和联合度分布.福建师范大学学报(自然科学版),2006,22(1):1-6.
[26]Brrat A,Barthelemy M,Pastor-satorras R,Vespignani A.The architecture of complex weighted networks.Proc.Natl.Acad.Sci.U.S.A.,2004,101:3747-3752.
[27]Li xiang,Chert G R.A local-world evolving network model.Physic A,2003,328:274-286.
[28]Saram(a|¨)ki J,Kaski K.Scale-free networks generated by random walkers.Physic A,2004,341:80-86.
[29]Li C G,Chen G R.Network connection strengths:Another power-law?.condmat,2003,:0311333.
[30]Garlaschelli D,Battiston S,Castri M,Servedio V D P,Caldarelli G.The scale-free topology of market investments.cond-mat,2003,:0310503.
[31]Yook S H,Jeong H,Barabasi A L,Tu Y.Weighted evolving networks.Phys.Rev.Lett.,2001,86:5835-5838.
[32]Barabasi A L,Albert R,Jeong H.Me,n-field theory for scale-free random networks.Physic A,1999,272:173-187.
[33]Zheng D,Trimper S,Zheng B,Hui P M.Weighted scale-free networks with stochastic weight assignments.Phys.Rev.E,2003,67:040102.
[34]Bianconi G,Barsbasi A L.Competition and multiscaling in evolving networks.Europhys.Lett.,2001,54:436-442.
[35]Barrat A,Barthelemy M,Vespignani A.Weighted Evolving Networks:Coupling Topology and Weight Dynamics.Phys.Rev.Lett,2004,92:228701.
[36]Barrat A,Barthelemy M,Vespignani A.Modeling the evolution of weighted networks.Phys.Rev.E,2004,70:066149.
[37]Wang W X,Wang B H,Hu B,Yan G,Ou Q.General Dynamics of Topology and Traffic on Weighted Technological Networks.Phys.Rev.Lett,2005,94:188702.
[38]Wang W X,Hu B,Zhou T,Wang B H,Xie Y B.Mutual selection model for weighted networks.Phys.Rev.E,2005,72:046140.
[39]Chen Q H,Shi D H.Markov chains theory for scale-free networks.Physic A,2006,360:121-133.
[40]Shi D H,Chen Q H,Liu L.Markov chain-based numerical method for degree distributions of growing networks.Phys.Rev.E,2005,71:036140.
[41]Noh J D,Rieger H.Random Walks on Complex Networks.Phys.Rev.Lett,2004,92:118701;
[42]Evans T S,Saramaki J P.Scale-free networks from self-organization.Phys.Rev.E,2005,72:026138.
[43]Liu Z H,Lai Y C,Ye N,Dasgupta P.Connectivity distribution and attack tolerance of general networks with both preferential and random attachments.Physics Letters A,2002,303:337-344.
[44]Barabasi A L,Ravasz E,Vicsek T.Deterministic scale-free networks.Physic A,2001,299:559-564.
[45]Ravasz E,Barabasi A L.Hierarchical organization in complex networks.Phys.Rev.E,2003,67:026112.
[46]Dorogovtsev S N,Goltsev A V.Mendes J F F.Pseudofractral scale-free web.Phys.Rev.E,2002,65:066122.
[47]Bollobas B.Random Graphs.2nd ed.New York:Academic Press,2001:1-80
[48]史定华.随机模型的密度演化方法.第一版.北京:科学出版社,1999:1-100
[49]何声武.随机过程引论.北京:高等教育出版社,1999:1-95.
[50]钱敏平.龚光鲁.应用随机过程.北京:北京大学出版社,1998:1-97
[51]陈希孺.数理统计引论.北京:科学出版社,1999:23-80.
[52]茆诗松,王静龙等.高等数理统计.北京:高等教育出版社,1998:1-90