论文部分内容阅读
摘 要:复杂网络的研究已成为当今世界的核心科学问题之一,而现实世界中很多网络都是各个连接间具有不同权值的加权网络,采取一定的方法研究网络的静态统计特性、网络上的动力学特性和网络演化模型等方面的内容对现实的指导意义颇大。本文对加权复杂网络的研究现状及研究方法进行了分析。
关键词:加权网络 权重 赋权方式
中图分类号:TP391 文献标识码:A 文章编号:1672-3791(2013)05(b)-0013-01
近年来,越来越多的学者对复杂网络产生了兴趣,来自各个不同领域的研究者正对复杂网络的发展进行着密切的研究,复杂网络以及加权复杂网络的各种性质正逐渐被揭示出来。构建一种能较好模拟现实网络的复杂网络模型是每一个研究者的目标。
复杂网络经历了规则网络、随机网络、小世界网络和无标度网络几个阶段。在现有文献中大多数的研究都是针对无权网络的,但现实世界中很多网络都是各个连接间具有不同权值的加权网络,例如航空网、科学家合作网等就是典型的加权网络。加权网络能够对实际复杂网络的动力学演化特性提供更加真实、细致和全面的描述。因此,对加权网络研究的重要意义是显而易见的。
1 研究现状
复杂网络就是由节点和连线画出的一种网络。在考虑实际网络的时候,我们通常关心的是节点之间是否有边相连,而不考虑不同节点间连接的紧密程度—即边的权值。事实上,许多网络的节点间相互关系的强度是不同的,仅知道边的有无还不足以准确反映个体之间的关系和差异,此时就不能再将系统抽象成无权网络了,必须引入一个新的维度来描述和区分边与边之间的这种差异性。权重将提供更加细致的刻画,加权网络的研究就在这种要求下诞生了。事实证明复杂加权网络能够更贴切地描述实际复杂系统,提供了人们深入探索实际复杂系统特性和复杂行为的一个数学工具,也拓展了复杂网络在实际中的应用。
实际的许多系统都可抽象为加权网络,例如人际交往网络,对于传染病的传播,有无接触虽然起着决定作用,但频繁接触者和偶尔接触者被感染的几率应该不同。在科学家合作网中,任意两个科学家之间的合作次数是不同的,合作一次与合作十次对信息传播的贡献显然不一样,应用不同的边来表现两个人合作的亲密程度和思想传播的难易程度,此时就需要根据实际情况给每条边赋予权重才能反映出现实网络的特点。因此研究网络的权值问题是有必要并且是有意义的。
目前对加权网络的研究主要集中在网络静态统计特性、网络上的动力学特性和网络演化模型等几个方面。对于加权网络统计特性研究:除要研究拓扑结构之外,还需要分析在拓扑结构上的权值分布情况,以及引入权重以后网络几何量的重新定义和实证分析等方面工作。研究结果表明:在许多实际加权网络中,除了幂律度分布、平均最短距离小、聚类系数高这些无权网络所具有的基本特点外,点权和边权也遵从幂律分布。
对于加权网络上动力学特性的研究:加权网络将不同的边赋予了权值,必然会影响各种物理量如信息、流量等在网络上的动力学特性。Brau nstein等[1]引入了随机权值,研究了这种加权网络中权重随机性强弱对最优路径的影响。Crucitti等[2]基于网络上流量简单再分配过程,研究了加权网络关于一系列点(或边)瘫痪与失效的模型,指出负载量最大的节点受到攻击将会最大程度地降低网络的有效性,甚至使系统瘫痪,这对于具有负载广泛分布的Internet网和电力网等实际网络预防攻击是有重要意义的。
对于加权网络的建模研究:在加权网络中,模型的建立以及运用必须充分考虑各个网络节点和通路由于不同的实际权值所造成的网络总体统计特性的极大差异。最近,Zheng等[3]研究了随机分配权重的加权网络模型;Gao和Zhao等[4]首次提出了网络形成的机制源于系统的阶段平衡,这种平衡是确保新加入节点不能再通过改变自身的选择而获得更大的效用。
2 研究方法
(1)建立复杂网络模型。自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。比如人际关系网络:以人为节点,以“认识”为连线,全中国某一天的人口就组成一个复杂网络。在交通系统中,以地点表示节点,以公路、铁路或航线表示边而建立起来的公路网络、铁路网络和航空网络等等。这些关系网都可以用一个复杂网络的数学模型来表示。
(2)复杂网络的权值研究。采取一定方式给网络的边赋权值,计算并分析点权的分布规律。通常采取以下三种方式给网络的边赋权重:①常数权重:网络中每条边的权重均为常数构建的加权网络。②服从指数分布的边权重:假设边的权重服从指数分布,即,其参数为>0。③服从节点度乘积分布的边权重:设节点i与节点j的度分别为和,则连接这2个节点的边权重定义为:,其中可有效地调节节点强度大小。(3)加权网络的稳定性分析。可以采用选择性攻击和随机性打击的方法考察加权网络的容错能力和抗攻击能力,讨论网络的静态统计特征量的变化及特点。(4)实际应用。以现实世界的各个网络为例抽象出相应的加权复杂网络模型,并对其统计特性及动力学特性进行研究,得出相应分布规律,以指导实际。例如,公交站点网络,通过模型的建立及静态统计特征量的分析,可以给出缓解交通压力的方案,以指导实际。
3 结语
现实世界中的大多数网络都是加权网络,所以越来越多的人加入到加权复杂网络的研究队伍,研究其几何性质、形成机制、网络演化的统计规律、网络模型的性质以及网络的结构稳定性,并把它与真实系统结合起来。但由于目前对小世界网和无标度网相关的工作还相当有限,并且复杂加权网络已展示出比拓扑网络更广泛的统计特性,所以对于复杂加权网络的研究尚处于早期阶段,还有许多问题有待解决,许多方面要加强探索,许多相关课题值得进一步研究。
参考文献
[1] Braunstein L.A.Buldyrev S.V.Cohen R.et al.Optimal paths in disordered complex networks.Phys.Rev.Lett. 2003,91:168701.
[2] Crucitti P.Latora V.Marchiori M.. Model for cascading failures in complex networks.Phys.Rev.E,2004,69(4):045104.
[3] Zheng D.Trimper S.Zheng B.et al. Weighted scale-free networks with stochastic weight assignments.Phys. Rev.E,2003,67:040102.
[4] 高自友,赵小梅,黄海军,等.复杂网络理论与城市交通系统复杂性问题的相关研究[J].交通运输系统工程和信息,2006,6(3):41-47.
关键词:加权网络 权重 赋权方式
中图分类号:TP391 文献标识码:A 文章编号:1672-3791(2013)05(b)-0013-01
近年来,越来越多的学者对复杂网络产生了兴趣,来自各个不同领域的研究者正对复杂网络的发展进行着密切的研究,复杂网络以及加权复杂网络的各种性质正逐渐被揭示出来。构建一种能较好模拟现实网络的复杂网络模型是每一个研究者的目标。
复杂网络经历了规则网络、随机网络、小世界网络和无标度网络几个阶段。在现有文献中大多数的研究都是针对无权网络的,但现实世界中很多网络都是各个连接间具有不同权值的加权网络,例如航空网、科学家合作网等就是典型的加权网络。加权网络能够对实际复杂网络的动力学演化特性提供更加真实、细致和全面的描述。因此,对加权网络研究的重要意义是显而易见的。
1 研究现状
复杂网络就是由节点和连线画出的一种网络。在考虑实际网络的时候,我们通常关心的是节点之间是否有边相连,而不考虑不同节点间连接的紧密程度—即边的权值。事实上,许多网络的节点间相互关系的强度是不同的,仅知道边的有无还不足以准确反映个体之间的关系和差异,此时就不能再将系统抽象成无权网络了,必须引入一个新的维度来描述和区分边与边之间的这种差异性。权重将提供更加细致的刻画,加权网络的研究就在这种要求下诞生了。事实证明复杂加权网络能够更贴切地描述实际复杂系统,提供了人们深入探索实际复杂系统特性和复杂行为的一个数学工具,也拓展了复杂网络在实际中的应用。
实际的许多系统都可抽象为加权网络,例如人际交往网络,对于传染病的传播,有无接触虽然起着决定作用,但频繁接触者和偶尔接触者被感染的几率应该不同。在科学家合作网中,任意两个科学家之间的合作次数是不同的,合作一次与合作十次对信息传播的贡献显然不一样,应用不同的边来表现两个人合作的亲密程度和思想传播的难易程度,此时就需要根据实际情况给每条边赋予权重才能反映出现实网络的特点。因此研究网络的权值问题是有必要并且是有意义的。
目前对加权网络的研究主要集中在网络静态统计特性、网络上的动力学特性和网络演化模型等几个方面。对于加权网络统计特性研究:除要研究拓扑结构之外,还需要分析在拓扑结构上的权值分布情况,以及引入权重以后网络几何量的重新定义和实证分析等方面工作。研究结果表明:在许多实际加权网络中,除了幂律度分布、平均最短距离小、聚类系数高这些无权网络所具有的基本特点外,点权和边权也遵从幂律分布。
对于加权网络上动力学特性的研究:加权网络将不同的边赋予了权值,必然会影响各种物理量如信息、流量等在网络上的动力学特性。Brau nstein等[1]引入了随机权值,研究了这种加权网络中权重随机性强弱对最优路径的影响。Crucitti等[2]基于网络上流量简单再分配过程,研究了加权网络关于一系列点(或边)瘫痪与失效的模型,指出负载量最大的节点受到攻击将会最大程度地降低网络的有效性,甚至使系统瘫痪,这对于具有负载广泛分布的Internet网和电力网等实际网络预防攻击是有重要意义的。
对于加权网络的建模研究:在加权网络中,模型的建立以及运用必须充分考虑各个网络节点和通路由于不同的实际权值所造成的网络总体统计特性的极大差异。最近,Zheng等[3]研究了随机分配权重的加权网络模型;Gao和Zhao等[4]首次提出了网络形成的机制源于系统的阶段平衡,这种平衡是确保新加入节点不能再通过改变自身的选择而获得更大的效用。
2 研究方法
(1)建立复杂网络模型。自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。比如人际关系网络:以人为节点,以“认识”为连线,全中国某一天的人口就组成一个复杂网络。在交通系统中,以地点表示节点,以公路、铁路或航线表示边而建立起来的公路网络、铁路网络和航空网络等等。这些关系网都可以用一个复杂网络的数学模型来表示。
(2)复杂网络的权值研究。采取一定方式给网络的边赋权值,计算并分析点权的分布规律。通常采取以下三种方式给网络的边赋权重:①常数权重:网络中每条边的权重均为常数构建的加权网络。②服从指数分布的边权重:假设边的权重服从指数分布,即,其参数为>0。③服从节点度乘积分布的边权重:设节点i与节点j的度分别为和,则连接这2个节点的边权重定义为:,其中可有效地调节节点强度大小。(3)加权网络的稳定性分析。可以采用选择性攻击和随机性打击的方法考察加权网络的容错能力和抗攻击能力,讨论网络的静态统计特征量的变化及特点。(4)实际应用。以现实世界的各个网络为例抽象出相应的加权复杂网络模型,并对其统计特性及动力学特性进行研究,得出相应分布规律,以指导实际。例如,公交站点网络,通过模型的建立及静态统计特征量的分析,可以给出缓解交通压力的方案,以指导实际。
3 结语
现实世界中的大多数网络都是加权网络,所以越来越多的人加入到加权复杂网络的研究队伍,研究其几何性质、形成机制、网络演化的统计规律、网络模型的性质以及网络的结构稳定性,并把它与真实系统结合起来。但由于目前对小世界网和无标度网相关的工作还相当有限,并且复杂加权网络已展示出比拓扑网络更广泛的统计特性,所以对于复杂加权网络的研究尚处于早期阶段,还有许多问题有待解决,许多方面要加强探索,许多相关课题值得进一步研究。
参考文献
[1] Braunstein L.A.Buldyrev S.V.Cohen R.et al.Optimal paths in disordered complex networks.Phys.Rev.Lett. 2003,91:168701.
[2] Crucitti P.Latora V.Marchiori M.. Model for cascading failures in complex networks.Phys.Rev.E,2004,69(4):045104.
[3] Zheng D.Trimper S.Zheng B.et al. Weighted scale-free networks with stochastic weight assignments.Phys. Rev.E,2003,67:040102.
[4] 高自友,赵小梅,黄海军,等.复杂网络理论与城市交通系统复杂性问题的相关研究[J].交通运输系统工程和信息,2006,6(3):41-47.