改进复杂网络模型

改进复杂网络模型（精选7篇）

改进复杂网络模型 第1篇

随着特高压电网逐步建设和大规模跨区域输电增多,区域间电力系统互联更加紧密,电网规模不断增大,电网形态也更加复杂[1],在提高了经济性与可靠性的同时,也增加了由局部故障引发大面积停电等灾难性事故发生的可能性[2,3]。利用复杂网络理论能从拓扑结构的角度整体分析电网的特性,但现有分析大多基于引入部分电力系统相关的网络性能指标或参量的复杂网络模型,与实际的电网模型差别较大[4]。

目前,构建适用于电网的复杂网络模型主要从引入电网的物理特性和运行约束来改进,如建立了加权网络模型、采用最短路径或潮流分布因子来模拟电网中功率的传输、考虑支路和节点的容量极限。文献[5-7]把支路阻抗作为节点间的距离,把支路潮流作为边的权重,使得模型更接近电网结构的物理特性,同时考虑了电力系统运行参数,但两者的联系有待进一步深入研究。在计算以平均最短路径为代表的连通性指标时,电网模型从无权模型发展到加权模型,最短路径的定义从任意2个节点间最少边数目发展到线路最小电抗值之和,逐步完善了模型的物理意义,但结果是把功率通过电网的传输简化为只沿最短路径传输[8],而采用潮流分布因子的方法是基于潮流的直流模型[9],这都与电网中的实际情况存在差距。此外,以往的建模中往往忽视了电网支路传输功率上限。文献[9]把边的权重定义为反映不同电压等级边的重要程度,从电压等级方面考虑了线路的容量极限,但与电网运行实际仍存在差距,如发电机节点的出线电压等级一般较低,而输电容量一般较大,与发电机的最大出力相匹配。

近年来,世界范围内发生的大停电事故初期往往是少量元件相继故障,进而影响到电网该状态下的关键环节(节点和支路),造成了事故扩大[10,11,12]。因此,辨识出电网实时状态下的关键环节,并进行重点监控与保护,对指导电网规划以提高电网强度、帮助电网运行人员控制事故发展具有十分重要的意义。电网环节的关键程度一方面既体现在其重要性上,另一方面也体现在其脆弱性上。利用复杂网络理论辨识电网结构中的关键环节,其核心指标是节点度数、介数和边介数,通过对这些指标的改进与完善,可以更侧重于脆弱性或重要性。文献[13-14]在电网的无向无权小世界模型基础上,指出高介数的节点和线路对连锁故障的发生和扩大有着重要作用,认为电网在应对故意攻击时存在脆弱性。文献[5-6,9,15-17]对最短路径的定义作出了前文所述的改进,并引入潮流作为支路权重,使介数的计算更符合电网的物理特性,并在一定程度上同时考虑了电网结构和潮流状态的影响,从重要性或脆弱性的角度考察了节点、线路的关键性。但这些指标的计算大多是基于潮流沿最短路径传输的假设,有必要深入探讨电网潮流状态与电网结构之间的关系,且定义的节点度数、介数和支路介数指标不够完善,如文献[5]指出现有的介数指标并不能准确反映出节点对功率的输入量、输出量、承载能力及节点在电网中的活跃程度。

针对上述研究现状,本文通过对功率传输路径、路径的功率加权传输距离以及传输能力的定义,使得基于复杂网络理论的电网模型更好地符合电网的物理实际和运行约束。基于改进模型提出了合理确定电网关键环节的系列指标,并通过对IEEE典型系统和某省级电网的实例仿真验证了所述模型和算法的合理性与有效性。

1 电网复杂网络模型的改进

电网中节点和节点之间通过支路相连通的实际功率传输路径包含多个反映电网物理特性的属性,如电气距离和传输能力等。将各节点及支路所参与的功率传输路径的电气距离、传输功率和传输能力等属性反映在所建立的电网复杂网络模型中,结合电网的实际运行状态,可以分析出电网中的节点之间实际耦合作用的强弱。因此,本文给出了功率传输路径、功率加权传输距离以及路径传输能力的定义及其计算方法。

1.1 功率传输路径

当前许多文献中节点和支路介数的计算都是基于“节点间最短路径”这一定义,与实际电网特性不符。为此,本文采用基于潮流追踪法的发电—负荷节点对之间的功率传输路径解析方法[18],搜索电网任意发电—负荷节点对之间的功率传输路径(由顺序相接的节点、支路组成)集合,进而计算得到该发电—负荷节点对之间每一条路径上的传输功率。针对实际电网中存在的多回线,本文认为每回线都参与到经过该线路两端的节点的传输路径中,对每条路径贡献的传输功率正比于每回线的实际传输功率。

1.2 功率加权传输距离

电气距离是表征电网中节点对之间功率传输难易程度的测度。基于不同的研究目的对电气距离的定义有所不同,常见的有线路阻抗法[17]、电压灵敏度法[19]、阻抗矩阵法等[20]。对一条传输路径而言,本文将该路径所包含各支路的阻抗和定义为该路径的功率传输距离。对高电压等级线路,有较大数值等效充电容纳,但高电压等级的线路两端一般并联有电抗器进行补偿,这减小了等效充电容纳,因此本文没有考虑其影响。

对于相同或不同发电—负荷节点对之间的多条功率传输路径,每条路径承担的功率传输比例可能有所不同,因此有必要对功率传输路径赋予合适的权值,本文按权重系数与传输功率成正比的方式赋予权值。因此,对于一条功率传输路径,其功率加权传输距离为该路径的权重系数与电气距离的乘积。

1.3 路径传输能力

路径传输能力定义为一条路径的传输容量极限,传输容量极限由系统在一定运行方式下的静稳极限来确定,并认为一条由多个支路组成的路径的传输容量极限为各支路的传输容量极限最小值。

式中:pk为第k条传输路径的传输能力;bi为第k条路径中的第bi条支路;Rk为第k条路径中所包含的支路集合;为第bi条支路的传输容量极限。

上述功率传输路径、功率加权传输距离和路径传输能力综合考虑了电网结构和系统运行状态,克服了功率沿着节点之间的最短路径传输这个不合理的假设,在此基础上建立的辨识模型能更准确地反映电网的物理特性。

2 电网关键环节辨识模型

基于功率传输路径、功率加权传输距离和路径传输能力的定义,本文建立了电网关键环节的评价指标集,包含节点距离度、节点能力度、节点枢纽介数、节点距离介数、节点能力介数、支路枢纽介数、支路距离介数、支路能力介数8个指标。从电网整体结构和系统运行状态的角度,较为准确地考虑了电网中的节点与支路在电网中承担的任务和在电网结构中的地位。指标模型结构如图1所示。

2.1 节点评价指标簇

1)电网节点度指标集

电网节点度指标集包含节点距离度和节点能力度两个指标。

节点距离度表征与节点i直接相连的支路的总电气距离,反映了与该节点直接相连的线路在电网中直接覆盖的电气距离范围。距离度越大,节点i在电网中的覆盖距离范围越大,在电网结构中的地位越重要。

节点能力度表征与节点i直接相连的支路的功率传输能力,反映了节点在电网中提供的支路传输能力大小。其值越大,节点i与其他节点之间连通的支路功率极限传输容量越大,节点在系统运行中的地位越重要。

节点距离度和节点能力度分别按式(2)和式(3)计算:

式中:dLi和dCi分别为节点i的距离度和能力度;i和j为节点号;lij为节点i与j之间的电气距离;cij为节点i与j之间的支路传输能力;αij为电网节点邻接矩阵的元素,对于节点i,若节点j与其直接相连,且功率由节点j流向i则αij=1,功率由节点i流向j则αij=-1,若节点j与i没有直接相连,则αij=0。

2)电网节点介数指标集

电网节点介数指标集包含节点枢纽介数、节点距离介数和节点能力介数3个指标。

节点枢纽介数表征电网中经过节点i的发电—负荷节点对之间功率传输路径数与电网中所有发电—负荷节点对之间的功率传输路径总数的比值。节点枢纽介数越大,电网中经过节点i连通的发电—负荷节点对间的传输路径比例越大,该节点对于全网的功率传输枢纽作用越重要。

节点距离介数表征电网中经过节点i的发电—负荷节点对之间路径的功率加权传输距离之和与电网中所有发电—负荷节点对之间的传输路径的功率加权传输距离之和的比值。节点距离介数越大,电网中经过节点i的发电—负荷节点对之间的路径所覆盖的规模越大,该节点对于全网的范围覆盖枢纽作用越重要。

节点能力介数表征电网中经过节点i的发电—负荷节点对之间路径的功率加权传输能力之和与电网中所有发电—负荷节点对之间的传输路径的功率加权传输能力之和的比值。节点能力介数越大,电网中经过节点i的发电—负荷节点对之间路径的功率传输能力越大,该节点在全网的传输能力枢纽作用越重要。

节点枢纽介数、节点距离介数和节点能力介数分别按式(4)、式(5)、式(6)计算:

式中:bHi,bLi,bCi分别为节点i的枢纽介数、距离介数和能力介数;k为节点号;G为电网中所有发电节点的集合;L为电网中所有负荷节点的集合;M(jk)为发电节点j与负荷节点k间的功率传输路径数;wjk(m)为发电节点j与负荷节点k间的第m条功率传输路径的权重系数,其与该条路径上输送的功率大小成正比;ni(m)为发电节点j与负荷节点k间的第m条功率传输路径是否经过节点i的标识,若经过节点i为1,否则为0;djk(m)为发电节点j与负荷节点k间的第m条功率传输路径的电气距离;cjk(m)为发电节点j与负荷节点k间的第m条功率传输路径的传输能力。

2.2 支路评价指标簇

支路评价指标簇只包含电网支路介数指标集,由支路枢纽介数、支路距离介数和支路能力介数构成。

支路枢纽介数表征电网中经过支路e连通的发电—负荷节点对间功率传输路径数与电网中发电—负荷节点对间的功率传输路径总数的比值。支路枢纽介数越大,电网中经过支路e的发电—负荷节点对间的传输路径比例越大,该支路对于全网的枢纽作用越重要。

支路距离介数表征电网中经过支路e的发电—负荷节点对之间的路径的功率加权传输距离之和与电网中所有发电—负荷节点对间的功率传输路径的功率加权传输距离之和的比值。支路距离介数越大,电网中经过支路e的发电—负荷节点对间的传输路径距离规模越大,该支路对于全网的传输距离枢纽作用越重要。

支路能力介数表征电网中经过支路e的发电—负荷节点对之间路径的功率加权传输能力之和与电网中所有发电—负荷节点对之间的功率传输路径的功率加权传输能力之和的比值。支路能力介数越大,经过支路e的发电—负荷节点对间功率传输路径的传输能力越大,支路在全网的传输能力枢纽作用越重要。

支路枢纽介数、支路距离介数和支路能力介数分别按式(7)、式(8)、式(9)计算:

式中:bHe,bLe,bCe分别为支路e的枢纽介数、距离介数和能力介数;e为支路号;ne(m)为发电节点j与负荷节点k间的第m条功率传输路径是否经过支路e的标识,若经过支路e为1,否则为0。

2.3 指标归一化与节点和支路关键度综合指标

1)电网节点和支路指标的归一化

为增强节点指标之间和支路指标之间的可比性,需要对各个指标进行归一化。本文采用某一指标的计算值与该类指标的最大值之比作为归一化值,计算公式如下:

式中:vnor为某一节点或支路指标归一化后的值,反映了某一指标与该类指标的最大值的接近程度;v为指标原始值;vmax为该类指标所有原始值的最大值。

2)节点和支路关键度综合指标

电网节点i的关键度综合指标是该节点的归一化节点距离度、节点能力度、节点枢纽介数、节点距离介数和节点能力介数的加权和,用于辨识节点在电网结构和系统运行中的关键程度。节点度指标表征与节点相连支路的电气距离及容量,是从单独的节点角度衡量其重要性。节点介数指标表征节点参与组成的路径的数量、电气距离和容量,是从节点对整个电网功率传输的支撑作用的不同侧面衡量其重要性。这些指标是从不同侧面对节点在电网中的重要性进行评价,因而各指标间不存在冗余。节点关键度计算公式为:

式中:Ni为电网节点i的关键度综合指标;dLinor和dCinor分别为节点i的归一化距离度与能力度;bHinor,bLinor,bCinor分别为节点i的归一化枢纽介数、距离介数、能力介数;ω1至ω5为节点关键度综合指标的权重系数。

电网支路e的关键度综合指标是该支路归一化的支路枢纽介数、支路距离介数和支路能力介数的加权和,用于辨识支路在电网结构和系统运行中的关键程度。同样,支路关键度各子指标间也不存在冗余。支路的关键度计算公式如下:

式中:Be为电网支路e的关键度综合指标;bHenor,bLenor,bCenor分别为支路e的归一化枢纽介数、距离介数、能力介数;α1,α2,α3为支路关键度综合指标的权重系数。

对于包含多个子指标的综合指标,可以采用改进灰色关联度法[21]等方法来实现综合指标的加权系数计算,也可以根据电网规划人员或运行人员不同的关注重点来设置加权系数。为了分析各子指标对结果的影响程度,本文采用等权重设置方法,即设定每个综合指标的子指标相同的权重系数。

3 算例分析

3.1 IEEE典型算例分析

为说明本文方法的有效性以及评价方法,采用IEEE典型算例进行分析,并与其他文献中提出的算法进行对比分析。

1)关键节点辨识

以Matpower 5.1中的IEEE 30节点系统为例进行仿真,该系统共有6 台发电机、20 个负荷和41条线路。基于本文算法对其建模,其中通过潮流追踪可以解析出电源节点到负荷节点的功率传输路径有90条。

基于本文提出的节点关键度的综合评价指标计算得到的IEEE 30节点系统的节点关键度排序如图2所示。文献[22]提出了一种基于节点收缩后的网络凝聚度的节点重要度计算方法,利用节点收缩后的网络凝聚度评估节点重要度,用于骨架网络重构。将对比方法所计算得到的节点重要度进行归一化,与本文方法的对比如图2所示。

由对比图可知,本文方法与对比方法的评估结果呈现的趋势基本一致,在部分节点的关键度上有更好的区分效果。表1中进一步对比了两种方法针对IEEE 30节点系统的前8个最重要节点的排序结果。由表1可知,本文方法针对IEEE 30节点系统的前8个最重要节点的排序中有6个节点与对比方法结果相同,在表1中以红色数字标识,仅有少部分节点与对比方法评估结果存在差异,说明本文所述方法与对比方法对节点的重要性评价有共同之处。对比方法前5个最重要的节点6,10,12,4,27,均处于网络的中心位置,且分别有7,6,5,4,4条支路与其相连,可见该方法主要从节点在网络结构的作用来评价其重要性。本文既考虑节点本身的重要性,也从其对于整个电网完成功率输送的贡献(即参与组成的输电路径)来评价节点的重要性。因此,这5个节点对也在本文认为最重要的前8 个节点中,但排序有所不同。

本文方法与该方法存在差异的节点,如对于节点1,2,13,28的排序,两种方法的排序结果有较大出入,其成因分析如下:节点1,2,13均为发电机节点,处于网络结构的边缘且相连的支路不是很多,从网络角度来看,它们并不重要。但从表2可以看出,发电机节点1,2,13的有功出力都很大,参与组成的功率传输路径数很多,可见它们在完成电网最基本任务,即电能的供应与输送中的重要作用。节点28只参与构成了2条输电路径,且都是为节点8上的负荷供电,提供了负荷32.3%的功率,此外还有6条输电路径为节点8提供功率。因此,节点28对于电网整体而言其重要性有限。

从与文献[22]方法的对比中可以看出,本文方法能够考察节点在确保足够的功率供应以及完成功率的输送,即电网最基本任务中的重要作用。

2)关键支路辨识

以IEEE-RTS 24 节点系统[23]为例,该系统共有10台发电机、17个负荷和38条支路。基于本文算法对其建模,其中通过潮流追踪可以解析出电源节点到负荷节点的功率传输路径有101条。

基于本文提出的支路关键度的综合评价指标计算得到的IEEE-RTS 24节点系统的支路关键度排序如图3所示。文献[24]提出了一种利用源流路径电气剖分信息的网络支路脆弱度评估方法,该方法能够综合考虑网络结构和系统运行状态的影响。为了方便比较两种算法的结果,将对比方法所计算得到的支路重要度和脆弱度进行归一化,与本文方法的对比如图3所示。

可见,本文方法与对比方法计算得到的支路关键度结果趋势基本一致。表3进一步对比了本文方法与对比方法前15位关键支路的排序结果,其中有10条相同线路,在表3中以红色数字标识。

表4展示了各支路按支路枢纽介数排序对应的传输路径数以及潮流数据。从表4可知,本文所辨识出的关键度较高的支路不仅承担的输电任务较重,而且是多条输电路径的组成部分,如支路14-16和16-17。支路11-14,15-24,12-23,3-24,15-24 等是构成电源中心与负荷中心之间输电断面的关键支路,因而具有较高的重要性,对比方法也指出了这些支路是重要的联络线。对比方法采用的源流路径电气剖分与本文采用的潮流追踪有相似性,其定义的支路脆弱性为一条支路所有的剖分支路脆弱性的和,而一条剖分子支路的脆弱性正比于剖分子支路的阻抗、参与的输电路径的源流节点容量,以及对该支路容量极限的利用率。因此,对于参与多条输电路径的支路,其剖分子支路多,每个子支路的平均阻抗会较大,所以在评估其脆弱性时,会有比较大的值。这与本文在评估支路重要度时考虑支路参与组成的输电路径的数量、电气距离以及容量有一定的相似性,故而其评价的部分脆弱度比较高的支路也是很重要的支路。

但对于支路7-8,虽然输电任务比较重,但是只承担供给节点8上的负荷,对于整个电网范围的运行来说,重要性较低。而支路1-5,2-4,2-6等输电容量比较小,且只参与构成了少数输电路径,虽然脆弱性比较大,但它们重要性相对较低,这是由于本文侧重于从电网整体的角度评价支路在完成功率输送任务中的作用。本文与文献[24]采用了不同的方法解析输电路径,均考虑了支路在电网结构和运行两方面的作用,部分相似的结果,验证了本文所述方法能够有效评价支路对电网输送电能的支撑作用。由于侧重点不同,本文依据改进的复杂网络模型建立支路关键度评价模型,而文献[24]则更多地考虑支路的脆弱性,导致两者的评估结果有所差别。

3.2 某省级电网分析

选取某省级电网的某规划方案为算例进行计算分析,该方案共有1 665个节点(其中有170个发电节点和212个负荷节点)和2 196条支路。算例中共有7 个1 000kV节点,其中5 个地理上位于邻省,未计入表格数据中。用第1节的改进的复杂网络模型对其进行建模,通过潮流追踪可以解析出电源节点到负荷节点的功率传输路径有20 454条(至少提供负荷节点千分之一的功率)。节点关键度如图4所示,可见该省级电网中,比例较小的一部分节点具有很高的关键度。

对节点关键度进行分析可知,关键度大于0.1的节点有72 个,约占总节点数的4.32%,其中有1 000kV节点7个,500kV节点51个,220kV节点13个,110kV节点1个。关键度前50的节点包含所有的7个1 000kV节点,关键度前30的节点包含3个1 000kV节点,21 个500kV节点以及6个220kV节点,除去邻省3个1 000kV节点,省内前30个关键节点如表5所示。

对上述关键节点的辨识结果进行分析可以看出,关键节点普遍由电压等级较高,500kV及以上主网架的组成节点、重要的发电节点或是220kV网架中的枢纽节点构成。

支路关键度如图5所示,与节点关键度类似,一部分支路具有很高的关键度,且所占的比例不大,关键度大于0.1 的支路有261 条,约占总支路数的11.89%。

除去省间联络线后,该省电网支路关键度前15的支路如表6 所示,排名前15 的关键支路均为500kV及以上电压等级的线路或变压器支路。关键度排名前50的支路均表现出这一特点,且包含了全部1 000kV特高压线路或变压器支路。

从某省级电网的关键节点和支路的辨识结果中可以直观地看出,本文所提出的模型及辨识方法符合电网规划评价的一般规律。以节点为例,一般认为,电网中电压等级较高的环节较为重要,表5中大部分的结果与其相一致。但小部分评估结果并不完全遵循这一规律。例如:关键度排名前30的节点中包含6个220kV节点,作为各自网架中的核心枢纽节点,其重要性甚至超过了相当一部分电压等级更高的节点;关键度排序第57位的鄂咸丰110节点,虽然电压等级仅为110kV,但其通过架空线和变压器支路直接连接了12 个节点,其中包括两台出力100 MVA的发电机,流经该节点的潮流功率大,且输电覆盖范围广,该节点在该地区网架中承担了枢纽任务,因此关键度居前。

上述示例验证了所述模型算法能够胜任大型复杂电网中针对关键环节的辨识任务,且辨识结果合理,能够有效地定位电网的核心部分。

4 结语

在电网规模日益增大、耦合程度不断增强、复杂度不断增加的情形下,对电网整体特性进行分析和理解显得尤其重要,从复杂网络的角度进行分析是一种非常重要的方法。本文通过对功率传输路径、功率加权传输距离以及路径传输能力的定义,克服了以往电网复杂模型的功率沿最短路径传输的不合理假设,并综合考虑支路传输容量等电网实际物理特性,使得改进后的电网复杂网络模型更加符合电网基本电气规律,并能够满足实际运行约束。基于上述改进复杂网络模型,在节点和支路的度数和介数指标的基础上,建立了较为系统和完善的电网关键环节辨识模型。

基于所提出的电网关键环节辨识模型,对IEEE典型算例以及某省级电网进行的分析表明,电网中大部分电压等级较高的节点和支路关键度较高,但对于少数较低电压等级的节点和支路,其关键度超过了部分更高电压等级的节点和支路。这是由于所述模型综合考虑了节点和支路在整个电网结构中的枢纽作用、承担的功率传输任务,以及功率传输能力等因素,因而可较为准确地考察节点和支路在电网结构和系统运行中的关键程度,能够适应大型复杂电网的分析需求。

综上,本文对电网复杂网络模型的改进,使之更符合实际电网的物理特性,可以促进复杂网络理论在电力系统中的应用。所提出的电网关键环节辨识模型能够满足工程应用需要,帮助电网规划或运行人员直观地获知各个节点和支路的关键程度,确定网架中的核心枢纽节点和支路,为电网规划评价和运行分析提供决策支持。在此基础上,加强对这些关键节点和支路的重点监控和保护,将有助于减少大停电事故发生的概率,提升电网运行的安全稳定性。

摘要：为了更好地揭示电网复杂形态下的特性以及辨识可能触发电网大规模事故的关键环节,通过功率传输路径、功率加权传输距离、路径传输能力的定义对已有的电网复杂网络模型进行改进,使之符合电网基本电气规律和满足物理特性约束。进而基于改进的电网复杂网络模型建立了包含距离度、能力度、枢纽介数、距离介数和能力介数的电网关键节点和支路的评价指标集,使之能准确考虑节点和支路在电网结构和运行中的地位和作用。利用所述模型对IEEE典型系统以及某省级电网进行建模和关键环节辨识,取得了较好效果,并通过与现有方法的对比验证了算法的合理性与有效性。

复杂网络模型的弹性研究 第2篇

关键词：复杂网络模型,弹性,结构

1 概述

尽管网络的发展迅速, 每天都会有成千上万的网络服务器遭受攻击后受到干扰并关闭, 导致网络本身性能降低甚至是功能瘫痪。本文将弹性定义为其遭受攻击后节点和连接边的恢复, 并结合熵权算法, 最终能够实现对四种网络弹性能力进评。

2 复杂网络弹性指标定义

本文引入网络弹性连接和弹性恢复两项指标来定义网络弹性。两项指标结合熵权算法[1]反应出网络结构异质性, 在复杂网络的四种模型中, 每一种网络都有着不同的差异性[2]。

2.1 网络弹性连接。

在实际网络中, 网络遭受攻击情况分为蓄意攻击和随机攻击两大类。网络遭受攻击破坏后, 网络中剩余节点能够保持连通的能力, 称之为弹性连接。在两种攻击过程中, 蓄意攻击会选择网络度值较大的节点破坏, 去除最大的节点和其对应的边[3]。基于此, 本文选用的弹性连接指标为

式中:N表示初始网络规模;表示从该网络中去除的节点个数;C表示当节点被去除后网络中连通即能够正常通信节点个数。

2.2 网络弹性恢复。

现实网络中, 网络在遭受攻击后会通过某种措施连通。因此将受损网络的弹性恢复定义为:当网络中的部分节点遭到破坏后, 能通过某些简单的策略将消失的网络结构元素进行恢复的能力[4]。边和点两项弹性恢复能力定义为:

式中:D表示弹性恢复指标;E为边弹性恢复指标;表示通过某种措施恢复的节点个数;M表示网络初始中边数量。

3 典型网络结构

本文分别对规则网络、BA无标度网络和WS小世界网络进行弹性分析。

3.1 随机网络。ER随机网络模型是网络研究中最简单的网络模型, 它按照一定概率, N为网络规模, 边为n, 该网络弹性熵值为:

3.2 规则网络。

本文选取最近邻耦合网络, 该网络为典型规则网络, 网络中有N节点并围成一个环状, 且每个节点只与两边的k/2个邻居节点连接, 该网络结构熵:

3.3 BA无标度网络。

无标度网络是通过追踪万维网络而得出的网络模型, 具有幂率分布的网络形成机理。通过增长和择优连接, BA无标度网络的度分布函数, m为网络演化增长率, 无标度网络的弹性熵值为:

4 四种典型网络弹性仿真模拟

分别对规则网络、小世界网络、ER随机网络和BA无标度网络四种网络进行模拟, 并对三种网络熵值进行比较, 说明本文所提出网络弹性评价的有效性和可行性。实验中每个指标独立进行30次计算后取平均值, 以网络规模为500进行分析。网络恢复性指标D重连概率p从0.0002以补偿0.0002递增至0.1;其中无标度网络初始节点数为20, 增长率m从2以步长2递增至20。

4.1 网络弹性连接实验分析。

图1中反映出四种网络参数随网络节点破坏数目的增加而变化的情况, 对于随机网络, 网络的弹性连接能力在一定范围内下降很快, 通过增大网络密度可增大其弹性连接能力。

ER随机网络, 当网络密度小于0.3时, 网络弹性连接有明显好转, 其熵值几乎和近邻耦合网络的熵值相似。BA无标度网络随着攻击强度的增大, 网络弹性连接降低在某一区间内明显增高, 随着网络密度的增大, 其弹性连接也明显增强, 同时网络熵值反应出其异构性更强。小世界的熵值介于随机网络和规则网络之间。由于规则网络异构性并不明显, 所以其弹性连接能力不会遭到破坏。

4.2 网络弹性恢复实验分析。

对于ER随机网络, 网络密度较小, 当网络中去除节点数的增多, 其丢失节点得不到恢复。对于BA无标度网络, 网络去除节点数较少时可以得到恢复, 网络密度可以使网络恢复弹性得到增强。WS小世界网络, 当重连概率p增大, 节点弹性恢复则会有所提升, 若去除节点个数增加, 其网络平均度值k可以提升到规则网络弹性恢复。

5 结论

本文从“边”和“点”两个方面对四种典型网络进行弹性分析, 并将“边”和“点”恢复性引入弹性定义。实验仿真表明, ER随机网络对于恶性攻击的弹性要好于其他三种网络;BA无标度网络则更体现其节点的恢复能力增强, 熵值较小;由于影响WS小世界网络因素较多, 其熵值介于ER随机网络和规则网络之间, 网络弹性也表现的不如随机网络。当网络参数发生改变, 不同网络变化程度也有明显差异。本文定义的指标可以将不同网络的弹性进行对比, 同时通过熵算法对比四种网络差异性。在实验中, 不同参数所对网络模型的影响, 也是今后需要研究的内容。

参考文献

[1]谭跃进, 吴俊.网络结构熵及其在非标度网络中的应用[J].系统工程理论实践, 2004, 24 (6) :1-3.

[2]Cancho R F I, Sole R V.Optimization in complex networks[C].Lecture Notes in Physic, 2003, 625:114-126.

[3]杜巍, 蔡萌, 杜海峰.网络结构鲁棒性指标及应用研究[J].西安交通大学学报, 2010, 4.

复杂物流网络区间规划模型及算法 第3篇

随着物流行业及社会需求的不断发展, 商品的多元化、交换频率及流通周期的快速化趋势明显, 大规模的商品流通带来大规模的物流。物流网络呈现出多商品、多生产商、多层次流通节点、多需求用户特征, 受系统中需求关系的不确定性、流通成本的变化等各因素的影响, 物流网络的复杂性越显突出, 此类系统定义为复杂物流网络。其规划与设计是当前行业及学术界研究的热点问题之一, 针对复杂的物流网络系统, 如何设计各层次节点对间的配送需求、规划节点的决策等问题是保证整体系统运行效益及效率的关键, 也是重点研究领域。

Watts等[1]于1998年提出小世界网络概念以来, 复杂网络研究的重视性不断加大, 特别是在实际应用性行业, 如物流复杂网络系统。张纪会等[2]从系统工程的角度对复杂物流网络进行分析, 并对小型配送企业复杂物流系统进行设计;朱卫峰等[3,4]讨论了复杂物流系统的仿真设计问题, 构建多种控制策略下订货点量模型, 并进行算例仿真研究;卞文良等[5]构建了复杂物流网络的拓扑模型;覃儒展[6]等对复杂物流网络特性进行详细分析, 并提出模型构建的设想;秦进[7]等提出多级别的复杂物流配送网络设计模型, 设计算法并进行算例分析;文献[8]、[9]、[10]讨论不确定性环境下复杂物流网络设施选址模型及算法。

分析表明, 当前复杂物流网络设计的研究焦点集中于网络特征分析、基于随机与模糊规划的不确定性模型及算法等方面。本文拟设计一类复杂物流网络结构模型, 运用区间规划理念对不确定性问题展开分析, 以揭示复杂物流网络结构特性, 为复杂物流网络设计合理决策提供依据。

1 问题的描述

1.1 复杂物流网络结构

复杂物流系统是一个由若干个制造商、若干个批发商和若干个零售商组成的网状物流链[3]。

如图1设计一个复杂物流网络结构, 系统中:A1={A11, A12, , A1a}, 代表首层节点集, 共有a个节点;A2={A21, A22, , A2b}, 代表第二节点层共有b个节点;如此类推, 整个物流系统共有N个节点层, 最终节点层AN={AN1, AN2, , ANM}。

因此, 复杂物流网络结构特征可以描述如下:

(1) 多节点、多商品、多层次。上述网络结构中, 其节点层为Ai={A1, A2, , Ai, AN}, 对应物流网络中共有N个层次, 首层A1共有a个节点, 末层AN共有M个节点, 其他中间层, 都包含一定的节点数目, 因此, 可以看出复杂物流网络结构是一个多层次、多节点的决策选址问题, 同时在实际网络中, 各层次与节点间的可能包含多种物品的需求, 问题设计与求解的复杂性更为突出。

(2) 各层次节点间存在相互需求配送关系。传统复杂物流网络设计对网络需求特征往往考虑的是相邻层次间各节点的流向关系, 即在图1中表现为A (i-1) wAijA (i+1) t (1wW, 1tT) 的关系, 节点Aij仅与其上下游相邻层次A (i-1) 和A (i+1) 存在需求与流向关系。而在事实上, 多层次、多节点的复杂网络结构应该是一个递阶的层次节点对间需求关系, 从物流网络的流向结构体系上, 上游层次中节点与下游各层次各节点间都可能具备一定的需求。如A11AN1表示存在直接从首层第一个节点到末层第一个节点的物流配送业务。

1.2 区间不确定性物流网络设计

复杂物流网络设计是一项系统工程, 在当前物流行业快速发展时期, 受费用约束、需求变动、发展环境等诸多因素的影响, 该类问题求解的不确定性彰显突出。目前对于不确定性物流规划研究主要集中于应用随机数与模糊数解决不确定性问题。

区间规划[11]由Moore[12]于1959年提出, 是解决不确定性问题的重要手段之一。文献[13]、[14]、[15]分别对带区间数的优化规划问题进行讨论;文献[16]研究了区间线性双层规划模型的求解;文献[17]对目标系数与约束系数均为区间数的线性规划方程进行研究, 并应用于运输问题求解。文献[18]对不同情况下非线性规划目标函数与约束条件中不确定性参数出现的不同情况, 以区间参数标定并利用遗传算法具体求解。以区间数标度不确定性问题对实际应用问题物流规划研究并不多见。

区间物流网络是以区间数的形式来度量不确定性变量, 运用区间运算法则, 实现物流网络设计模型的确定性转化, 结合区间优化算法求解。区间数的表达形式为:

式中:XI区间变量x所在区间;x, xmin区间下界;x, xmax区间上界;x区间变量。

2 模型的构建

建立物流网络设计模型的一般思路为:定义各层次不同商品在节点对间的配量变量, 以网络配送费用、节点中转及存储成本、节点建设及运营成本等综合费用最小为目标函数, 在节点到发平衡的约束下建模求解。运用区间规划理论, 以区间数度量各变量的不确定性变动, 定义网络模型基本指标如下:

N复杂物流网络层数 (第一层表示节点层为最初生产商层, 第N表示节点层为终端用户层, 其他中间层) ;

K商品种类数 (1kK) ;

Wn第n (2nN-1) 层等待选择的节点数;

商品k从第n层第i个节点至第m层第j个节点的区间运输费率 (1nN-1, n+1mN) ;

商品k从第n层的第i个节点至第m层第j个节点的区间配量 (1nN-1, n+1mN) ;

商品k在第n层第i个节点区间单位中转存储成本;

通过第n层第i个节点商品k的区间配量;

Yni0-1决策变量, 若Yni=1, 表示第n层第i个节点被选择, 反之, 则不选择;

第n (2nN-1) 层第i个节点的区间建设及运作成本;

第n层第i个节点对商品k通过或存储区间能力;

Mn第n层最多允许选择的节点数目;

(aik) I最终用户i对商品k的区间需求量;

任意一个大的正数区间。

运用区间约束构建的网络设计模型如下:

模型中, 目标函数与约束条件均以区间费用度量, 其中:

和;

用;

本;

3 求解算法设计

3.1 模型的确定性转化

上述模型中, 各决策变量、辅助变量以及费率参数均为区间约束, 因此目标函数也是一个区间函数, 按照式 (1) 对区间数的定义, 模型中的变量可转化为:

由于物流网络设计是一个实际应用型问题, 上述规划模型中各决策变量、辅助变量以及费率参数都为非负约束, 且在模型中仅存在区间数的乘法运算法则, 如:

则有:

且

对于ZI中任意值Z, 定义风险系数a:

风险系数a表示因决策变量的不确定而使得目标函数求解值大于或等于Z的风险因子, 显然0a1。

等式变化后:

表明原有的目标函数可以确定性转化为:

此外, 考虑到模型中决策变量外还有参数 (Cijnmk) I, (Eink) I, (Fni) I区间会给决策变量的求解造成偏差, 给出相应的决策偏差约束:

dmax由决策者事先给定偏差控制范围。

则式 (2) 可以转化为:

同理, 相应的约束条件可以转化为:

3.2 优化求解算法设计

上述问题转变成为含0-1变量的混合整数规划模型, 由于模型中存在0-1变量Yni, 故问题演化为离散的非线性模型, 对模型的求解既包括随机优化搜索的求解策略, 还包括对0-1变量的决策。

由约束条件 (Xijnmk) IYniDI, 故定义一区间松弛变量 (sijnmk) I, 满足:

考虑求解全局优化性能和稳健性, 本文采用区间分层优化遗传算法求解。其基本思路为:定义上下两层的优化决策过程, 首先给出满足上层决策问题的初始解, 下层决策在该初始解环境下, 根据自身偏好在可能范围内优化自己的目标, 然后反馈到上层问题, 在上下两层最佳反应的基础上, 寻求整体问题的最优解。算法求解过程如下:

(1) 基本参数及变量编码, 采用区间编号模式, 即每个编码对应一个区间值集;

(2) 生成0-1变量Yni初始种群集, 利用Matlab中gaot工具箱随机生成Yni的初始解集U, (Yni) t∈U且为U中第t (1tu) 个解, 同时设定群体进化代数;

(3) 设定风险因子a、惩罚因子N≥0, 以及允许的最大偏差dmax>0。

(4) 构建适应度函数评价解集, 由于复杂物流网络设计的目标是使得总体成本最小, 故适应度函数以决策区间变量 (Xijnmk) I为确定区间情况下的成本最优函数, 即为式 (18) ;

(5) 将种群中所有 (Yni) t分配到下层计算单元; (6) 计算:

(7) 向上层单元反馈计算结果, 在候选解Zt (X, Y) 收到下层单元结果后计算:

(8) 计算综合目标函数:

(9) 保存至解为最优解为止;

10若已完成进化代数, 则转12, 否则继续;

11当代优化解的复制、交叉、变异等遗传操作, 产生新的种群, 转 (2) ;

21最优区间解输出;

13计算, 将式 (15) 代入目标问题, 得到一组新的值;

14误差检验, 若d (Z) =Zmax (X, Y) -Zmin (X, Y) dmax, 则终止运算, 否则令t=t+1, 转 (2) 。

4 算例分析

存在一个复杂物流网络结构:某企业要在一定区域内构建自身的物流配送网络体系, 其商品种类K=5, 网络层数N=4, 从商品配送起点至最终用户层各层包含的物流节点数目分别为Wn= (3, 4, 6, 5) , 各层的节点选择限制为Mn= (M2, M3) = (2, 3) , 各节点间的运输区间费率如图2。

图2中, 各边上区间标量为不同层次各节点间的区间运输费率, 由于商品种类不同, 其运输费率可能存在一定差异性, 本算例采取各商品综合区间费率;另外对其他变量区间约束如下:

U= (1t100) , 300代, 惩罚因子N=100, 在不同的风险因子a和最大偏差dmax下进行计算机仿真, 可得出如下结果:

表1的运算结果表明, 在区间约束下, 运用区间分层优化遗传算法对该算例求解, 在不同的情景状态下, 即定义不同风险因子a和最大偏差dmax所求最优解与节点决策存在一定的差异。如在情景a=0.2、dmax=100状态下, 系统中间层节点选择为 (A21, A23, A32, A33, A34) , 对应的系统最优区间目标值minZ=[9348.2, 9412.3];而在情景a=0.2、dmax=500状态下, 决策节点为 (A21, A23, A32, A33, A35) , 系统最优区间目标值minZ=[8936.6, 9233.5]。两种情景状态下模型求解的决策方案与系统最优目标存在一定差异。表明该方法具有区间最优解与情景决策的优越性, 其区间最优解反应由于物流网络需求的不确定性引发的目标值变动情况, 而决策方案的不同则取决于决策者事先的决策态度取向。

图3为在两种dmax定义模式下, 风险系数a与minZ的变化关系。当dmax固定时, 随着a的不断增大, 目标函数的区间下界Zmin与区间上界Zmax的计算值也是在不断增加, 表明决策的风险增加。同时对dmax=100与dmax=500两种状态下的结果比较可知, 随着dmax的增加, minZ的求解区间下界也在增加, 表明决策决策者若放宽不确定性变量对函数求解的影响程度, 其决策的选择机会相应增大。由此可见, 风险系数a与最大偏差dmax作为问题求解预设的两个参数, 对系统求解以及决策结果具有较大的影响。

5 结语

复杂物流网络规划与设计的不确定性影响变量多而杂, 且变动性较强, 易给系统决策带来较大影响。本文从区间规划的角度考虑多层次、多节点、多商品的复杂物流网络设计问题, 研究成果主要表现为:

(1) 描述了复杂物流网络的基本结构, 指出其层次节点对间的递阶需求特征, 并在规划模型中得以体现。

(2) 运用区间需求的形式标定物流网络需求的不确定性特征, 以区间数学度量不确定性变量与参数, 建立了复杂物流网络设计的区间规划模型。

(3) 设计区间两层优化遗传算法的求解模式, 并进行算例测试。结果表明该方法具有区间最优解与情景决策的优越性。

改进复杂网络模型 第4篇

关键词：病毒传播,复杂网络,无标度网络

当今社会中,手机已成为人类最主要的通讯手段。手机经历了从2G、2.5G的单纯收发短信息、接听电话时代发展到3G的集成便携电脑功能的时代的过程中,通过智能手机进行传播的病毒也随之产生和发展。手机病毒也是一种计算机程序,同样具有传染性和破坏性。其工作原理是因为存在于手机中的嵌入式操作系统(固化在芯片中的操作系统,一般由JAVA、C++等语言编写),相当于一个小型的智能处理器,容易遭受病毒攻击。而且,短信也不只是简单的文字,其中包括手机铃声、图片等信息,都需要手机中的操作系统进行解释,然后显示给手机用户,手机病毒就是靠软件系统的漏洞来入侵手机的。随着智能化手机越来越普及,手机病毒势必会成为继计算机病毒后的又一大威胁[1]。因此,为了防止手机病毒造成严重破坏后果,研究手机病毒传播特征及规律,有助于制定病毒防御策略及方法,预防以抑制手机病毒的传播[2,3]。本文应用复杂网络理论针对手机病毒的传播网络进行建模,通过仿真结果证明有效性及合理性,最后还提出了抑制智能手机病毒传播的几种策略。

1 背景知识

目前,随着手机用户数量的不断增加,手机的智能化程度也不断提高,智能手机(Smartphone)的硬件配置也越来越高,拥有更快的计算速度,更大的存储空间,一些新型的高端智能手机的配置已超过1999年个人计算机的配置。这也为手机病毒的传播和运行提供了必要条件。最早的手机病毒出现在2000年,该病毒通过西班牙电信公司“Telefonica”的移动系统向系统内的用户发送脏话等垃圾短信,事实上这类病毒最多只能被算作短信炸弹。真正意义上出现的具有实质破坏性的手机病毒是在2004年6月俄罗斯发现的,即“Cabir.a”病毒,这种名为“卡比尔”(Cabir)的病毒是一种网络蠕虫病毒,它不但可以感染运行Symbian操作系统的手机,还会通过蓝牙技术进行传播,如果病毒成功进入手机,就会在屏幕上显示“Caribe”字样,以后每次开机时都会出现该字样,电池会很快耗尽,蓝牙功能丧失,同时不断扫描正在使用蓝牙的手机,并复制自身副本发送过去。之后,手机病毒便开始泛滥。由于智能手机整合了IEEE 802.11和Bluetooth等网络技术,并提供多种数据连接方式,因此它也具备了恶意代码活动的硬件条件,随着智能手机使用者数量的增加,基于智能化手机传播的病毒势必会对手机系统的安全性造成严重威胁[2,3]。目前对于手机病毒传播的模型研究还处于初步阶段,已经提出的一些模型大多针对随机网络,不能很好的模拟实际网络环境,如何精确的描述手机病毒的传播行为,揭示其特性,找出对该行为有效的控制及防御的方法,将会成为未来的一个研究热点。

2 手机病毒传播网络模型

2.1 手机病毒传播模型选择

手机之间进行的是一对一的通信,手机使用者通过手机中所存储的联系人列表建立了一种社会关系网络。因此,手机病毒网络可以用图论进行建模。通过选择,建立合适并合理的手机病毒传播网络模型有助于更好的理解病毒的传播特性,为病毒的监控与防御提供解决思路。复杂网络理论下的几个典型的网络模型理论包括Erdos和Renyi提出的随机网络理论,Watts和Strogatz提出的小世界网络理论、以及Barabasi和Albert提出的无标度网络理论[4,5,6,7,8,9]。网络的度分布P(k)作为网络选择的一个重要指标,表示一个随机选定节点的度为k的概率。节点度服从幂律分布的网络叫做无标度网络(scale-free networks),P(k)～k-r,r为常数,这种节点度的幂律分布是网络的无标度特性。节点度服从幂律分布是指具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似表示。幂函数曲线是一条下降相对缓慢的曲线,这使得度很大的节点可以在网络中存在。随机网络和规则网络,度分布区间非常狭窄,几乎找不到偏离节点度均值较大的点。图1给出了具有10 000个节点,网络平均度为10同时在随机网络,小世界网络和无标度网络进行10次仿真取其平均值后对病毒传播的影响情况。

由图1所示,病毒在无标度网络上传播要快于在其他两个网络上的传播速度。另一方面,无标度网络节点度分布呈不均匀状态,除少数节点度很大,大多数节点的度都比较小。图2为一个包含了130个节点的无标度网络,其节点度服从幂指数为-3的幂律分布。图中的5个红色节点是网络中度最大的5个节点。图3给出了不同网络下已感染节点的平均度随时间变化的情况[5,7]。

由图2说明,无标度网络中节点度大的少数节点容易被感染病毒,也容易成为病毒的主要传播者。通过对无标度网络上病毒传播行为影响的研究发现,在无标度网络中,病毒的传播阈值明显要比在随机网络中小得多,这说明无标度网络更适合手机病毒的传播。尽管目前还缺乏实际的大量统计数据,但是通过小区域调查以及实际情况分析,手机病毒传播网络体现了无标度网络特性,本文就是基于手机病毒传播网络采用无标度网络拓扑来建立模型,并进行深入讨论的。

2.2 手机病毒传播网络模型的建立

手机病毒传播网络中,假设如果手机用户a在联系人列表中存有手机用户b的号码,那么手机用户b的联系人列表中同时也存有手机用户a的号码,这样,两个手机节点之间可以建立的是一条无向边,手机关系网络可以用一个无向非均衡图来表示,节点随着时间增加或者删除,边以非随机的方式连接到节点,这种增长模式可以用边以偏好依附规则增长的BA模型来表示。假设当一个手机用户在联系列表中存有较多联系人时,则有更大的可能建立一个新边(在联系人列表中增加联系人或者被其他手机用户加入联系人列表),即当一个人的社会关系比较广泛的时候,他就有更多的机会认识其他人,或者被其他人认识,该手机用户也有更大的机会将手机病毒传给其他用户,或者被其他手机所感染,这也体现出了无标度网络生长和优先连接的两个关键机制,网络初始状态含有m0个互连顶点的用户节点,每个时间步增加一个新的用户节点时,则该新节点连接到已含有m个节点的网络中。一个新的用户节点与网络中一个已经存在的节点i连接的概率Πi与节点i的连接度ki满足如下关系:Πi=$\frac{ki}{{\displaystyle \sum _{j}k}j}$。通过t次迭代后,会产生一个含有N=m0+t个节点,mt条边的无标度网络。

假设手机病毒传播网络中的节点只存在两种状态:易染状态(S)和已感染状态(I)。这里定义已感染状态的节点向与其有关联的手机节点发送病毒的概率为p0;一个易染状态节点收到含有病毒的信息后,点击该信息的概率为p1;初始概率p10由一个随机变量X产生,X-N(μp,σ${}_p^2$),初始变量的大小影响病毒的传播行为。一般的,如果一个手机节点第一次感染了某种病毒,那么手机用户以后再遇到含有此类病毒的信息或wap业务的时候,点击的概率就会越来越小,概率减小的幅度di与初始概率p10的选择有关,二者的关系可以用下面的等式表示:$d{}_i=\frac{2}{p{}_{10}}+\alpha$,其中α表示手机用户的安全意识因子,即衡量网络中用户的安全意识的平均水平,$\frac{2}{p{}_{10}}$表示p1的减小幅度与每个用户自身的安全意识关系。图4给出了di与p10之间的关系。

这里假设一个节点如果感染了病毒就会对此种病毒产生免疫性,不会再次被感染。初始概率大的节点可以加快病毒的传播,越容易被病毒感染,它的减小幅度越小;反之,初始概率小的节点病毒的感染会减慢,减小的幅度越大。一个已感染节点收到病毒信息并打开的概率p1k表示为:p1k=p10(1-di)k-1,k=0,1...。

2.3 手机病毒传播模型仿真分析

无标度网络初始时有m0=5个孤立点,加入一个节点的同时加入m=5条边,t=9 995,则此时网络中有N=10 000个节点。对于初始p1的选择采取同IM病毒传播时用户打开消息的相同概率,即p1由随机变量X-N(0.5,0.32)产生,X<0时,X=0;X>1时,X=1。最初时网络中有10个节点处于已感染状态,对p0取不同的值进行10次迭代并取平均值,其结果如图5所示。

如图5所示,处于已感染状态的手机,病毒直接向该手机中所存储的联系人列表中的号码继续发送含病毒的信息,即使是处于蓝牙环境下的蠕虫病毒需要对周围使用蓝牙手机进行搜索,由于范围有限,时间也不会很长,因此可以认为病毒从发送病毒消息到用户打开病毒消息的一次病毒传播的过程所经历的一个时间段△t很小;p0越大,则病毒的传播速度就会越快;p1由随机变量X-N(0.5,0.32)产生,所以节点的初始概率p10为0的概率应为:

${\rm P}\left\{X0\right\}=\phi \left(-0.5/0.3\right)=0.0475$,这说明网络中大约至少4.75%的用户不会感染病毒,而且手机用户接收到的含病毒的消息次数越多,p1的取值会越来越小,因此不会出现整个网络中的所有节点均被感染的情况。

安全意识因子α用于描述网络中的手机用户对于手机病毒的防御意识的能力。α取值越高,手机用户对于病毒的防御意识则越强,因而病毒的传播速度和范围也会越小。图5显示了不同取值的α仿真10次取平均值的对于病毒传播的影响结果。

由图6可以发现α的取值不同,在最初一定的时间范围内对于病毒的传播速度是有较明显的抑制作用,但是最终几乎都右相同的时间内完成了病毒的传播。所以仅仅采取提高用户的安全意识来抑制病毒传播是无法实现的。

4 结语

手机病毒是日渐兴起的一种新的病毒,随着手机智能化程度的不断提高,通过手机传播的病毒的严重程度及破坏程度将不亚于甚至超过计算机病毒。本文以智能手机病毒的传播为研究对象,研究了其传播过程中的复杂网络特征,同时探讨了应用复杂网络理论建立手机病毒的传播网络模型,定义了病毒感染速率、易染概率、减小幅度因子、安全意识因子等,分析了各个量对于模型的影响,实证表明,智能手机病毒传播服从度分布幂律分布和无标度分度,无标度网络应用于手机病毒传播网络模型的具有合理性。本模型只考虑了网络节点只有已感染和易感染的两种状态存在的理想情况,对于更复杂的节点情况的传播规律问题的探索,将在接下来的工作中继续进行。

参考文献

[1]May R M,Lloyd A L.Infection dynemics on scale-free net-works.Phasical Review E,2001;64(6):66—112

[2]Moteno Y,Pastor S R,Vespignani A.Epidemic outbreaks in complex heterogeneous networks.European Physical Journal B,2002;26(4):521—529

[3]Wen W P,et al.Research and Development of Internet worms.Journal of Alexandria,USA,2006;9—16

[4]Newman M E J.The Structure and function of complex networks.SLAMReview,2003;45(2):167

[5]Albert R,Barabasi A L.Statistical mechanics of complex networks.Reviews of Modern Physics,2002;74(1):47

[6]Erdos P,Renyi A.On the evolution of random graphs.Publ Math Inst Hung Acad Sci,1959;5:17—60

[7]Albert R,Barabasi A L.Statistical emergence of scaling in random networks.Science,1999;286:509—512

[8]Watts D J,Strogatz S H.Collective Dynamics of“small-world”net-works.Nature,1999;393(6684):440

基于泊松过程的供应链复杂网络模型 第5篇

关键词：复杂网络,供应链,出强度,入强度,有向含权网络

长期以来, 供应链管理的研究方法大多采取基于系统动力学、基于经典运筹学的数学规划方法, 采取的模型大多是单链型的上下游企业结构[1], 而且模型结构大多固定不变, 然而, 随着经济全球化、网络技术、电子商务的发展, 供应链的形式越来越复杂, 供应链的结构也不断动态演化, 呈现出复杂网络的特征, 传统的数学解析方法无法对供应链系统的复杂动态本质进行描述, 如何在更为接近实际的供应链网络模型基础上进行研究是急需解决的问题之一。 利用复杂网络的理论和方法对供应链网络进行研究有助于弥补传统的数学解析方法的不足, 有助于从系统的角度对供应链的整体运行规律和网络动态生长演化规律进行探讨。

1 研究现状

随着供应链管理思想的发展以及复杂网络方法日益受到学术界的关注, 基于复杂网络的方法对供应链进行研究的成果也趁日益增长的趋势。在国外, Thomas Y.Choi等 (2001) 首次提出从复杂适应系统角度对供应链网络进行研究, 探讨了将供应链网络视作复杂适应系统的必要性[2]; Dirk Helbing (2006) 首次提出供应链管理中的“牛鞭效应”与供应链网络本身的拓扑结构有关[3]; Christian Kuhnert等 (2006) 发现城市的物资供应网络服从无标度分布[4]; Marco Laumanns等 (2006) 建立了一个供应链有向网络, 用鲁棒最优控制方法实现供应链的最优化目标[5]; S.D.Pathak等 (2007) 对该方法在供应链网络研究中的应用进行了总结, 指出在供应链管理研究中加入复杂网络理论进行研究的有用性[6]。在国内, 郭进利 (2006) 针对供应链的有向网络进行了一系列的研究, 提出了G有向模型, 研究表明网络的稳态平均入度分布和稳态平均出度分布表现为幂律分布[7]; 高蕾 (2011) 通过分析网络节点的产生、衰亡及退出状况, 建立了一种择优连接模型以描述其演化过程[8]。但是上述众多模型的不足之处在于采用的是无权网络, 忽视了供应链网络权重的重要性。在采用有权网络对供应链网络进行研究的成果中, 于海生等 (2009) 将加权网络演化理论引入到供应链网络领域, 提出了基于交易量的供应链网络演化模型[9];宋思颖 (2010) 基于交易量构建了成品油供应链加权网络并进行了实证研究[10]。但是这些有权供应链模型没有考虑连接的方向性, 然而, 供应链网络中方向性代表了物质的流向, 反应了企业之间销售和采购的关系, 也是供应链网络中必不可缺的要素。总而言之, 复杂网络理论目前在经济管理领域比如供应链管理的领域的应用还相对较少, 现有研究的不足之处主要体现在以下几个方面:

①在采用复杂网络方法的过程中, 偏重物理学角度的复杂网络理论, 没有深入地揭示供应链自身的特点。比如Dirk Helbing关于“牛鞭效应”的研究。

②同时考虑权重和方向的模型比较少。交易量和方向性都是供应链网络中的重要要素, 交易量反应了节点企业在供应链网中的地位, 交易量越大, 说明节点企业在网络中的地位越重要, 而方向性代表了物质的流向, 反应了节点企业之间销售和采购的关系, 因此在建立供应链网络模型的过程中有必要同时考虑权重和方向, 建立供应链有向含权网络。

③大部分模型考虑的都是节点等时间间隔增长的情况, 而在现实供应链网络中, 新企业的加入时间是随机的, 并不是等时间间隔。郭进利在其研究中发现Barabási等[11]在对BA模型进行分析的过程中假定了节点等时间间隔进入系统和节点到达时间服从均匀分布, 于是便对Barabási等关于BA模型的分析的缺陷进行了论证[12], 因此沿用BA模型关于节点等时间间隔进入系统的假设将无法反映供应链网络增长的真实情况。

为了从多个角度更真实地反映供应链网络变化的机制, 本文将综合如下特征以建立更接近实际的供应链网络模型:①供应链网络是有向网络有权网络, 权重反映节点企业之间的交易量, 方向反映节点企业之间的销售供应关系;②加入供应链网络的企业数量服从泊松分布, 即企业将不再以等时间间隔的方式加入网络;③引入相互影响的拓扑增长与边权耦合同步机制, 当新企业加入供应链网络或者供应链网络中的企业退出时将导致边权发生变化, 边权的变化将影响择优选择的概率, 从而对网络拓扑结构产生影响;④进入网络的新节点具有入边和出边。

2 定义

为了明确区分节点强度分布和网络强度分布的概念, 首先给出相关定义。供应链网络g为有向含权网络, V为g的点集, 有向边〈i, j〉反映了节点企业i供应物资给节点企业j, wij为有向边〈i, j〉的权重, 反映了节点企业i与j之间的交易量。VIi为所有指向节点i的节点集合, VOi为所有i指向的节点集合, KIi为节点i的入度, KOi为节点i的出度, SIi为节点i的入强度, $S{\rm I}{}_i={\displaystyle \sum _{j\in V{\rm I}{}_i}w}{}_{ji}‚S{\rm O}{}_i$为节点i的出强度, $S{\rm O}{}_i={\displaystyle \sum _{j\in V{\rm O}{}_i}w}{}_{ij}.{\rm N}(t)$表示网络在t时刻的节点个数, N (t) 是一个随机过程, E (N (t) ) 为网络在t时刻的节点平均数。

定义1 节点i的瞬态入强度分布为P{SIi (t) =s} (其中s≥0) , 表示节点i在t时刻的入强度等于s的概率。节点i的瞬态出强度分布为P{SOi (t) =s} (其中s≥0) , 表示节点i在t时刻的出强度等于s的概率。

定义2 当极限$\underset{t\infty }{{\displaystyle \lim }}{\rm P}\{S{\rm I}{}_i(t)=s\}$存在, s≥0 且${\displaystyle \sum _{s=0}^{\infty }\underset{t\infty }{{\displaystyle \lim }}}{\rm P}\{S{\rm I}{}_i(t)=s\}=1\text{时}‚$称极限$\underset{t\infty }{{\displaystyle \lim }}{\rm P}\{S{\rm I}{}_i(t)=s\}$为节点i的稳态入强度分布, 记为P{SIi=s}。当极限$\underset{t\infty }{{\displaystyle \lim }}{\rm P}\{S{\rm O}{}_i(t)=s\}$存在, s≥0且${\displaystyle \sum _{s=0}^{\infty }\underset{t\infty }{{\displaystyle \lim }}}{\rm P}\{S{\rm O}{}_i(t)=s\}=1$时, 称极限$\underset{t\infty }{{\displaystyle \lim }}{\rm P}\{S{\rm O}{}_i(t)=s\}$为节点i的稳态出强度分布, 记为P{SOi=s}。

定义3 称${\rm P}\{S{\rm I}(t)=s\}=\frac{1}{E[{\rm N}(t)]}{\displaystyle \sum _{i\in V(t)}{\rm P}}\{S{\rm I}{}_i(t)=s\}$为网络在时刻t的瞬态平均入强度分布。称${\rm P}\{S{\rm O}(t)=s\}=\frac{1}{E[{\rm N}(t)]}{\displaystyle \sum _{i\in V(t)}{\rm P}}\{S{\rm O}{}_i(t)=s\}$为网络在时刻t的瞬态平均出强度分布。

定义4 如果极限$\underset{t\infty }{{\displaystyle \lim }}{\rm P}\{S{\rm I}(t)=s\}$存在, 且${\displaystyle \sum _{s=}^{\infty }\underset{t\infty }{{\displaystyle \lim }}}{\rm P}\{S{\rm I}(t)=s\}=1‚$则称极限$\underset{t\infty }{{\displaystyle \lim }}{\rm P}\{S{\rm I}(t)=s\}$为网络的稳态平均入强度分布, 记为P{SI=s}。如果极限$\underset{t\infty }{{\displaystyle \lim }}{\rm P}\{S{\rm O}(t)=s\}$存在, 且${\displaystyle \sum _{s=}^{\infty }\underset{t\infty }{{\displaystyle \lim }}}{\rm P}\{S{\rm O}(t)=s\}=1$, 则称极限$\underset{t\infty }{{\displaystyle \lim }}{\rm P}\{S{\rm O}(t)=s\}$为网络的稳态平均出强度分布, 记为P{SO=s}。

3 模型描述

中国科技大学复杂系统研究小组提出的TDE模型[13]引入相互影响的拓扑生长和强度耦合同步机制, 所得的网络特性比较接近实际, 不仅网络度分布、网络强度分布以及网络权重分布均为幂律分布, 而且获得了高聚集性和非相称混合性的特征, 成功地刻画了真实技术网络的无尺度性质和小世界效应。本文将引入TDE模型的拓扑生长和强度耦合同步机制建立供应链复杂网络模型。

(1) 初始。

网络g初始由较少的m0个节点组成的BA网络, 节点之间有向边的初始权值为w0.

(2) 增长。

每个时间步新增节点数服从参数为λ的泊松过程, 每个新节点带有m条有向边连接到m个不同的网络中已经存在的节点 (mm0) , 其中新节点的入边数服从二项分布B (m, p) , 出边数服从二项分布B (m, 1-p) , p∈ (0, 1) 。新边的初始权重为w0.

(3) 择优连接。

复杂网络中的强度指标反映了供应链企业在网络中的交易量大小, 强度越大的企业在供应链网络中越处于核心位置, 越容易吸引其他企业与之合作, 在网络的演化中将采取与TDE模型相同的以强度为基础的择优规则。由于新节点的m条边连接到网络具有方向性, 所以择优连接的概率分为以下两种情况:

①当选择网络中已有的节点i为终点时, 选择i的概率Π1依赖于i的入强度

$\Pi {}_1=\frac{S{\rm I}{}_i}{{\displaystyle \sum _{j\in V}S}{\rm I}{}_j}(1)$

②当选择网络中已有的节点i为起点时, 选择i的概率Π2依赖于i的出强度

$\Pi {}_2=\frac{S{\rm O}{}_i}{{\displaystyle \sum _{j\in V}S}{\rm O}{}_j}(2)$

(4) 权值动态演化。

网络每次新增一个节点时网络中的流量会产生变化以适应流量增长, 由于本模型是有向模型, 而TDE模型的边权更新机制时建立在无向网络的基础上, 因此有必要对TDE模型的边权更新机制进行相应的修正, 所有可能的 (存在或者尚未存在) 连边的权重均参照如下边权耦合机制进行更新。

$w{}_{ij}=\{\begin{array}{cc}w{}_{ij}+w{}_0,& \text{以}\text{概}\text{率}Wp{}_{ij}\\ w{}_{ij},& \text{以}\text{概}\text{率}1-Wp{}_{ij}\end{array}(3)$

其中:$p{}_{ij}=w{}_{ij}/{\displaystyle \sum _{a,b}w}{}_{ab}‚W={\displaystyle \sum _{i,j}\Delta }w{}_{ij}$, 反应了网络中边权的总增量, 且W≥m.若节点i与节点j不相连, 则wij=0。若Wpij>1, 则令Wpij=1。

4 解析过程

在模型演化的过程中, 不允许出现自连边, 也不允许出现重复边, 只是相应地增加边权值。在分析的过程中, 令w0=1。 N (t) 为t时刻网络的节点总数, 令N (t) =a (t) +m0.

由于节点的到达过程是具有参数λ的泊松过程, 由泊松过程理论[14,15]可知, 在[0, t]内到达网络的节点的平均数为λt, 即到t时刻平均有λt个节点添加到网络, 则:

$E(a(t))=\lambda t(5)$

网络中的每一个节点以它进入网络的时间先后顺序来定义, 即第i个节点是指在第i个时间步长进入网络的节点, ti为第i个节点进入网络的时刻, wij (t) 为时刻t有向边〈i, j〉的权值, wji (t) 为时刻t有向边〈j, i〉的权值, SIi (t) 表示时刻t第i个节点的入强度, SOi (t) 表示时刻t第i个节点的出强度。

4.1 入强度分析

假设wji (t) 、SIi (t) 为一连续实变量, 则从式 (5) 得到wji (t) 的变化率为:

$\begin{array}{l}\frac{dw{}_{ji}(t)}{dt}\\ =[(w{}_{ji}+1)Wp{}_{ji}+w{}_{ji}(1-Wp{}_{ji})-w{}_{ji}]\lambda \\ =\lambda Wp{}_{ji}\\ =\lambda W\frac{w{}_{ji}}{{\displaystyle \sum _{a,b}w}{}_{ab}}\end{array}(6)$

当有新节点进入网络时会引起节点入强度的变化, 对于节点i的入强度SIi (t) 来说, 它的增加既可以是因为一个新增的结点选择i为终点建立连接, 也可以是因为以结点i为终点的有向边〈j, i〉的权重根据式 (3) 发生了更新。 因此, 节点i的入强度SIi (t) 满足如下动态化方程:

$\frac{dS{\rm I}{}_i(t)}{dt}=\frac{(1-p)m\lambda S{\rm I}{}_i(t)}{{\displaystyle \sum _{y}S}{\rm I}{}_y(t)}+{\displaystyle \sum _{j\in V{\rm I}{}_i}\lambda }W\frac{w{}_{ji}}{{\displaystyle \sum _{a,b}w}{}_{ab}}(7)$

因为${\displaystyle \sum _{a,b}w}{}_{ab}={\displaystyle \sum _{y}S}{\rm I}{}_y‚{\displaystyle \sum _{y}S}{\rm I}{}_y(t)\approx (m+W)t\lambda$, 所以

$\frac{dS{\rm I}{}_i(t)}{dt}=\frac{[(1-p)m+W]S{\rm I}{}_i(t)}{(m+W)t}(8)$

令$A=\frac{(1-p)m+W}{m+W}$, 则上式转换为如下形式:

$\frac{dS{\rm I}{}_i(t)}{dt}=\frac{AS{\rm I}{}_i(t)}{t}(9)$

由于节点i在ti时刻进入网络的入强度为SIi (ti) , 则解方程 (9) 得

$S{\rm I}{}_i(t)=\frac{S{\rm I}{}_i(t{}_i)}{t{}_i^A}t{}^A(10)$

则:

$\begin{array}{l}{\rm P}(S{\rm I}{}_i(t)<s)\\ ={\rm P}(\frac{S{\rm I}{}_i(t{}_i)}{t{}_i^A}t{}^A<s)\\ ={\rm P}(t{}_i>(\frac{S{\rm I}{}_i(t{}_i)}{s}){}^{1/A}t)\\ ={\displaystyle \sum _{l=0}^m{\rm P}}\{S{\rm I}{}_i(t{}_i)=l\}{\rm P}\{t{}_i>(\frac{S{\rm I}{}_i(t{}_i)}{s}){}^{1/A}t|S{\rm I}{}_i(t{}_i)=l\}\\ ={\displaystyle \sum _{l=0}^{m}C}{}_m^{l}p{}^l(1-p){}^{m-l}{\rm P}\{t{}_i>(\frac{l}{s}){}^{1/A}t\}\end{array}(11)$

因为节点到达过程是具有参数λ的泊松过程, 根据Poisson过程理论[14,15], 节点的到达时间ti服从Γ分布, 即${\rm P}(t{}_{i}x)=1-\exp (-\lambda x){\displaystyle \sum _{l=0}^{i-1}\frac{(\lambda x){}^l}{l!}}$, 则

$\begin{array}{l}{\rm P}(S{\rm I}{}_i(t)<s)\\ ={\displaystyle \sum _{l=0}^{m}C}{}_m^{l}p{}^l(1-p){}^{m-l}{\rm P}\{t{}_i>(\frac{l}{s}){}^{1/A}t\}\\ ={\displaystyle \sum _{l=0}^m[}C{}_m^{l}p{}^l(1-p){}^{m-l}\cdot \exp [-\lambda (\frac{l}{s}){}^{1/A}t]\\ \cdot {\displaystyle \sum _{j=0}^{i-1}\frac{[-\lambda (\frac{l}{s}){}^{1/A}t]{}^j}{j!}}]\end{array}(12)$

根据定义1, 节点i的瞬态入强度分布为:

$\begin{array}{l}{\rm P}(S{\rm I}{}_i(t)=s)\\ =\frac{\partial {\rm P}(S{\rm I}{}_i(t)<s)}{\partial s}\\ =(\frac{\lambda t}{A})(\frac{1}{s}){}^{1+1/A}\\ \cdot {\displaystyle \sum _{l=0}^m[}C{}_m^{l}p{}^l(1-p){}^{m-l}\frac{\exp [-\lambda (\frac{l}{s}){}^{1/A}t]\cdot [\lambda (\frac{l}{s}){}^{1/A}t]{}^{i-1}l{}^{1/A}}{(i-1)!}]\end{array}(13)$

根据定义2, 节点i的稳态入强度分布为:

$\begin{array}{l}{\rm P}(S{\rm I}{}_i=s)\\ =\underset{t\infty }{{\displaystyle \lim }}(\frac{\lambda t}{A})(\frac{1}{s}){}^{1+1/A}\\ \cdot {\displaystyle \sum _{l=0}^m[}C{}_m^{l}p{}^l(1-p){}^{m-l}\frac{\exp [-\lambda (\frac{l}{s}){}^{1/A}t]\cdot [\lambda (\frac{l}{s}){}^{1/A}t]{}^{i-1}l{}^{1/A}}{(i-1)!}]\\ =0\end{array}(14)$

根据定义3, 网络的瞬态平均入强度分布为:

$\begin{array}{l}{\rm P}(S{\rm I}(t)=s)\\ =\frac{1}{E[{\rm N}(t)]}{\displaystyle \sum _{i\in V(t)}{\rm P}}(S{\rm I}{}_i(t)=s)\\ =\frac{1}{m{}_0+\lambda t}{\displaystyle \sum _{i\in V(t)}[}(\frac{\lambda t}{A})(\frac{1}{s}){}^{1+1/A}\\ \cdot {\displaystyle \sum _{l=0}^m[}C{}_m^{l}p{}^l(1-p){}^{m-l}\frac{\exp [-\lambda (\frac{l}{s}){}^{1/A}t]\cdot [\lambda (\frac{l}{s}){}^{1/A}t]{}^{i-1}l{}^{1/A}}{(i-1)!}]]\end{array}(15)$

根据定义4, 网络的稳态平均入强度分布为:

$\begin{array}{l}{\rm P}(S{\rm I}=s)\\ =\underset{t\infty }{{\displaystyle \lim }}{\rm P}(S{\rm I}(t)=s)\\ \approx \underset{t\infty }{{\displaystyle \lim }}\{\frac{1}{\lambda t}{\displaystyle \sum _{i=1}^{\infty }(}\frac{\lambda t}{A})(\frac{1}{s}){}^{1+1/A}\\ \cdot {\displaystyle \sum _{l=0}^m[}C{}_m^{l}p{}^l(1-p){}^{m-l}\frac{\exp [-\lambda (\frac{l}{s}){}^{1/A}t]\cdot [\lambda (\frac{l}{s}){}^{1/A}t]{}^{i-1}l{}^{1/A}}{(i-1)!}]\}\\ =\underset{t\infty }{{\displaystyle \lim }}\{\frac{1}{As{}^{1+1/A}}{\displaystyle \sum _{l=0}^{m}C}{}_m^{l}p{}^l(1-p){}^{m-l}l{}^{1/A}\exp [-\lambda (\frac{l}{s}){}^{1/A}t]\\ \cdot {\displaystyle \sum _{i=1}^{\infty }\frac{[\lambda (\frac{l}{s}){}^{1/A}t]{}^{i-1}}{(i-1)!}}\}\\ =\frac{1}{As{}^{1+1/A}}{\displaystyle \sum _{l=0}^m[}C{}_m^{l}p{}^l(1-p){}^{m-l}l{}^{1/A}]\end{array}(16)$

4.2 出强度分析

假设wij (t) 、SOi (t) 为一连续实变量, 则从式 (5) 得到wij (t) 的变化率为:

$\begin{array}{l}\frac{dw{}_{ij}(t)}{dt}=[(w{}_{ij}+1)Wp{}_{ij}+w{}_{ij}(1-Wp{}_{ij})-w{}_{ij}]\lambda \\ =\lambda Wp{}_{ij}=\lambda W\frac{w{}_{ij}}{{\displaystyle \sum _{a,b}w}{}_{ab}}(17)\end{array}$

与入强度分析过程类似, 节点i的出强度SOi (t) 的增加既可以是因为一个新增的结点选择i为起点建立连接, 也可以是因为以结点i为起点的有向边〈i, j〉的权重根据式 (3) 发生了更新。 因此, 节点i的出强度SOi (t) 满足如下动态化方程:

$\frac{dS{\rm I}{}_i(t)}{dt}=\frac{pm\lambda S{\rm O}{}_i(t)}{{\displaystyle \sum _{y}S}{\rm O}{}_y(t)}+{\displaystyle \sum _{j\in V{\rm O}{}_i}\lambda }W\frac{w{}_{ij}}{{\displaystyle \sum _{a,b}w}{}_{ab}}(18)$

根据入强度的分析过程, 同理可得如下有关出强度的指标。

节点i的出强度为:

$S{\rm O}{}_i(t)=\frac{S{\rm O}{}_i(t{}_i)}{t{}_i^B}t{}^B(19)$

其中, $B=\frac{pm+W}{m+W}.$

节点i的瞬态出强度分布为:

$\begin{array}{l}{\rm P}(S{\rm O}{}_i(t)=s)\\ =(\frac{\lambda t}{B})(\frac{1}{s}){}^{1+1/B}\\ \cdot {\displaystyle \sum _{l=0}^m[}C{}_m^l(1-p){}^l(p){}^{m-l}\frac{\exp [-\lambda (\frac{l}{s}){}^{1/B}t]\cdot [\lambda (\frac{l}{s}){}^{1/B}t]{}^{i-1}l{}^{1/B}}{(i-1)!}]\end{array}(20)$

节点i的稳态出强度分布为:

$\begin{array}{l}{\rm P}(S{\rm O}{}_i=s)\\ =\underset{t\infty }{{\displaystyle \lim }}(\frac{\lambda t}{B})(\frac{1}{s}){}^{1+1/B}\\ \cdot {\displaystyle \sum _{l=0}^m[}C{}_m^l(1-p){}^l(p){}^{m-l}\frac{\exp [-\lambda (\frac{l}{s}){}^{1/B}t]\cdot [\lambda (\frac{l}{s}){}^{1/B}t]{}^{i-1}l{}^{1/B}}{(i-1)!}]\\ =0\end{array}(21)$

网络的瞬态平均出强度分布为:

$\begin{array}{l}{\rm P}(S{\rm O}(t)=s)\\ =\frac{1}{E[{\rm N}(t)]}{\displaystyle \sum _{i\in V(t)}{\rm P}}(S{\rm O}{}_i(t)=s)\\ =\frac{1}{m{}_0+\lambda t}{\displaystyle \sum _{i\in V(t)}[}(\frac{\lambda t}{B})(\frac{1}{s}){}^{1+1/B}\\ \cdot {\displaystyle \sum _{l=0}^m[}C{}_m^l(1-p){}^l(p){}^{m-l}\frac{\exp [-\lambda (\frac{l}{s}){}^{1/B}t]\cdot [\lambda (\frac{l}{s}){}^{1/B}t]{}^{i-1}l{}^{1/B}}{(i-1)!}]]\end{array}(22)$

网络的稳态平均出强度分布为:

$\begin{array}{l}{\rm P}(S{\rm O}=s)\\ =\underset{t\infty }{{\displaystyle \lim }}{\rm P}(S{\rm O}(t)=s)\\ \approx \underset{t\infty }{{\displaystyle \lim }}\{\frac{1}{\lambda t}{\displaystyle \sum _{i=1}^{\infty }(}\frac{\lambda t}{B})(\frac{1}{s}){}^{1+1/B}\\ \cdot {\displaystyle \sum _{l=0}^m[}C{}_m^l(1-p){}^l(p){}^{m-l}\frac{\exp [-\lambda (\frac{l}{s}){}^{1/B}t]\cdot [\lambda (\frac{l}{s}){}^{1/B}t]{}^{i-1}l{}^{1/B}}{(i-1)!}]\}\\ =\underset{t\infty }{{\displaystyle \lim }}\{\frac{1}{Bs{}^{1+1/B}}{\displaystyle \sum _{l=0}^{m}C}{}_m^l(1-p){}^{l}p{}^{m-l}l{}^{1/B}\exp [-\lambda (\frac{l}{s}){}^{1/B}t]\\ .{\displaystyle \sum _{i=1}^{\infty }\frac{[\lambda (\frac{l}{s}){}^{1/B}t]{}^{i-1}}{(i-1)!}}\}\\ =\frac{1}{Bs{}^{1+1/B}}{\displaystyle \sum _{l=0}^m[}C{}_m^l(1-p){}^{l}p{}^{m-l}l{}^{1/B}]\end{array}(23)$

从上述解析过程来看, 该网络的节点稳态入强度分布和节点稳态出强度不存在, 但是网络的稳态平均入强度分布和稳态平均出强度存在, 并且满足幂律分布, 即:

P (SI=s) ～s-γ, 幂律指数$\gamma =1+\frac{1}{A}=1+\frac{m+W}{(1-p)m+W}‚\gamma$的取值在[2,3]之间;

P (SO=s) ～s-ω, 幂律指数$\omega =1+\frac{1}{B}=1+\frac{m+W}{pm+W}‚\omega$的取值在[2,3]之间。

5 仿真结果

针对上文模型, 通过数值仿真检验模型节点的幂律特性。

图1、图2分别给出了λ=2、m=4、w=6、p=0.6、t=2000时的网络稳态平均出入强度的仿真值与解析估计值, 图3、图4分别给出了λ=2、m=4、w=8、p=0.6、t=2000时的网络稳态平均出入强度的仿真值与解析估计值, 从两组仿真结果可以看出, 该供应链复杂网络演化模型呈现出较明显的幂律特性, 并且仿真结果与解析估计值也比较吻合。

6 结论

本文在建立供应链复杂网络模型时考虑了方向性和权重, 在节点增长的机制上采取了泊松增长, 使模型能更真实地反映供应链网络实际增长的情况, 解析结果表明该模型的节点稳态出入强度不存在, 但网络稳态平均出入强度服从幂律分布。 模型在演化机制中仅仅考虑了节点增长的情况, 没有考虑节点退出、老节点互联等情况, 在今后的工作中可以在这几个方面对模型进行逐步修正和改进, 使其能够更好地刻画现实世界中的供应链复杂网络。

改进复杂网络模型 第6篇

1 基于模糊神经网络的故障诊断模型

一般而言,基于模糊神经网络模糊系统诊断模型由监控系统、神经网络系统和故障诊断分析输出系统组成,如图1所示。其中,监控系统用于数据的有效获取;神经网络系统用于故障的诊断,故障诊断分析输出系统用于系统的告警和输出。M1是测量的直接和间接测量的观测数据,并且作为神经网络系统的输入。N1是通过神经网络方法诊断的故障。M2直接或间接测量的观测值,是故障诊断分析系统的部分直接输入。

1.1 诊断方法

首先,将从数字传感器得到的离散输入进行归一化数据处理,并且通过为系统语言变量定义的友规则进一步模糊化。其次,网络模型结构包含一个与状态变量(温度、压力、热容量或者流速)相应的输入节点、隐藏节点,与偏离规格(高、低)和一般状况相对应的输出节点。第三,该模型假设计算机能够监控并控制每个状态变量,每台都运行模糊神经网络软件。通过传感器测量获得的输入数据与计算机建立通信,阀值能够通过假设扩大的模糊偏节点总是为ON而学习获得,因此输出为1的节点也叫真值节点。语言变量“低”“一般”“高”定义为代表质量标准。

1.2 节点的输出函数

所谓节点的输出函数是与系统的输入激励相对应。本系统建立的输出函数是一个sigmoid逻辑函数,如下定义:

其中Netj是节点j的激励。Netj激励是一个常见的非线性离散函数,本系统中用来与后向传播学习结合来训练多层网络。

1.3 学习阶段

该系统中包括两个学习阶段:1)输入通过网络以前馈方式传播,产生与期望输出相比较的输出值,使得每个输出节点存在误差量;2)误差通过网络后向传播,在本系统中首先计算输出层的Δ(误差量),并将其调整至隐含层。为此该系统需要计算输出间隔的模糊权值和模糊输入的h层集合,有关定义如下。

定义1:模糊数字X的h层集合定义,其中,ψx(x)是X的友函数,R是实数集合。

定义2:层集合[X]h的上下限。

定义3:,对于非负模糊输入Xpi的h层集合,模糊神经网络的输入输出关系如下:

定义4:通过使用误差函数eph来对每个参数的调整层可以表示如下:

这里η是一个学习常量因子,α是一个动力常量;t表示调整的数字,eph是模糊输出向量Op的h层集合的误差函数。

定义5:模糊权值通过以下规则更新:

2 计算机仿真

以再循环的水工厂为例(如图2所示)进了故障诊断仿真,主要包括原料源故障与控制器故障仿真,表1是故障部分列表,其中不包括传感器故障。仿真结果如图3和图4所示。

3 结论

基于模糊神经网络的复杂系统故障诊断模型有效的解决了复杂设计中的错误诊断问题,为更好的改进复杂系统的设计提供了必要的诊断测试手段。在实际问题中,如何利用处理过程中的知识改进神经网络在并行错误诊断中的处理方法是另一个值得进一步研究的课题。

摘要：复杂系统故障诊断是复杂系统设计中的一个重要内容,本文构建了基于模糊神经网络的复杂系统的诊断模型。以工业领域的水资源再循环系统为例,论述了系统的模糊神经网络模型结构,并进行了计算机仿真。实验结果证明了该模型的有效性和可行性。

关键词：模糊神经网络,复杂系统,工业过程

参考文献

[1]陈小玉,朱海华.一种改进的神经网络模型在故障诊断中的应[J].微型电脑应用,201026(2):55-58.

[2]朱醒,钟再敏,孙泽昌.修正指数遗忘RLS算法及其在故障诊断上的应用[J].计算机测量与控制,2007,15(3):329-331.

[3]林万里,祁富燕.可编程序控制系统的故障检测与显示[J].安全技术与管理,2006,5:46-47.

[4]李静.基于神经网络和遗传算法的Ad hoc网络故障管理模型研究[M].电子科技大学,2008.

改进复杂网络模型 第7篇

关键词：知识传播,复杂网络,Cowan模型,信任机制

0 引言

在现今知识经济时代,知识创造、知识传播与扩散、知识利用都是经济增长的重要因素,现实生活中的知识传播都是嵌入到网络中的,系统地研究知识传播网络受到越来越多的关注。复杂网络是门新兴学科,近些年来发展十分迅速,现实世界中的很多问题都可以抽象到复杂网络中建立模型研究、求解。如果将组织中人员的知识传播过程放到复杂网络中来进行研究,将组织中的人员看成复杂网络中的结点,人员间的接触而产生的知识传播看作网络中有向的结点连线,那么组织中人员都能够充分地利用网络的知识共享关系接触或使用其他人创造的知识成果,促进已有知识价值的最大发挥和新知识的不断涌现。

知识在复杂网络上的传播过程存在不少障碍,除了技术方面的因素,主要是组织中人与人之间的信任问题,应当指出,知识传播在个人与个人、个人与组织的交互过程中实现,是一种双方不仅仅基于互利互惠的关系还是一种基于信任的交换,并随着双方理解和交互时间的变化而变化,即在组织中知识传播过程中,初始信任决定组织中人与人之间是否传播知识,累积信任值大小决定组织中人与人之间知识传播的多少。网络中人员交互的不同阶段,信任值影响知识传播的动态过程会有所不同。因此,研究不同信任水平的复杂网络下知识的传播对加速组织知识共享、提高整体竞争力有着积极的现实意义。

1“小世界”特性的复杂网络构建

1.1 建立模型

Watts和Strogatz[1]提出“小世界”网络模型(WS模型),用来描述从一个规则网到一个随机网的转移过程。用V={1,2,…,N}表示一个有限个体集合,对任意i,j∈V,定义变量e(i,j),当i和j间有边连接时,e(i,j)=1,否则e(i,j)=0。网络G={e(i,j):i,j∈V}是所有个体的关系对列表,dij是结点i到结点j的最短距离。建立模型的步骤如下:

①从具有N个节点的环形网络开始,其中每一节点都与它初始的K个邻点相连(每一边有K/2个)。为了获得一个稀疏但任何时刻总有连接的网络,考虑N>K>ln N>1。

②以概率P随机为网络的每条边重新布线,同时保证没有自连接和重复边。

因为不允许重复连线,给定N个结点的环形网络只有NK/2条连线。重新布线时依次对每条旧连线选定的某一边端点随机放置新位置,因此改写的连线数目为PNK/2。由于随机性缘故,这些改写的连线可能会出现远距离连线,它们被称为捷径。显然,当P=0时仍为给定的环形网络,当P=1时为随机网。随着增加,可以看到网络从规则网向随机网的变化,如图1所示。

1.2“小世界”网络的特性参数

网络两结点间的距离为连接两者的最短路径的边的数目,网络直径为任意两点间最大距离,网络平均路径长度则是所有节点对之间距离的平均值,它描述了网络中节点间的分离程度,即网络有多小。复杂网络研究中一个重要的发现是绝大多数大规模真实网络的平均路径长度比想象的小得多,称为“小世界”效应。

平均距离l:N为网络节点数

集聚系数用来描述网络中节点的聚集情况,即网络有多紧密。若网络中结点l的度数为k,则它的邻域,即与结点l有连线的相邻结点全体,最多有k(k-1)/2条连线。如果它的邻域中实际存在的连线数为E(l),那么结点l的集聚系数为:

网络的集聚系数定义为所有结点集聚系数的算术平均值,即

当P=0时,网络是规则网络,网络的平均距离l随N的增大呈线性增长,集群系数大;当P=1时,网络变为随机网络,l随N的增大呈对数增长,且集群系数随N减小而减小;在P∈(0,1)时,存在一段较宽的区间,模型显示出小世界特性,l约等于随机网络的平均距离,网络具有高集群性。

2 复杂网络信任的内涵和类型

人作为知识共享的主体,通过激励、制度等手段可以改善知识传播的效果,但成员之间良好的信任关系更是知识传播中的关键影响因素。众多研究表明,信任在知识传播中扮演着重要角色,信任别人的人总是在组织中与他人持续合作,这种信任行为反映的是“道德责任或义务”。[2,3]反之,组织成员之间由于个性、经历、知识结构等方面的差异,必然导致理念、观点、处事方法和原则等方面的差异,由此引发的信任危机是不容忽视的,如成员之间由于观念不同而导致的冲突以及沟通不畅引发的猜疑和误解等,都会对组织的知识传播效率造成影响。

2.1 信任的含义及知识传播中相关研究

在知识传播的研究中,信任的重要性已经受到关注。Huemer等认为,信任最重要的角色关系到组织中知识是如何传播以及传播发展的原因[4]。他们根据March&Olsen的观点[5],提出信任便于让组织中成员之间学习,并且基于信任的这种确定条件下决定进行知识传播。知识成员的脑力劳动通过知识共享和转移的行为,与组织中其他成员共同构建成一个学习网络,这就是知识传播的复杂网络,这样,知识不仅在个人头脑中出现和保留,并且可以通过这种人与人之间基于信任的相互交互原则,将知识镶嵌在组织成员网络中。与网络中人与人之间的互动关系相联系,信任可以在参与双方建立起情感纽带,它促使组织成员进行交流,与此同时,组织知识得到扩展。Szulanski[6]进一步从反面验证了不信任对于知识传播的消极作用。他从妨碍知识传播的因素入手,证实了知识提供方缺乏可靠性是造成知识传播出现困难的主要因素。Andrews和Delahay认为,接受方感受到的提供方的可靠性和提供方感受到的接受方的可信性分别在知识获取和共享过程中起着重要的促进作用。他们还认为“信任在知识共享中的重要性甚至超过了正式的合作程序,因为如果没有信任的存在,知识共享就不可能发生”[7]。Levin和Cross将信任分为基于能力的信任和基于善心的信任。在此基础上,他们通过数据分别验证了两种不同维度的信任均与接受方感受到所获知识的有用性之间存在显著正相关关系,继而提出,信任能促使接受方减少对知识的验证,更愿意接受并运用提供方的知识。

2.2 信任的类型及影响信任的因素分析

知识传播双方的相互信任,能够促进双方间更多地沟通。随着这种沟通的进一步发展,组织中人员之间会拥有更广泛的共同知识、建立更多的沟通渠道并且能够利用更丰富的媒介进行沟通,因此知识转移会变得更加容易。不同领域的学者对信任研究的阐释不同,经济学者倾向从计算或制度方面来理解,心理学家则分析人格属性与认知的角色,社会学家着重人际与社会关系中的结构镶嵌性质,因此造就了信任分类的不同型态。通过对比各种信任类型的含义,在知识传播领域大致归为两类:认知型及情感型。

认知型信任定义为信任者基于与被信任者个人有关的可信任性证据的认知,而产生信任对方的意愿,这些证据包括被信任者的人格特质、文化背景、意图善恶、相关能力强弱、是否言行一致并具有可预测性等,信任者在搜集、处理、计算、解释这些信息的过程都是一种认知的程序。无论是在信任发展初期或是信任发展进入稳定期之后,这种认知性的程序都会反复产生作用,以检验彼此的信任关系是否仍能维持。一般而言,影响认知信任的主要有网络中个体的利益、能力及社会相似性。当结点之间进行基于信任的知识传播时,若两结点存在利益冲突,则信任值越低。能力和社会相似性反映在结点间的最短距离和关系权重上,如果结点间的关系越紧密,也就是某结点到达另一结点的最有效的关系长度越小时,关系权重越大,能力越强,越具有社会相似性;反之,网络中关系长度越长,两者的关系越弱,能力也越弱,社会相似性也随之减弱。

情感型信任定义为信任者基于对被信任者的情感依附而愿意信任对方。其主要特点是需要经过一段时期的互动之后才可能发展,而不太可能在交换关系开始时就出现。如果信任者在频繁互动中充分了解到被信任者的善意(benevolence)及可信任性,就会对被信任者产生依赖的意愿及情感的依附。影响情感型信任主要是互动时间的长短和累积的认知型信任值。互动时间越长,累积的认知型信任值越大,情感型信任值就越大。

认知型信任是基础,它可以支撑情感型信任的发展。情感性联系的产生必须是在双方频繁的互动中确认对方的可信任性之后,即关系中的认知型信任已经成熟,因此情感型信任的建立需要有一定程度的认知型信任作为基础。

3 复杂网络知识传播相关模型研究

荷兰学者Cowan和法国研究者(Cowan and Jonard,2004;Cowan,Jonard&Zimmermann,2006)提出了复杂网络上的一种知识扩散模型和一种知识增长模型[8]。他们利用复杂网络模型模拟了知识在社会网络中传播扩散的过程,分别研究了网络结构与知识扩散间的关系、网络结构与知识增长间的关系,发现在“小世界”网络中知识传播效率最高,但同时知识差异也最大(也就是知识传播扩散最不公平,从传播学角度看就是“知识沟”最大)。对照前文复杂网络建模的参数特征,从图2中可以看出,在P∈[0.01,0.1]区间该网络具有明显的小世界效应,即该网络同时具有较大的C(p)值和较小的L(p)值,整个网络平均知识水平较高,并一直呈上升趋势;当p叟0.1之后,平均知识水平呈现快速下降之势。

4 基于信任机制的复杂网络知识传播模型

4.1 对Cowan模型的修正

Cowan等学者基于复杂网络的模拟研究为当前知识传播与扩散领域的前沿开辟了新的领域,然而,Cowan模型仍存在一些不足,模型有两个隐含前提并不符合知识传播的实际情况,即:一是知识传播的易货交换假设;二是知识传播的无条件主动假设。下面对Cowan模型的这两个隐含前提予以批判和修正,建构新的基于信任机制的复杂网络上知识传播模型。

①Cowan等学者认为所研究的知识传播与扩散类似于“易货贸易”,只有当网络中A拥有B所需要的知识,同时B有A所需要的知识,这样A、B之间才能进行知识传播和相互扩散。这样的模型前提显然是有缺陷的,人们在实现的知识传播过程中,往往不会有理想化的相互交换产生。而从现实的知识传播网络出发,组织中人与人之间的知识传播实质是人与人基于信任的互动过程,通过网络中成员的互动,知识发生转移、共享及创造。在人与人初始交流时,人们会搜集、处理、计算、解释对方的人格特质、文化背景、意图善恶、相关能力强弱、是否言行一致等方面信息,这些信息的搜集是一种认知的程序,形成认知型信任,认知型信任决定信任关系是否能维持,是知识在网络上传播的基础条件。由于初始信任程度比较低,成员之间知识传播的行为偶尔发生,整体网络知识传播效率低。

②Cowan等学者默认了模型中每个人都毫无保留地将自己的知识与他/她的邻居分享、主动进行知识传播,这是一种非常理想化的状态。而现实中组织内个体之间知识竞争合作关系,个体并不是无条件主动将自己的知识传播给他人,对于这种知识传播的悖论,情感型信任可以对此进行解释。信任在程度上有高低之分,因此组织中人员之间的信任水平可以进行量化,用信任值表示。组织中人员经过一段时期的互动之后,认知型信任值上升,随着彼此依赖的意愿及情感的依附而产生情感型信任,情感型信任值越大,知识在网络中传播效率越高,情感型信任值很小就会出现知识传播的悖论,即附有知识价值的个体担心自己的知识被他人学去,需要在组织内维持一点程度的知识优势,而阻碍知识的传播。

4.2 知识传播网络中信任值的确定

在复杂网络的知识传播中,组织中的人员可以通过认知型信任与组织中的其他成员交流、吸收新的知识、提高自己的知识水平,并且知识的传播是发生在有信任关系的网络中两个个体之间。当结点传播知识的时候,只有与它有信任关系的结点才是潜在知识接受对象。结点总的信任值由认知型信任和情感型信任组成。[9]

其中:T表示知识传播的复杂网络中结点的信任值,c和f分别表示结点的认知型信任值和情感性信任值,α、β为二者的权重,0<α,β<1,α<β确保复杂网络中知识传播先基于认知型信任,后通过频繁互动产生情感性信任,而且情感型信任对知识传播的贡献高于认知型信任对知识传播的贡献。

ly表示结点间的利益,本模型采用-1,+1来衡量;-1表示两结点有利益冲突,+1表示两结点没有利益冲突。nl表示结点的能力和社会相似性,用网络参数最短距离来表示,因为本模型考虑知识传播的复杂网络是不加权的,所以没有用权重体现网络中结点的能力及社会相似性。ct-1表示结点前t-1次认知型信任的累加值。t表示时间影响因数,如果交流越频繁,时间越长,情感型信任值越大。

4.3 基于信任机制的复杂网络知识传播模型建构

我们在前文已分析构造了“小世界”网络模型G(V,E),给定该复杂网络的总结点数N=1000,初始规则网络每个结点有K=50个信任结点,网络重连概率P从0到1逐渐变化。根据L(p)/L(0)和C(p)/C(0)可以测算出“小世界”效应,参见图3。

基于信任机制的复杂网络知识传播模型与Cowan模型不同的是,我们引入了信任值,记作:T,Vi(t)和Vj(t),分别表示结点i、j在t时刻知识水平。这样,组织中结点在进行知识传播过程中,不像货物交换那样简单直接,而是涉及到信任值的更新,信任值在不同结点的交互之间增加或减少,初始的信任值为认知型信任,经过一段时间交互累积的信任值为情感型信任;在此基础上,若该结点在该时刻进行基于信任值的知识传播,可以建立从t~t+1时间段的知识水平函数,传播后的知识水平变为:

信任值变为:Ti,t+1=αlyi,tnli,t+βlyi,t-1nli,t-1t

网络的平均知识水平为:

网络平均信任值为:

通过对知识传播的复杂网络进行建模,可分析知识传播网络特征,选用网络平均知识水平作为衡量该网络知识传播程度的指标,如果网络平均知识水平的值很大,说明网络内各节点之间的知识传播效率很高。另一方面,知识传播网络的信任值也可以作为衡量知识传播的程度指标,信任值代表知识传播网络中各节点之间的联系,这些联系有可能让组织整体智慧提升。

5 结束语

通过对Cowan模型进行修正,将“小世界”特性的复杂网络应用到知识传播中,建立了含信任机制的知识传播模型,分析了在认知型信任、情感型信任不同信任水平下知识在网络上的传播行为,得出:结点之间信任值高、网络的平均知识水平高时,知识传播效率越高,即知识传播更加容易。因此满足上述模型的企业、高校或政府部门应积极采取有效措施,加大人与人之间信任感,促进知识的流动及共享。

参考文献

[1]D J Watts and S H Strogatz.“Collective dynamics of‘small-world’networks,”[J];Nature,1998,393:397-498.

[2]高兆明:《存在与自由:伦理学引论》[M];南京师范大学出版社,2005:216-370。

[3]J.Nahapiet and S Ghoshal.“Social capital,intellectual capital,and the organizational advantage,”[J];Academy of Management Review,1998,23:242-266.

[4]L Huemer and Von Krogh G Roos.“Knowledge and the concept of trust,”[M];Newbury Park:Sage Publications,1998:23-45.

[5]J G March and J P Olsen.“The uncertainty of the past:Organizational learning under ambiguity,”[M];London:Blackwell,1990:335-358.

[6]G Szulanski.“The process of knowledge transfer.A diachronic analysis of stickiness”[J];Organizational Behavior and Human Decision Processes,2000,82:9-27.

[7]Kate M Andrews,Brian L Delahaye.“Influences on knowledge processes in organizational learning:The psychosocial filter,”[J];Journal of Management Studies,2000,37:797-810.

[8]R.Cowan and N Jonard.“Network structure and the diffusion of knowledge,”[J];Journal of Economic Dynamics and Control,2004,28:1557-1575.