复杂网络（精选十篇）
复杂网络 篇1
早在20世纪90年代初, 钱学森先生就提出了“开放的复杂巨系统理论”。随着对复杂性科学重要意义认识的不断加深, 复杂性科学在国内也受到了普遍的重视。受到广泛研究的网络包括互联网、万维网、铁路网、航空网、电力网、生物网、蛋白质相互作用网、新陈代谢网、基因调控网和各种合作性的网络等。研究这些网络不仅有助于我们了解自然界的各种现象, 并且对人们的生产生活具有指导意义[1-5]。
自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由大量节点和连接节点的连边组成, 其中节点代表真实系统中不同的个体, 而边则表示个体间的关系, 当两个节点之间具有某种特定的关系时, 则连一条边, 反之则不连边。有边相连的两个节点在网络中被看作是相邻的。现实世界中很多系统都可以用复杂网络模型来表示。例如, Internet是由路由器和传输介质组成的复杂网络;人脑是由神经元通过互连形成的复杂网络;而社会则是人与人通过各种各样的关系联系起来的。复杂网络的广泛存在, 使得大量科学家致力于复杂网络的拓扑特性和动力学特性的研究。关于复杂网络的系统研究应该归功于数据采集能力的提高和高性能计算工具的出现, 在此基础上, 各种实际网络复杂的拓扑结构被揭示出来。要对复杂网络进行研究, 首先要为其建立合适的数学模型, 这是进一步研究复杂网络的重要条件。目前已发现的比较有名的数学模型主要有:Erdos-Renyi (ER) 随机网络模型[6], Strogatz-Watts (SW) 小世界网络模型[7]和Barabasi-Albert (BA) 无标度网络模型[8]。
上个世纪50年代末60年代初, 两位匈牙利数学家Erdos和Renyi提出了随机图理论, 建立了ER模型, 用随机图来描述网络的拓扑结构, 为复杂网络理论的研究奠定了数学理论基础, 是复杂网络研究中的一个重要突破。
1998年, Watts和Strogatz提出了WS小世界模型的生成算法, 这种网络具有较高的聚集系数和较小的最短路径, 即呈现出小世界的特性 (六度分离理论) 、, 而且度分布遵从泊松分布。
而大量的对现实复杂网络的统计结果表明, 实际复杂网络的度分布服从Power Law分布。为了解释这种幂律分布, Barabasi和Albert在1999年提出了Scale-Free网络模型, 即BA无标度网络模型。
自从WS小世界网络模型和BA无标度网络模型的开创性工作发表以来, 在科学与工程各个领域掀起了关于复杂网络研究的热潮。
除了对网络进行建模以外, 复杂网络上的动力学行为及动态事件成为了复杂网络研究的一个新热点。其中, 实际网络上发生的一些危害性事件已经越来越引起人们的重视。这些事件包括电力网上的大停电, Internet上的信息拥塞, 计算机网络上的病毒传播等。利用复杂网络理论对这些事件进行研究, 有利于控制这些危害网络安全事件的发生。
研究复杂网络的主要目标就是理解复杂网络上的动力学行为, 特别是理解网络拓扑结构对其动力学的影响。比如, 网络的拓扑结构对病毒传播的快慢以及最终传播范围的影响;数据包的传输路径对其传输效率的影响;复杂网络中的随机行走问题;高压输电网络结构对因级联故障而导致的大停电事故的影响;藕荷振子之间的连接模式对于整体同步能力的影响以及人际关系网络对于相应市场行为及博弈关系的影响等。
复杂网络的研究不仅具有学术意义, 而且具有重大的实际意义。复杂网络的研究可以使人们更好的了解现实世界的复杂系统, 为设计具有良好性能的网络提供理论依据, 同时复杂网络的理论成果将会广泛地应用到生物、计算机、交通等各个领域。
摘要：自然界中存在的大量复杂系统均可表示成网络的形式。近几年兴起研究的复杂网络, 真实地反映出现实世界中复杂系统的某些重要拓扑和统计特性, 成为研究现实网络的有效手段。随着大型数据库的出现和计算能力的提高, 人们发现, 许多不同的真实网络具有一些相同的特性, 如小世界效应、无标度特性、度相关性等。这些发现掀起了复杂网络研究的热潮。
关键词：复杂网络,小世界
参考文献
[1]D.J.Watts.Small Words:The dynamic of Networks between Order and Randomness[M].Princeton:Princeton University Press, 1999.
[2]D.J.Watts.Six Degree:The Science of a Connected Age[M].New York:Norton, 2003.
[3]A.-L.Barabasi.Linked:The New Science of Networks[M].Cambridge:Perseus, 2002.
[4]M.Buchannan, Nexus:Small Worlds and the Ground Breaking Science of Networks.New York:Norton, 2002.
[5]S.H.Strongatz, SYNC:The Emerging Science of Spontaneous Order[M].New York:Hyperion, 2003.
复杂网络数据挖掘论文 篇2
1、复杂网络数据流密度分析
对于一个多种网络形式并存的复杂网络，假设复杂网络作为一个网络社区，在复杂网络中存在的网络类型数即社区数。我们用一个无向遍历图GV,E来表示整个网络社区，如果网络中有两个节点有两条不重合的网络路径，则说明这两个节点处于一个网络环路当中，网络中的数据流需要经过网络环路到达特定的节点。当在某个时间段里需要传送的数据流个数大于网络节点数时，则说明该网络的数据流密度较大，为了能够准确地在复杂网络中挖掘出所需的数据流，则需要根据数据流密度来划分整个网络社区，寻找数据流处于哪个社区，再确定数据流所在社区的环路。在这里我们通过设计算法确定网络数据流密度，来对复杂网络进行社区划分，再对社区进行无向环路遍历，并通过遍历得到该社区网络的所环路，确定所需查询的数据流位于哪个环路。以下为复杂网络中需要用到的符号说明。
2、增量子空间数据挖掘算法
为了能够有效地在复杂网络中挖掘出目的数据流，使用了复杂网络数据流密度的分析方法在对复杂网络进行社区划分后，通过对社区网络进行无向环路遍历并得到社区网络的所有环路。接下来挖掘算法先后挖掘出目的数据流所属的社区以及环路，最终确定目的数据流的具体位置。
2.1基于社区网络遍历的数据流挖掘
当数据流i与社区k的相关度最大时，说明数据流i位于社区k的可能性就最大。但是当多个数据流的大小区别不大时，以数据流的大小作为指标来定义相关度会导致挖掘精度较低。这里我们也引入数据流的.特征集和数据流中的分组队列长度来计算相关度。
2.2基于多增量空间的数据流挖掘
在采用基于社区网络遍历的数据流挖掘方法得到数据流的所属社区后，我们接着采用基于多增量空间的数据流挖掘方法来挖掘出数据流的所属环路。先将社区网络的环路进行多增量空间扩展，即先得到
目标数据流所经过的环路，再得到数据流所经过的节点与时间的相关系数，这样就可以在时空上确定目的数据流位于环路的哪个节点中。
3、实验结果
为了验证本文提出的基于复杂网络数据流密度的增量子空间数据挖掘算法的效果，我们通过matlab7.0软件进行算法仿真，其中仿真的复杂网络由多种网络形式组成，网络节点有200个，数据流大小为500bytes，节点的接收能耗为10nJ/bit，发射能耗为50nJ/bit，进行信号处理和功率放大的能耗为10nJ/bit。其他节点干扰而产生的能量消耗为5nJ/bit。在对本文算法进行分析的过程中，我们采用了对比分析的方法，Lopez-Yanez等人提出一种基于时间序列数据挖掘的新的关联模型，该模型是基于伽玛分类，是一种监督模式识别模型，目的是为了挖掘已知模式中的时间序列，以预测未知的值。由Negrevergne等人提出的一种PARAMINER算法：一个通用的模式挖掘算法的多核架构。多核架构采用的是一种新的数据集缩减技术（称之为EL-还原），在算法中通过结合新的技术用于处理多核心架构的并行执行数据集。为了验证本文算法的挖掘有效性，我们分别在增多节点数量和社区网络数的情况下获取算法的数据挖掘精度。实验采用的精度为NMI[16]，实验结果如图3和图4所示。在不同节点数量下基于复杂网络数据流密度的增量子空间数据挖掘算法的挖掘精度更高，挖掘精度高于85%，而文献[14]的挖掘精度在77%以上，挖掘精度在76%以上。因为、提出的关联模型、提出的多核架构没有准确把握数据流在不同时间段里与环路位置的相关情况。而本文算法采用社区网络遍历和多增量空间的方法可以有效地确定这种相关性。图4为不同社区数下的算法挖掘精度，从图中可以看出，当社区网络的种类增多时，会对算法的挖掘精度造成影响，本文算法的挖掘精度在社区数为10时是95.7%，当社区数增加到50时为87.5%。而基于时间序列数据挖掘方法的挖掘精度在社区数为10时是88.6%，在社区数为50时是77.4%，而PARAMINER算法在社区数为10时是86.7%，社区数为50时是78.2%。因此从数据分析来看，本文算法的数据挖掘精度在社区数增多时仍能保持在较高水平。
4、结论
透视复杂网络的规律 篇3
其中最著名的，是他在1999年提出的“无尺度网络”（scale-free network）的概念，这一概念很好地解释了社交网络的快速兴起。过去，网络一直被认为是随机分布的，无尺度网络理论则指出，在现实中，总有一类人特别擅长交往，他们认识很多人，成为许多圈子的中心节点。实际上，这种“幂律分布”的特征也符合二八定律：正是这些擅长交往的20%的人，携带了80%的连接，使得小小世界中的六度分隔成为可能：任何人只要通过自己所有的朋友，以及朋友的朋友，经过六次连接，就可以通达地球上所有的人，甚至奥巴马。
无尺度网络概念的提出，对防备黑客攻击、防治流行病乃至云计算的资源配置等都有深刻的启示。巴拉巴西甚至联合两位经济学家将其理论应用到国际贸易、产业升级中去，解释穷国为什么会穷的问题：根据对进出口产品空间网络结构的研究，富国拥有规模更大且更为多元化的经济体，并生产许多种产品——尤其是那些与网络中心紧密相连的产品；而穷国往往生产一些相互间无较大相似性的产品，在网络中处于边缘的地位。这一前沿视角可以广泛应用到创新产品的扩散、产业集群的建设、地区竞争力的提升等政策中。
在自己的新书《爆发》中，巴拉巴西试图论证，幂律不仅是网络在空间上分布的规律，也是在时间上展开的规律，是主宰着我们的真实活动的节奏。这背后的秘密就是人们做事时遵从的优先级法则。“时间是我们最宝贵的不可再生资源，如果我们尊重它，就必须设定优先级。一旦优先级设定了，幂律规律和爆发的出现就不可避免。”随着数字化、高度互联的发展以及大数据时代的到来，对于幂律的认知最终会导致对人类行为的精准预测。
“无尺度网络”的魅力
记者：“无尺度网络”的概念可以很好地解释社交网络的快速兴起，您如何看社交网络未来的发展？
巴拉巴西：无尺度网络一个有趣的特征就是它的历时稳定性。在人的一生中，你的朋友可能会越来越多，而且可能有的人朋友更多一些，有的人更少一些，但是这不会影响到总体的分布情况。你的朋友增多了以后，会有其他的人来填补你的位置。
在过去10年左右的时间里，我们已经在各种真实的系统中见证到无尺度网络的存在。在1999年我提出这个概念的时候，还主要针对万维网上的情况；现在Facebook、Twitter等社交网络的发展也印证了无尺度网络的概念。而且随着数据的增多，我们现在可以进行准确地测量和预测，这个概念将更加得到用武之地。
记者：您曾经在《科学》杂志上发表文章，用无尺度网络的理论来分析国家贫富的问题。您如何看中国经济在全球的位置？
巴拉巴西：在一篇文章中，我们对产品网络和经济发展的关系做了研究，发现如果一国生产的产品种类很少，它们往往在经济上就会非常落后。成功的经济来自于多种能力的组合，用这些能力创造出多样的产品组合。你所具备的能力越少，经济增长的潜力就越小。试想，即使对于生产和出口香蕉这样简单的工作来说，你也需要有土地、气候、农业技术、采购、物流、外贸等多方面的能力。而对于iPad这样的产品来说，所需要的部件、知识、技术就更要多得多了。
在接下来的10～15年时间里，中国处在一个独特的位置上，经济还会飞速发展，市场会更加多样化。面向不同的市场，中国可以做不同的混搭。
预测人类行为
记者：能否分享一下从您《链接》到《爆发》这两本书的思想发展脉络？
巴拉巴西： 《链接》是谈网络的，讲到人们之间是怎么样连接在一起的，社会网络、生物网络、技术网络是如何分布的，以及是如何随着时间而演进变化的。这本书唯一没有涉及的一个方面是，网络节点之间的互动是如何发生的。所以，在完成《链接》的写作之后，我研究工作的重心就开始转向对互动规律的研究，并且把研究的重点集中在社会系统上，因为社会系统的相关数据最容易获得。这一研究的主要发现，就写进《爆发》这本书里了。
记者：《爆发》探讨的是人类行为预测的课题。其实反观我们自身的大脑，它正是每时每刻都在从身体各处接收大量的信息，同时做出决策。大数据和预测可否从大脑的工作机理中获得一些启发？
巴拉巴西：我明白你的问题。答案是肯定的，如果我们有相应的工具的话，我们的确可以从大脑的工作机理中获得启发。
其中的难题在于，我们迄今还没有搞清楚大脑网络到底是什么样子。尽管大家都把人类的大脑视为一个神经网络，但是我们却一直没有这个网络的地图。每个人大脑的“布线”（wiring）都是不同的，学习、教育等等都会改变我们的布线。
迄今为止，还没有相应的工具来帮助我们描绘出人类大脑的地图。所以，回到你的问题，我们现在还无法确切地知道大脑是如何处理那些海量信息的。
记者：您在书中否定了卡尔·波普尔《历史决定论的贫困》的观点，即社会发展是无规律、不可预测的。但是您似乎没有充分展开，能否在这里集中阐述一下，波普尔的观点为什么是错误的？
巴拉巴西：卡尔·波普尔在上世纪60年代发表了一篇有趣的哲学论文，分析了社会科学之为科学的问题。此前有观点认为，科学研究领域都应该是可以进行量化研究的，并且进而最终应该有对未来进行预测的能力。但是，社会科学还不具备对未来进行预测的能力，那时的社会科学正如一些人认为的那样，基本上都是描述性的。这时卡尔·波普尔站出来为社会科学辩护说，人们不应该期望社会科学具备对未来进行预测的能力，因为人类行为本身是不可预测的。
nlc202309021003
我认为，波普尔的这个结论在当时可能是合乎逻辑的，但应当主要是意识形态性质的，因为他是在努力为社会科学的科学之为科学辩护。而今天，随着大数据和一系列数学工具的出现，整个情形已经得到根本改观。现在我们可以断言，人类行为的许多方面是可以预测的。因此，许多人会同意，在几十年以后，社会科学会变成具有预测能力的科学。
记者：可否为我们分享几个最新的利用大数据做出成功预测的案例？
巴拉巴西：在商业领域，基于网络的预测能力正在提升。这是因为“10年+10年”循环规律的效应正在显现出来。这个规律是说，一个新发现出现之后，首先需要大约10年的时间来认识它；在第二个10年，我们才开始看到它的应用以及相应的成果。对于网络理论来说，它已经度过第一个10年的周期，开始进入普及应用阶段。有很多大公司在利用网络理论做预测。
有一家匈牙利公司做的事情很有趣，它们把组织内部的沟通和互动做出图谱，帮助CEO做决策。这个图谱可以让CEO看到哪些人是组织里最有影响力的，哪些人是掌握知识最多的，哪些人是掌握最多资源的，等等。这个事情很重要，因为我们虽然在CEO身上投入了大量的金钱，但是却一直没有给他们多少真正有效的工具来帮助他们深入洞察组织的情况。有了这样的工具，CEO就可以实时了解组织的结构和变化因素，在必要时发起相应的文化变革。
需要提醒普通读者注意的是，这里的关键并不是要去利用这种能力来预测明天人们会去做什么事情，而是去获得和加深对组织或系统既有秩序和规律的理解。
C时代的变革驱动因素
记者：在您看来，在高度互联的C时代（the Connected Era），有哪些变革驱动因素尤其值得关注？
巴拉巴西：大家都已经看到互联网带来的巨大变革。但是，那只是C时代变革的一个层次，目前，无线通信是更大的一个驱动力量。互联网让我们可以从任何地点获得信息，而无线革命则在个人化上实现了突破。今天，无论我们做什么事情，都在某些数据库里留下来一些痕迹，从电子邮件到手机通话记录，正在积累起海量的关于人类行为的信息。这些数据当中包含着相当大的关于未来人类行为的可预测性，如果能够适当地加以利用，将会对企业、政府和社会带来变革。
记者：您下一步的写作计划是什么？
巴拉巴西：现在，我没在写面向普通读者的书。我正在写一本关于网络科学的教材，准备采用一种新的出版方式。每写完一章，就上传到我的网站上，人们可以免费阅读和下载，现在第一章已经在网站上了。等到所有章节都写完之后，我也会去找一家出版商再出一本书。同时，我也欢迎世界各地的读者以志愿者的身份把它翻译成不同语言的版本，目的就是以某种程度的免费方式把科学知识传播给每一个人。
复杂网络与网络化软件系统 篇4
随着Internet的发展以及计算机、Internet网络和自动控制技术在经济、社会和国防等领域的信息化应用,软件系统呈现出两个转变:软件运行平台从集中、封闭单机环境向开放、动态和多变网络环境转变;软件系统的功能向各种应用领域和为大众用户提供综合服务转变。这使得软件系统呈现出网络化的新特征,软件的规模和复杂性剧增。大规模软件系统的复杂性,使得开发者对系统的理解和控制越来越困难,软件质量、费用和生产率难以保证,软件开发就会经常处于失控状态,而传统的软件工程正接近其复杂性和可扩展性的极限。因此,复杂软件系统的软件工程日益成为研究热点,国内外研究者提出了一些新的软件开发理论、方法与技术,如:软件进化技术、软件构件技术、中间件、面向方面程序设计方法、基于角色的程序设计方法以及以软件体系结构为中心的网构软件开发方法等[1,2,3,4]。针对软件系统的复杂性问题,近年来一些研究者提出将复杂网络理论和软件工程相结合,利用网络拓扑特征改善大规模软件系统的质量,为软件工程研究开辟了一条新途径[7,8,9,10,11,12,13]。
本文主要简述复杂网络化软件系统呈现出的新特点,探讨复杂网络理论的最新研究成果在复杂网络化软件系统的建模、分析、设计和测试和维护中的应用。
1 网络化软件系统
网络化软件系统,是指人工构建的,用于对基于计算机网络的信息系统进行控制和管理,面向应用领域,向大众用户提供各种服务的大规模软件系统。
网络化软件系统是在Internet开放、动态和多变平台中软件系统基本形态的一种抽象。网络化软件作为一种新的软件形态,呈现出如下一些新的特点:
(1) 网络化软件基于Internet,具有自主、协同、反应、演化、安全和多态等特性[1]。
(2) 系统的规模和复杂度剧增,呈现出复杂系统的特性。
(3)网络化信息系统面向国民经济、社会生活和国防等各种应用领域;能够提供各种功能、以24小时365天形式服务于大众,由用户来主导,能适应用户各种动态需求。
为了适应这种网络化软件系统的新挑战,必须寻求建立与Internet开放、动态和多变环境相适应的新的软件工程理论、方法和技术体系,以构建面向应用领域、服务大众、高可信、高安全和自适应高柔性的大型网络化信息服务系统。
2 网络化软件系统与复杂网络
2.1 复杂网络[5,6]
网络模型是研究复杂系统的重要工具,20世纪60年代以来,随机网络理论一直是研究复杂系统的基本理论,同时大量应用统计物理学、非线性动力系统和复杂性科学的方法和工具,对网络的几何性质、形成机制、演化规律、结构稳定性和动力学等方面进行研究。20世纪末,科学家发现大量的、真实复杂系统的网络模型既不是规则网络,也不是随机网络,而是呈现出出乎意料的统计特征,如:具有大的聚集系数和小的平均距离的“小世界SW(Small-World effect)”效应,以及节点连接度分布服从幂律分布的“无标度SF(Scale-Free)”特征等。由于这样的网络是真实复杂系统的拓扑抽象,因此称为复杂网络(Complex networks)。对复杂网络的定量与定性特征的科学理解,已经成为网络时代科学研究中的一个极其重要的挑战性课题,甚至被称为“网络的新科学”。
目前的研究成果表明,复杂网络具有如下主要特征:
(1) 统计特征
它包括:
小世界现象,即网络节点对之间的平均距离较短,同时节点的集聚系数较大。
无标度特征,即网络节点的度服从幂律分布。网络中大多数节点的连接度很小,而少数节点的连接度很高。
(2) 动力学特征
基于对真实复杂网络系统的生成与演化的观察分析,无标度的BA模型设定了复杂系统的最重要且最普遍的两个生成机制:生长和择优连接。
(3) 社区结构特征
社区是网络中节点的集合,社区中的节点之间具有紧密的连接,而社区之间的则为松散的连接。复杂网络是由相对独立又相互交错、协作的社区组成。网络社区对网络健壮性和稳定性、在网络化数据上进行知识发现和数据挖掘,以及对复杂网络的化简等具有重要意义。
2.2 网络化软件系统具有复杂网络特征
大型复杂网络化软件系统是将复杂的问题分解为多个部分,再由多个开发者共同完成。在开发过程中,根据功能需要将复杂的功能分解为大量可重用的构件。若将这些构件视为节点,构件间的相互关系表示节点之间的边,就可以建立复杂软件系统的网络模型。采用逆向工程对已有的复杂软件系统的网络拓扑结构进行实证分析研究[7,8,9,10,11]表明:复杂软件系统的网络拓扑结构并不是随机的,而是具有小世界效应和无标度特性。
目前复杂网络化软件系统的开发主要采用基于构件软件技术和面向服务的体系结构,每个构件用面向对象的程序设计方法设计实现,更接近于客观世界,无标度特性更突出。构件的复用性使得软件系统的小世界效应突出。由于构件的自治性和异构性,构件之间具有层次化特征,构件以服务的形式交互,彼此的耦合更松散。
因此,复杂网络化软件系统不仅运行平台网络化,而且拓扑结构也具有复杂网络特征。
3 基于复杂网络的网络化软件工程
目前,国内外有关复杂网络的应用研究领域主要有:生命科学领域的各种网络、Internet、社会关系网等,但复杂软件系统网络的研究成果还相对较少。主要集中在对已有的复杂软件系统的复杂网络特征进行实证研究和统计分析[8,10,11]、对软件系统的度量[9,11]和测试[8]进行理论研究以及利用复杂网络理论对已有的网络化软件系统进行改进[12,13]。从复杂网络的角度,在更坚实的数学理论基础上,研究软件系统和软件工程,对网络时代复杂信息系统的软件工程具有重要理论和现实意义。复杂网络理论可应用于复杂软件系统的软件工程的下述几个方面。
3.1 软件建模
复杂网络的结构特征刻画了复杂系统的本质特征和普适共性,反映了经过进化形成的真实网络的优点。这些真实网络是由大量个体经过自发的相互作用,经过生长和择优的演化过程最终形成稳定的网络结构,这种结构经过了长时间的考验,可以认为是一种合理的组织形式。
复杂网络化软件系统作为人工设计和实现的复杂系统,完全可以借鉴和使用这种进化模式和网络结构,建立基于复杂网络拓扑结构的软件系统网络,以解决软件开发过程中的随意性而导致的各种不可预测问题。因此复杂网络理论和最新的研究成果,对于复杂网络化软件系统的建模具有重要参考价值。
3.2 软件设计
复杂网络理论也可应用于软件系统的设计过程。例如:
有效地利用复杂网络的信息动力学特性可改善信息传输网络结构设计,对预防控制网络上的信息拥塞、提高信息传输速率等具有重大的实际意义。
利用社区理论可优化网络化数据的知识发现和数据挖掘算法设计,提高速度和准确率。
3.3 软件测试
统计表明一个软件系统中,80%的软件缺陷常常存在于20%的软件空间里。因此,如何有效地确认和标识出这20%的空间,对软件测试是十分重要的。复杂软件系统中蕴涵着的无标度和小世界特征,可以帮助测试人员了解软件系统的构件之间的相互关系,在其特征规律的基础上分离出重要的构件或代码段,以制定测试的步骤和优先级,进而利用其组织关系进行有选择性的重点测试,可以适应复杂软件系统的规模,以较低成本、高效的方式对软件进行测试。
3.4 软件度量
软件度量是使软件设计与开发的科学性的重要保证,复杂软件系统的开发之所以经常处于失控状态的原因正是缺乏合理的度量。
利用网络化软件系统的复杂网络特征定量地刻画和分析软件系统的结构和行为,对于软件系统的复杂性度量具有如下作用:
(1) 节点间的平均距离、集聚系数和节点度的分布可以作为软件系统全局拓扑结构复杂性的度量标准。
(2) 软件构件交互的复杂性可以通过节点度分布度刻画,入度大的节点说明其复用度大,而出度大的节点则比较复杂。
(3) 用户的多样性、需求的持续变化、网络环境的动态演变、资源的自治性与不确定性及它们之间的相互作用、软件构件的目的性与自主性及其相互作用,必然导致网络化软件系统结构、行为、性能和质量的动态演变,最终驱动软件系统的发展和进化。利用复杂网络的动力学特征的生长和择优连接机制,可以刻画和度量软件系统的演化复杂性。
4 结 论
“结构决定功能”是系统科学的基本观点。目前,复杂网络是新兴学科交叉研究领域,利用复杂网络理论研究复杂网络化软件系统的工作也刚刚起步,需要从更深层次的理论高度以及理论与实际相结合的方向上推进,随着对网络化软件系统的复杂网络特性的认识不断深入,必将建立起一套基于复杂网络的软件工程新理论,以适应网络时代对大型复杂信息系统开发的需求。
摘要：复杂网络理论是对复杂系统的高度抽象,实证研究发现网络化复杂软件系统的拓扑结构具有复杂网络的特征。复杂网络理论的最新研究成果,为网络化复杂软件系统的开发提供了新的数学基础。提出一种基于复杂网络的网络化软件工程,探讨了复杂网络理论在网络化复杂软件系统的建模、测试和度量中的应用。
复杂系统布尔网络模型及应用 篇5
复杂系统布尔网络模型及应用
生命是一种自发的秩序,有其自身的调节机制.从布尔网络模型所表示的行为,探讨了生物的.稳定性、进化以及个体发生学中的一些问题,为解决生物界中的复杂性问题提供了新的思路.
作 者：李谋勋 LI Mouxun 作者单位：华南师范大学,广东,广州,510631刊 名：系统科学学报 PKU英文刊名：CHINESE JOURNAL OF SYSTEMS SCIENCE年，卷(期)：14(4)分类号：N941.4关键词：布尔网络 稳定性 进化 复杂性
我国网络安全形势日趋严峻复杂 篇6
“针对我国互联网基础设施和金融、证券、交通、能源、海关、税务、工业、科技等重点行业信息系统的探测、渗透和攻击逐渐增多，金融行业网站频频遭遇‘网络钓鱼’，成为不法分子骗取钱财和窃取隐私的重点目标。”高新民说。
中国互联网络信息中心此前发布的报告显示，2011年上半年，遭遇过病毒或木马攻击的网民为2.17亿人，占网民的44.7%。有过账号或密码被盗经历的网民达1.21亿人。有8%的网民最近半年内在网上遇到过消费
欺诈。
近期部分互联网站发生的用户信息泄露事件，也暴露出网站存在密码管理等安全措施上的严重缺陷。
在网上服务快速发展的今天，网上安全直接关系老百姓利益，更需要提高关注度，互联网管理规范亟待加强。
中国互联网协会表示，将通过加强密码保护和登录认证、强化系统安全防护和互联网企业内部管理等措施，进一步推动网站用户信息保护工作。
业内专家同时建议，国家尽早就个人信息保护问题进行立法、有关部门出台相关标准或指南对网站信息安全的技术建设进行规范、建立联动机制共同维护互联网络安全。
（来源：新华网）
复杂网络 篇7
网络可以用来描述从生物到社会的各类真实系统, 其中节点表示真实系统中不同的个体或组织, 而边则表示个体或组织之间的联系。近年来, 国际科学界对复杂网络理论与实证的研究做了大量的工作, 很多国际一流的刊物如Nature、Science等都陆续刊发了大量复杂网络的研究论文, 研究所涉及的网络有:科学家合作网络、交通网络、神经网络、新陈代谢网络等。但综观这些论文, 没有学者对产业结构进行分析和研究。
英国是世界经济强国之一, 其国内生产总值在西方国家中居前列。2002年, 英国经济规模居世界第四, 是世界第二大海外投资国, 同时是世界第四大贸易国。英国经济的发达与其产业结构有重要的关联。本文试图从复杂网络的角度对英国产业结构进行分析和研究。因此, 本文以英国产业结构为研究对象, 将产业结构抽象为由产业和产业间联系所组成的复杂网络, 把产业看作是网络中的节点, 将产业与产业之间的联系看作是网络中的边, 计算网络的统计特征, 分析其具有的复杂性, 希望为我国产业结构的发展和优化提供决策依据。
二、英国产业结构网络
产业是同类企业的总和, 产业结构由许多的产业部门组成, 各产业部门之间相互依存、相互联系、相互作用, 共同构成一个有机的整体。本文研究的英国产业结构网络由123个产业组成。所利用的数据来自英国2002年价值型投入产出表。为研究方便, 对数据有以下说明:
1. 不考虑本产业对本产业的中间投入, 只有这样建立起来的网络才不是一个自环的网络。
2. 引入消耗系数的临界值并进行无向化处理。临界值的计算过程如下:首先, 计算出所有的直接消耗系数, 其计算公式如下:
式中, xj为j产业的产出, xij为i产业对j产业的中间投入。然后, 把实际的有方向的数据转换成无向数据, 即:
式中, 和分别为j产业生产时所消耗i产业投入的系数和i产业生产时所消耗j产业投入的系数。令为临界值, 对所有的rij取均值即得到。计算得出的临界值为5.564×10-3, 如果则保留此数据, i与j之间有边存在。经计算得到网络中边数为2061条。
三、网络的相关统计特性
网络的相关统计特征有:平均最短距离、平均簇系数、度分布、度-度相关性、度-簇相关性、点介数。
1. 平均最短距离
在英国产业结构网络中, 最短距离表示任意两个产业之间最少的边的数目。整个网络的平均最短距离则是对所有节点对的最短距离的平均。其公式如下:
其中N=123为网络节点数, dij为节点i到节点j的最短距离, 经过计算得到网络的平均最短距离为1.925。
2. 平均簇系数
网络的簇系数是用来衡量网络节点聚类情况的参数, 一个节点i的簇系数是指它所有相邻节点之间连边的数目占可能的最大连边数目的比例, 其公式如下:
其中Ki表示节点i的度, bij为邻接矩阵元, 当节点i, j相邻时值为1, 否则为0。整个网络的簇系数C是所有节点簇系数的平均值,
经过计算得到英国产业结构网络的簇系数为0.478, 表现出聚集性。由于该网络同时具小的平均最短距离和较大的簇系数, 因此可以认为它是一个小世界网络。
3. 度分布
节点的度是指与此节点连接的边的数量, 所有节点的度的平均值称为网络的平均度。网络中节点的度分布可以用分布函数p (k) 来表示, p (k) 被定义为随机地选择一个节点恰好有K条边的概率, 或者等价地描述为网络中度为K的节点数占网络节点总数的比例。
根据英国产业结构网络的实际数据计算, 可以得到网络的平均度为16.8, 即每个产业平均连接17个其他的产业。英国产业结构网络的度分布, 如图1所示。
图1为双对数坐标, 横坐标表示点序号, 纵坐标表示节点度。由图1可见, 在这个网络中, 节点度服从双段幂律分布, 对所得数据进行双段拟合, 得到的拟合斜率分别为-0.2778和-5.8826。
4. 度-度相关性
度-度相关性表现的是节点之间相互选择的偏好性。一个节点i所有邻近节点的平均度记为
那么, 度为k的所有节点的邻点平均度为
其中, Nk是度为k的节点数目。
如果km (k) 随k递增, 则网络是正相关的;反之, 如果knn (k) 随k递减, 则意味着网络是负相关的。运用Newman给出的计算方法判断网络相关性, 即计算网络节点度的Pearson相关系数r,
其中, ji和ki分别是第i条边两个端点的度, i=1, …M, M为网络的边数, -1≤r≤1。度-度相关性如图2所示。
根据公式3-6可知英国产业结构网络的相关系数r=-0.5898, 度度之间表现出负相关性, 说明度大的节点优先连接度小的节点。英国产业结构网络是一个小网络 (节点数少) , 而且有接近六分之五的产业部门度都小于30, 因此表现出来度大的产业总是更倾向于和度小的产业连接, 这是由网络规模和自身特点所决定的。
5. 度-簇相关性
度-簇相关性是指节点的度与其平均簇系数的关系。先计算出所有节点的邻点平均簇系数, 再计算出节点度相同的所有节点的邻点平均簇系数。
由图3可知, 英国产业结构网络具有正的度-簇相关性, 表明度大的节点比度小的节点更倾向于聚集成团。对数据进行线性拟合, 其拟合斜率为0.3953。度大的节点比度小的节点更倾向于聚集成团, 即簇系数随着度值的增长而增长, 但增长速度略慢于度值的增长速度。
6. 点介数及其分布
点介数是一个重要的全局几何量, 反映了相应的节点在整个网络中的作用和影响力, 具有很强的现实意义。节点的介数含义为网络中所有的最短路径之中, 经过的数量, 记之间最短路径的集合为, 节点的介数计算公式为:
根据公式 (3-7) 可计算出123个节点当中的每个节点的介数Bi, 点介数分布如图4所示。
由图4可知, 点介数分布服从幂律分布, 介数大的节点数目较少, 介数小的节点数目教多, 大部分节点的点介数均处在0.039832和0.01639之间, 这些节点在网络中的影响较小。表中展示了介数值排名前10位的产业, 由于点介数反映了其在网络中的影响力, 那如果把表1中的任何几个节点或全部节点从网络中删除, 则会极大地影响网络的运行。
四、结论与展望
以产业部门为节点的英国产业结构网络是一个小世界网络, 具有短的平均路径长度和大的簇系数, 且其度分布服从双段幂律分布。网络表现出负的度度相关性, 表明度大的节点优先连接度小的节点。同时, 此网络具有正的度簇相关性, 说明度大的产业比度小的产业更倾向与集聚成团。
本文只是对英国产业结构网络无向性质的一个初步研究, 在后续的研究工作中会深入研究边的方向及边权、点权对网络性质的影响。除此之外, 还将对比各国的产业结构网络的性质, 从而对各国经济的增长和同一产业的发展进行比较, 进而能够采取措施促进整个经济的增长或单个产业的发展等。
参考文献
[1]周涛柏文洁等:复杂网络研究概述[J].物理, 2005, (1) :31～36
[2]Newman M E J.The structure and function of complex networks[J].SIAM Review, 2003, 45:167～256
[3]Wang X F.Complex networks:Topology, dynamics and synchronization[J].Int J Bifureation&Chaos, 2002, 12:88～916
[4]Albert R, Barabasi A-L.Statistical mechanics of complex networks[J].Rev.Mod.PhyS, 2002, 74:47～97
[5]刘宏鲲周涛:中国城市航空网络的实证研究与分析[J].物理学报, 2007, (1) :106～113
[6]郑金连狄增加:复杂网络研究与复杂现象[J].系统辨证学学报, 2005, (4) :8～13
[7]吴金闪狄增加:从统计物理学看复杂网络研究[J].物理学进展, 2004, (1) :18～46
[8]英国投入产出表http://www.statistics.gov.uk/about/methodology_by_theme/inputoutput/latestdata.asp
复杂网络 篇8
同自然界多数网络类似,城市地铁网络也是由线和点组成,是1种典型的复杂网络[1]。国内一些主要城市,如北京、上海、广州地铁建设已初具规模。随着网络规模的不断扩大,城市地铁也会出现一系列问题,例如信号故障,乘客人数的骤增造成列车、站台过度拥堵,等等。这些节点或边发生的故障会通过线路和车站之间的耦合关系扩散开来,从而引起其他节点故障,最终导致部分节点甚至整个网络的崩溃,即发生相继故障[2,3]。因此有必要对网络化条件下国内地铁网络拓扑结构特性以及相继故障的发生、发展进行研究,从而对故障的预防、控制提供理论依据。
国外对地铁网络复杂特性已有初步研究,而国内在这方面研究较少。Latora[4]等人研究了波士顿地铁网络特征,并提出网络构造法则;Seaton和Hackett[5]分析了维也纳和波士顿地铁网络的小世界特性; Angeloudis[6]分别从地铁成网过程和网络类型等方面进行了研究;汪涛[7]等人分别研究了城市地铁网络的Space L和Space P模型;李进[8]分析了国内外多个城市地铁网络拓扑特性并对北京地铁鲁棒性进行研究,得到一些有意义的结论。国内外对相继故障的研究主要集中在网络拓扑结构类型方面[9,10,11,12],对地铁网络相继故障的研究较少涉及。
本文采用Matlab编程仿真,对北京、上海、广州3个城市地铁网络复杂特性进行了研究,研究主要分为2个方面:
1) 采用Space L网络模型构造方法[7],得到地铁网络各特征值,对网络拓扑结构进行分析。
2) 采用基于耦合映像格子(CML)的相继故障模型,分析地铁网络相继故障传播特点,得到随机攻击和蓄意攻击2种策略下扰动幅度和故障规模关系,以及相继故障在这2种攻击下的扩散过程。
1 地铁网络拓扑结构分析
1.1 复杂网络特征参数
1) 直径与平均路径长度。
网络中2点之间的距离定义为连接2点的最短路径边数。其中任意2点之间距离的平均值称为网络的平均路径长度,记为L;任意2个节点之间的距离的最大值称为网络的直径,记为D。平均路径长度与直径是衡量网络传输效率的重要指标。
2) 度与度分布。
度是节点在复杂网络中的1个重要属性,是指与该节点连接的边数。节点度的分布情况可以用分布函数P(k)来描述,是指1个随机选定的节点度恰好为k的概率。度分布反映了节点度在网络中的宏观统计特征。
3) 聚类系数。
聚类系数Ci又叫做群聚系数,定义为与该节点直接相邻的实际边数目与最多可能边数之比。聚类系数是反映网络中节点聚集程度的重要参数。整个网络的聚类系数<C>即为网络中所有节点聚类系数的平均值。
4) 节点介数。
节点介数是指网络中通过该节点的最短路径的数目。节点介数是1个宏观统计量,反映了相应节点在整个网络中的重要程度。
1.2 地铁网络拓扑结构特征分析
结合上述评价分析指标,对北京、广州、上海地铁网络的拓扑结构特征进行对比分析,
其中对地铁网络构造说明如下:
1) 分析所用数据均来自各城市地铁运营公司官方网站,时间截止到2011年底。
2) 地铁网络采用Space L构造方法,以地铁车站作为网络节点,若在实际网络中2站点之间有线路直接相连,则将其作为构造网络的1条边,并且在网络构造过程中对部分线路和站点进行了适当处理。对于部分孤立线路,比如北京地铁9号线、房山线和S 2线,以及尚未开通站点均不在数据统计范围之内。
3) 不考虑地铁线路方向和列车在线路上行驶时间,将地铁网络抽象为无向非加权网络。对北京、广州、上海地铁网络拓扑结构特征值统计见表1:其中直径、平均路径长度、度、平均度在复杂网络中均为无纲量,在此指代不同情形下两点之间边的个数。
由表1可知:北京、广州、上海地铁网络规模虽不相同,但其直径、平均度、平均路径长度和聚类系数都非常接近,说明3座城市具有相似的网络逻辑结构。地铁网络平均度接近于2、平均路径长度在14~15之间,说明多数站点仅有1条地铁线路通过,任意2点平均需要经过14~15个站点才能到达目的地,该值明显大于小世界或无标度网络中平均路径标度值lg N,其中N为网络节点数;北京和广州聚类系数为零,上海近似为零,这是因为在上海地铁网络中宜山路、徐家汇和上海体育馆3个车站两两相连,在网络形态上呈现出三角形,从而导致网络中节点的聚类特征,而小的聚类系数则意味着地铁网络容错性较差,可选择的出行路径较少,当某段线路被临时取消时,对部分乘客会造成较大影响。以上分析表明城市地铁网络具有较小的聚类系数和较大的平均最短路径,网络中站点较为分散,网络路径的可替代性较差。这同熟知的万维网、社会网络、生物网络[13]等许多现实中的其他网络有明显不同。
北京、广州、上海地铁网络介数和度的关系见图1。
从图1(a)、(b)、(c)中可以直观的看出,度越大则相应度的节点介数会在1个更大的数值周围波动,度和介数之间呈现出正相关性。说明在国内地铁网络中与节点所连接边越多则可能有更多的最短路径通过,则该节点越重要。在复杂网络中节点度反映了节点自身的重要性,是1个微观数值,而节点介数则反映出节点在整个网络中的重要程度,是1个宏观统计量,以上结果表明了在地铁网络中节点在微观和宏观上的一致性。
为了更好的说明度和介数的统计关系,在此引入度的平均介数的概念。将度的平均介数定义为度为k的所有节点介数的平均值,以下简称平均介数。从而得到图1(d),可以看出度和平均介数的关系曲线近似为直线,经Matlab拟合分别得到3城市曲线斜率为:北京0.063 59,广州0.101 70,上海0.045 27。可以看到拟合曲线斜率的大小关系为,广州>北京>上海,而其网络规模恰好相反。表明国内地铁网络度和平均介数呈线性正相关,而且这种正相关性会随着地铁网络规模增大而变得越来越弱。
地铁网络度分布分析:
地铁网络度分布拟合曲线如图2所示。
从图2中可以看出国内地铁网络大部分站点度为2(其中北京81.4%、广州82.0%、上海79.9%),少数其他度数站点分布在两侧,度分布曲线存在明显峰值,可以近似为Poisson分布,通过对多种拟合函数比较分析,发现高斯分布函数可以得到较好的拟合结果。经Matlab拟合,得到如下拟合函数:
北京。P(k)=0.845 6×e-((x-1.89)/0.563 5)2
广州。P(k)=0.839 2×e-((x-1.907)/0.607 2)2
上海。P(k)=0.811×e-((x-1.929)/0.585 9)2
以上3个拟合函数的方程确定系数均在0.98以上,均方根误差和残差平方和分别在0.009和0.038以内,拟合效果较好。
在复杂网络中,规则网络的特点是聚类系数较大而平均路径较长;随机图与之恰好相反,且度分布近似为Poisson分布;小世界网络模型具有较短的平均路径 (约为lg N)和较高的聚类系数;无标度网络的度分布具有幂率形式[16]。通过对北京、广州、上海地铁网络拓扑结构分析可以看到,以Space L模型为基础的国内地铁网络具有较小的聚类系数和较大的平均最短路径,度和介数呈线性正相关,度分布近似服从Poisson分布。显然地铁网络既非规则网络,同时又不属于小世界或无标度网络,而是具有一定随机网络特征的混合拓扑结构网络。这主要是因为对于地铁网络而言,有其建设的特殊性和复杂性,因而表现出一定的不确定性。通常在有限的土地和资金条件下,为了保障网络覆盖率和良好的平行线路间距,地铁网络会在保证乘客出行方便的前提下,尽量均匀的覆盖所在地区,除环线之外,其他线路间相互联系较少,因而造成地铁网络的平均度接近于2,多数站点仅有一条线路通过,并且极少出现站点的聚类现象。同时城市地铁发展受到地形、经济、政策等诸多方面的制约,在实际规划线路时还要考虑乘客的出行服务频率、线路客流分布、线路重复率等因素,导致新增站点的不确定性,在网络拓扑结构上则表现出一定的随机网络特征。
2 地铁网络相继故障分析
2.1 基于CML的相继故障模型
将具有N个节点的CML相继故障模型描述如下[10,11,15] :
式中:xi(t)为第i个节点在t时刻的状态。N个节点的连接信息用邻接矩阵A=(ai,j)N×N表示。若节点i和j之间有边相连,则aij=aji=1;否则aij=aji=0。规定任意2个不同的节点之间至多只能有一条边,且不允许节点和自身相连。k(i)是节点i的度,ε∈(0,1)表示耦合强度。非线性函数f表征节点自身的动态行为,选择为混沌Logistic映射:f(x)=4x(1-x),当0≤x≤1时,0≤f(x)≤1。上式中的绝对值符号保证各节点的状态非负。
如果节点i的状态在m个时序内始终在(0,1)范围内,即0<xi(t)<1,t≤m,那么称节点处于正常状态。如果在m时刻,节点i的状态xi(m)≥1,那么称节点在此刻发生故障,节点在以后的任意时刻状态恒等于零,即xi(t)≡0,t>m。在节点状态按照公式(1)迭代演化的网络中,如果所有N个节点的初始状态都在(0,1)范围内,并且没有外部扰动,那么所有的节点将永远保持正常状态。
假设在m时刻给某个节点c施加1个外部扰动R≥1,见式(2)。
在这种情况下,节点c在第m时刻发生故障。因此,对所有的t>m有xc(t)≡0。在第m+1时刻,与c直接相邻的节点都将受到m时刻c节点的状态xc(m)的影响,并且这些节点的状态值按照式(1)计算得出。此时计算出来的节点状态值也有可能大于1,从而会引起新一轮的节点故障。这个过程反复进行,节点故障就可能扩散,最终导致网络的崩溃。
2.2 相继故障仿真结果分析
在2.1的分析中知道国内地铁网络中度和介数呈正相关性,故只将度作为区分关键节点和非关键节点的特征参数。本次仿真工具采用Matlab,图中数据均为50次实验的平均值,并在第10个时刻选择攻击节点施加扰动R(R≥1)。与常规公交相比,地铁作为1种高密度交通运输系统,具有较高的独立性,站点之间耦合强度都比较大,因此在这里取ε为0.6。实验采取2种攻击策略:随机攻击和蓄意攻击。前者模拟地铁网络中随机发生的节点故障,将初始扰动施加到随机选择的1个节点上;后者模拟地铁网络遭受蓄意攻击时的情况,攻击者通常会选择关键节点进行攻击,在这里对北京、广州、上海分别选取西直门、广州火车站、世纪大道作为攻击目标。首先读入网络邻接矩阵,求出相应参数,然后根据CML相继故障模型得到仿真结果,输出数据并画出关系图。
图3显示了地铁网络中在随机攻击和蓄意攻击2种策略下,扰动幅度R与故障规模I(即发生相继故障的节点个数与整个网络节点个数比值,为无纲量)的关系曲线。从图中见,3座城市地铁网络的扰动幅度与故障规模均有相似的变化趋势,故障规模都会随着扰动幅度的增大而增加,并且在这2种攻击策略下均存在相似的阙值R*1、R*2[14]。当R在这种情况下,节点c 在第m 时刻发生故障。因此,对所有的t>m有xc(t)≡0。在第m+1时刻,与c直接相邻的节点都将受到m时刻c节点的状态xc(m)的影响,并且这些节点的状态值R<R*1时故障规模I很小(I≤0.2),并且变化非常缓慢;当R*1≤R≤R*2时,故障规模I会迅速增加,并最终造成全局故障。从图中可以看到,该相继故障模型下,与随机攻击相比通过蓄意攻击引起相继故障进程稍有增加,但是效果并不明显,这主要是因为地铁网络的具有一定的随机网络特征。通过前面的分析已知地铁网络度近似服从Poisson分布,多数节点度为2,度分布较为均匀,因此相同的扰动幅度下,由蓄意攻击和随机攻击两种策略引起的相继故障规模不会有明显变化。
图4是单个节点相继故障在地铁网络中的扩散过程,图中t指故障传播时序。图4(a)、(b)分别表示了网络在随机攻击和蓄意攻击2种策略下故障规模的传播曲线,其中取扰动幅度R=12。可以看到在同一攻击策略下地铁网络的相继故障扩散过程也呈现出相似的变化趋势。在第0时刻施加扰动后,蓄意攻击策略下在各个时刻引起的节点故障规模总是大于随机策略,并且故障规模一开始便有较快的增长速度,变化呈现出先快后慢的趋势;而随机攻击策略下网络故障规模呈现出“慢-快-慢”的变化趋势。同小世界网络相比[15],地铁网络在2种攻击策略下的相继故障传播均需要较长时间,这也验证了地铁网络具有较大的平均最短路径拓扑结构特征。
3 结论与展望
1) 以Space L模型为基础的国内地铁网络具有较小的聚类系数和较大的平均最短路径,度和介数呈线性正相关,度分布近似服从Poisson分布,是1种具有随机网络特征的混合拓扑结构网络。
2) 同许多其他网络类似,地铁网络CML蓄意攻击下故障扩散过程比随机攻击要剧烈,具有较快的传播速度;但当相继故障经过充分传播时,通过蓄意攻击造成网络故障规模效果并不明显。
本文只是在地铁网络物理层面分析其网络拓扑结构和相继故障,而未考虑运营交路、乘客换乘等诸多复杂情况,需要结合地铁网络实际情况做进一步研究。
公交网络复杂性分析 篇9
青岛位于山东半岛南端, 多为丘陵, 旅游业发达。公交路网的规划合理与否直接影响到市民的日常生活。本文运用复杂网络的研究思路, 以山东省青岛市公交系统中的停靠站点为研究对象, 对其进行复杂性分析, 计算了网络的度分布、聚集系数、平均路径长度等指标来讨论公交线网的性能, 为青岛公交网络的优化和完善提供依据。
1 青岛公交换乘网络相关定义
定义1:一条公交线路是公交站点的有序集合, 记为:L (D, R) , 其中D={s1, s2, ……si, ……sn}为公交站点的集合, R={N}, N={
定义2:公交线路换乘网络是以公交站点为顶点构成的无向图, 记为:G (V, E) , 其中V为所有公交停靠站点的集合, 对于i, j∈V, 若i, j之间存在一条边eij当且仅当第i个站点与第j个站点之间有同一辆公交车经过。
一般来讲, 节点的度越大, 说明不用换乘就能到达该点的车站数目越多, 在该点处乘车越方便, 因此, 度数大的车站为网络中的枢纽站点。
定义3:公交换乘网络的顶点i的度指站点i可以直接到达的公交站点的数目。
定义4:累计概率, 即节点度大于或者等于K的概率。
定义5:节点i的聚集系数为, 其中ki为节点i的度, Ei为ki个节点之间实际的边数, 网络的聚集系数即各个节点聚集系数的平均值, 记为:。
定义6:站点i和j的最短路径长度是指站点i和站点j之间的最短路径经过的站点数, 网络中最短路长的最大值称为网络直径。
对于公交换乘网络来讲, 同一个公交线路中的节点是全连接的, 因此同一条公交线路中的任意两个站点间的最短路长为1, 换乘次数即为最短路径长度减一。
2 公交换乘网络分析
2.1 建立网络
据青岛信息港网站 (http://www.qd.sd.cn/) 提供的数据, 截止至2009年青岛市共有130条公交线路, 涉及到864个公交站点。这里并未考虑那些通往郊区的线路以及青岛郊区的公交线路。
公交网络包含停靠站点和线路两个基本要素。1条公交线路由若干公交站点组成, 一个站点可能有许多公交车经过。各条线路之间通过交汇的停靠站点发生联系, 站点与站点之间通过线路相联系。
为了研究方便, 在建立公共交通网络时, 做了以下假设:
(1) 大多数公交车来回走的线路是一样的, 但是不排除有极少数公交车因条件限制来回路线上稍微有些不同, 在进行数据提取时, 为了研究上的方便, 统一取下行方向的路线为标准, 网络抽象为无向网络。
(2) 相同名称的站点看作同一个停靠站点, 不同名称的站点视为不同的停靠站点。这里忽略了个别停靠站点名称相同但停靠地点不同的情况。
根据定义2, 构建了青岛市公交换乘网络, 网络的顶点是停靠站点, 如果站点之间有同一条公交线路通过则有一条边连接。这种方式构成的网络是一个无向网, 且同一条公交路线上的各个站点之间是完全连接的。最终, 该网络共包含864个节点, 34725条边, 是一个全连通网络, 说明在该网络中不存在孤立的全连接子网, 每条公交线路都可以通过其它的线路进行换乘。该网络可以很好的反应公交系统的换乘状况, 换乘情况是刻画公交系统可达性的一个重要指标。
2.2 网络拓扑参数分析
无向网络几个重要的拓扑参数有:度分布、聚集系数、平均路径长度等, 下面使用R环境对这些参数进行计算和分析, 估计青岛市公交换乘网络的性能和特点。
2.2.1 度与度分布
由定义3可知, 节点的度定义为该节点拥有的相邻节点的数目, 表明了从这个站点出行的方便程度。根据青岛市公交网络的实际数据计算, 可以得到青岛公交网络换乘网络的平均度
其中福州路一站具有最大的节点度400, 共有32辆公交车经过, 其次是度为379的李村站, 然后是台东站, 度为347, 中山公园仅次于台东站, 度为337。在此定义的节点是有相同站点名的公交站点, 和实际站点安排有一定的误差, 存在着节点名相同但实际站点不一致的情况。如福州路这一节点有4个不同的实际站点:远洋广场、天福苑小区、福州南路以及福州北路。福州路是市南区繁华的商业街, 是大型超市、银行等聚集的地方, 李村拥有庞大的居民区, 台东位于青岛市市北区, 拥有目前青岛最大的台东商圈。可见, 这些地方是青岛的繁华地带, 交通比较便捷, 青岛公交系统的安排比较合理。
为了便于对网络节点度进行研究, 公交换乘网络度的分布情况图如图1所示:
图1 (a) 显示了青岛市公交换乘网络的度分布情况, 其中横坐标为节点的度, 纵坐标为具有相应度的节点数的比例。可以看出该网络的度分布情况偏离Poisson分布, 明显向右倾斜, 这表示右边尾数过长且远大于平均数, 尾部有噪音不易测量。为了便于分析, 本文采用了累计概率, 如图2 (b) 所示。横坐标为节点的度, 纵坐标为累计概率的对数, 这样做的优点在于考虑了所有的原始数据。可以看出, 该图接近于一条直线, 青岛公交换乘网络的度分布服从指数分布。
2.2.2 聚集系数
由定义5可知, 聚集系数主要用来考察网络的聚集化程度, 定义为一个节点的任意两个邻居节点也连接的概率, 在公交网络中, 聚集系数即任意一个站点不需换乘即可到达的站点间也可以直达的概率。只有网络是全连接网络时, 该网络的聚集系数为1, 否则都小于1, 可见网络的聚集系数越大, 聚集程度越高。
公交换乘网络是由一个个的全连接子网构成, 这些子网内部的节点属于同一条公交线路, 各个子网之间通过交汇的站点连接。青岛市公交网络中每个站点聚集系数的分布情况如图2所示。可以看出, 青岛市公交网络中聚集系数大的站点比较多, 多于40%的站点聚集系数是1, 不能排除个别站点名字不同但实际站点相同的情况, 但是也能够反映出青岛公交网络中不乏少数的节点只有一条公交车通过, 这些站点一般地处偏僻, 或者因为城市的规划新增的一些站点, 如奥帆基地。相应地, 剩下的站点均有多辆公交车经过, 对这些站点来讲, 公交车聚集很多, 会导致路段的负荷过大, 容易造成交通阻塞现象。如果能有效利用那些聚集系数为1的车站, 可以在一定程度上缓解交通压力。
由上述分析可知, 利用复杂网络分析中的聚集系数这一参数来衡量网络的密集程度, 在公交换乘网络中并不适用。如那些只有一条线路经过的站点, 因为处于一个全连接子网中, 聚集系数为1。李村站有25辆公交车经过, 是一个重要的交通枢纽, 聚集系数反而很小, 为0.2。
站点的聚集系数与通过该站点的交通线路之间的关系如图3所示, 横坐标为通过每个站点的公交车的数目, 纵坐标表示相应站点的聚集系数。由图整体的变化趋势来看, 随着节点的聚集系数变小, 通过节点的公交线路会增多, 该点在公交线路中所起的作用越大, 该点的公交线路聚集化程度越高。这说明节点的聚集系数与通过该节点的公交线路的数目呈反相关系。
2.2.3 平均路径长度
由定义6可知, 网络的最短路径长度是指任意两个站点间的最短路径经过的边数, 也就是某一停靠站点到另一停靠站点之间换乘的次数再加一。对于青岛市公交换乘网络, 其网络直径为4, 平均路径长度等于2.135, 这意味着市民出行一次平均只需换乘1到2次车就可到达目的地。从一个站点到另一个站点需要换乘的次数的概率分布如图4所示, 结果显示目前的青岛公交网络从换乘情况来看, 在青岛出行还是比较方便的。
青岛市公交换乘网络的平均路径长度为2.135, 相同规模的随机网络的平均路径长度为1.9, 交通网络的聚集系数为0.433, 相同规模的随机网络的聚集系数为0.101。由此可以得出, 青岛市公交换乘网络具有较小的平均路径长度和较大的聚集系数, 具有比较明显的小世界网络的特征。
3 结束语
复杂网络 篇10
从20世纪70、80年代开始，复杂性问题的研究与非线性科学及其混沌动力学的复杂研究交错在一起，在国际上形成了非线性科学与复杂性问题的研究热潮[4]。而利用复杂网络理论来研究非线性复杂网络的方法已渗透到众多学科之中。将电力电子电路系统看成一个网络，可以用复杂网络特性的统计指标描述电力电子电路系统整体的状态，从而研究电力电子电路系统复杂网络的特性。复杂网络为其提供了一个全新的视角和研究方法[5]，从复杂网络的角度来分析和研究电力电子电路系统，有助于从整体上把握它的复杂性。
三相全控整流电路的整流负载容量较大，输出电流电压脉动较小，是目前应用最为广泛的整流电路，逆变电路在电力电子电路中占有十分突出的位置，其应用非常广泛，在三相逆变电路中，应用最广泛的应是三相电压型桥式逆变电路。本文以三相桥式全控整流电路及三相电压型桥式逆变电路为例将复杂网络应用到电力电子电路系统，用复杂网络的原理对电力电子电路的复杂性进行了分析[6,7]。
1 复杂网络的几何量
用图的顶点(或称为节点)代表所研究的事物，用图的边表达事物之间的联系，这样能较好地刻画出所研究的系统。在复杂网络中，人们最先考虑的是其统计特征：平均路径长度、聚类系数和度的分布律。具有较短的平均路径长度、较高的聚类系数是小世界网络[8]的典型特征，网络的度分布服从幂律分布时被称为无标度网络[9]。
如果把电力电子电路系统看作许多元件和各个电路的集合，把元件称为“节点”，并且把电路都称为“边”，则电力电子电路系统就被抽象、简化为一张普通意义上的“复杂网络”。复杂网络的基本几何量有：最短路径、平均距离、聚类系数、节点平均度数及节点度数分布、节点的介数及节点的介数分布等特征参数的规律。其定义分别如下：
(1)最短路径Lij。两点的最短路径Lij定义为所有连通i,j的通路中，所经过的其他顶点最少的一条或几条路径。
(2)平均距离L。网络中两个节点i,j之间的距离dij定义为连接这两个节点的最短路径上的边数。对任意两个节点之间的距离求平均值，就得到了该网络的平均距离：
其中N为网络节点数，平均距离反映了网络中节点之间信息传播的平均长度。
(3)聚类系数C。网络的聚类系数C是专门用来衡量网络节点集聚程度的一个重要参数。每个节点的聚类系数可表示为：
式中，ai为连接到顶点i的三角形的个数;bi为连接到顶点i的三元组的个数。整个网络的聚类系数定义为：
(4)网络平均度数K。节点的度数是指连接这个节点的边数。对所有节点的度数求平均值，即得到网络的平均度数K。对于一个边数为E、节点数为n的网络，其平均度数可表示为：
(5)节点度数分布Pcum(k)。用p(k′)表示度数为k′的节点个数占节点总数的百分比，则节点度数的积累概率为：
(6)节点介数分布Pcum(s)。节点介数是指所有最短路径中必须经过此节点的次数。用p(s′)表示介数为s′的节点个数占节点总数的百分比，则节点介数的累计概率为：
2 典型电力电子电路网络特性分析
2.1 三相桥式全控整流电路特性分析
三相桥式全控整流电路原理图如图1所示。如果把该图系统看作许多元件和电路的集合，把元件称为“节点”，并且把电路称为“边”，该整流电路系统就被简化为一张“复杂网络”，如图2所示。
本文将上一节的算法编制成MATLAB程序，通过式(1)～式(6)计算上述基本参数，并对三相桥式全控整流电路的网络特性以及其他相关的重要拓扑特性进行分析。其中将三相桥式全控整流电路网络简称为A网络。其拓扑参数如表1所示。其中，K表示网络平均度;L表示网络平均路径长度;C表示网络聚类系数。
由表1及图3可知，从网络拓扑参数方面考虑，A网络由于网络规模较小，平均路径较短，所以故障传播速度比较快，且对照图1、图2可以看出度数较大的元件为与三相电源相接的晶闸管。图4说明A网络的度分布在对数坐标系中对应于一条直线，符合幂律分布。
图5的曲线表明,A网络的介数分布曲线在对数坐标下呈线性，符合幂律分布，而具有幂律度分布的网络也称为无标度分布，所以A网络为无标度网络，具有无标度网络的特性。
2.2 三相电压型桥式逆变电路特性分析
三相电压型桥式逆变原理图，如图6所示。如把该图系统看作许多元件和电路的集合，同样把元件称为“节点”，并且把电路称为“边”，该逆变电路系统就被简化为一张“复杂网络”。如图7所示，将三相电压型桥式逆变电路网络简称为B网络。其拓扑参数如表2所示。其中，K表示网络平均度;L表示网络平就路径长度;C表示网络聚类系数。
由表2及图8可以看出B网络在网络拓扑参数方面平均度比较高，高度数节点相对集中，所以故障传播速度也比较快。对照图6、图7可知其度数较大元件为功率开关器件。图9说明B网络的度分布在对数坐标系中对应于一条直线，符合幂律分布。
如图10所示，B网络的介数分布曲线在对数坐标下呈线性，所以B网络同样为无标度网络。
由上面所述的2个典型电力电子电路系统网络可以看出，电力电子电路系统网络多为无标度网络，其中存在部分度数和介数很高的节点，成为网络的重要支撑点。下面将对这2个网络进行鲁棒性、脆弱性的仿真研究,通过仿真来验证这部分节点对系统产生的重要影响。
3 典型电力电子电路的网络鲁棒性与脆弱性研究
目前,普遍使用的衡量网络特性的指标是效能函数。整个网络G的功效性指标定义如下：
假设εij表示两节点之间的通信效率，与这两节点之间的最短距离成反比，而当dij=∞,即两节点之间没有路径时εij=0。
攻击脆弱性是复杂网络研究的一个热点分支，其基本定义是从网络中有选择地或有针对性地移去网络元件，以网络性能下降的程度来衡量此元件的脆弱度。而通过随机移除网络元件来考察网络性能的分析过程被称为网络的鲁棒性分析，研究目的在于识别出对系统功能影响严重的故障，从而采取正确的预防、校正措施，实施保护。
经过以上的参数计算，得到节点度数排序和节点介数排序，针对这两种情况，对网络进行攻击仿真，观察网络效能的变化情况，并与随机攻击相对比。攻击联络节点的方式可分为：随机攻击某个节点，并逐步增加被攻击节点的个数;有选择地蓄意攻击度数最大的节点，并依次攻击度数次大的节点;有选择地蓄意攻击介数最大的节点，并依次攻击介数次大的节点。
从仿真结果可以得出，节点的失效使得网络的特性曲线下降。蓄意攻击所引起的网络效能下降比随机攻击造成的影响要大，效能曲线的变化更快。A、B两个网络均为无标度网络，在蓄意攻击的模式下，失去很少的节点就能使得效能下降很快，这说明A、B网络对随机元件故障具有高度的鲁棒性，对蓄意攻击具有高度的脆弱性。网络结构的不平衡性使少数高介数和高度数节点能对网络产生很大的影响，对于这种小型电力电子网络来说，连接度比较高的节点和传输次数比较多的路径的点造成了这种结构上的不平衡，成为了网络上的脆弱点。综上所述，可以将介数和度数指标作为衡量网络脆弱点的标准，对小型电力电子网络来说，故障是不可避免的。通过上述分析可知，三相桥式全控整流电路的晶闸管和三相电压型桥式逆变电路的功率开关器件为上述的脆弱点，且实际运行表明其元件损坏确实为绝大多数故障的原因。因此，必须加强与网络结构相关联的节点的保护，保证结构更加平衡来提升性能。
可以看出，电力电子电路中多为无标度网络，其网络的非均匀性使得对蓄意攻击具有高度的脆弱性。
通过对典型电力电子电路鲁棒性与脆弱性的研究，发现了电力电子电路系统潜在的脆弱点，分析了影响网络脆弱性的因素。今后的研究将围绕系统元件的承受能力限制来进行研究，使这种分析方法更加完善。
摘要：基于复杂网络对电力电子电路的复杂性进行了研究,指出了复杂网络在电力电子技术中运用的结合点并以三相桥式全控整流电路及三相电压型桥式逆变电路为研究对象,提出用复杂网络的特征参数来分析该电路拓扑特性的方法,并对其鲁棒性及脆弱性进行了分析研究。最后对电力电子电路复杂性研究结果存在的问题进行了分析和总结。
关键词：复杂网络,电力电子技术,鲁棒性,脆弱性
参考文献
[1]DOBSON I,CARRERS B A,LYNCH V E,et al.Com-plex systems analysis of series of blackouts,cascading fail-ure,criticality,and self-organization[C].//9thBulk PowerSystem Dynamics and Control-VI Cortina d’Ampezzo,Italy,2004:438-451.
[2]CARRERAS B A,NEWMAN D E,DOBSON L,et al.Evidence for self-organized criticality in a time series ofelectric power system blackouts[J].IEEE Trans Circuits andSystem,2004,54(9):1733-1740.
[3]DOBSON I,CARRERAS B A,LYNCH V E,et al.Aninitial model for complex dynamics in electric power systemblackouts[C].//proceedings of 34th Hawaii International con-ference on system sciences.Maui,Hawaii January,2001,710-718.
[4]方娜清,汪小帆,刘增荣.略论复杂性问题和非线性复杂网络系统的研究[J].科技导报,2004,22(2):9-12,64.
[5]孙可,韩祯祥,曹一家.复杂电网连锁故障模型评述[J].电网技术,2005,29(13):1-9.
[6]欧阳敏,费奇,余明辉.复杂网络的功效性与脆弱性研究综述[J].计算机科学,2008,32(7):1-4.
[7]丁明,韩平平.加权拓扑模型下的小世界电网脆弱性评估[J].中国电机工程学报,2008,28(10):20-25.
[8]WATTS D J,STROGATZ S H.Collective dynamics of‘small worlds’networks.Nature,1998,393(6884):4404-42.
