一种基于节点状态演化的复杂网络节点重要性评估方法

摘要

本发明属于网络控制领域，具体涉及到考虑级联失效的复杂网络节点重要性评估方法，包括步骤一：输入复杂负载网络数据，计算出相应节点的度；步骤二：根据初始负载模型以及极限容量模型，计算复杂负载网络中节点的初始负载和极限容量，并初始化级联失效级数t＝1；步骤三：计算节点i在级联失效t级后的状态，节点i在级联失效t级后的状态包括此时节点自身的剩余负载容纳能力和相邻节点的剩余负载容纳能力，统计级联失效t级时的所有失效节点个数nt；步骤四：计算级联失效t级时由单个失效节点的引起的节点负载更新；步骤五：计算级联失效t级时由所有失效节点引起的节点负载更新；步骤六：计算整个网络在整个级联失效过程的过载崩溃节点的数目以及失效节点比例。

说明书

技术领域

本发明属于网络控制领域，具体涉及到考虑级联失效的复杂网络节点 重要性，特别是引入了节点状态演化机制的节点重要性评估方法。

背景技术

现有关于复杂网络级联失效模型的负载重分配策略主要可以分为全局 负载重分配策略、局部负载重分配策略以及混合负载重分配策略。全局重 分配策略包括等效增量策略、平均分配策略、随机分配策略。等效增量策 略突出了级联失效过程中的全局特性，即当网络中的任意元素失效时，网 络中的其他元素均将获得等量负载的增加，并且增加的负载与失效的元素 负载无关，仅与初始的给定值有关；平均分配策略在突出级联失效过程中 负载重新分配全局特性的同时，引入了负载增量与失效节点负载存在关联 的特点，即当网络中任意元素失效时，网络中其他完好的元素均将获得等 量的负载增量，且其增量是由失效元素负载等分而来的；随机分配策略同 样关注级联失效过程中的负载重分配的全局特性，主张负载增量与失效节 点负载存在关联关系，但是其增量是随机的而不是平均的，即当网络中的 任意元素失效时，网络中其它完好的元素均会获得负载增量，且其分布具 有随机性，并且整个网络中所有元素负载增量的累积等于原有失效元素的 负载；最近邻重分配策略考虑了网络的级联失效过程以及网络中信息流的 异质权重特性，级联失效过程由初始扰动诱发，失效节点的负载向周围节 点扩散，周围节点的负载增量按其节点的负载在周围节点所有负载中所占 的比例进行分配。

现有实现方案采用最近邻重分配策略，该策略考虑了网络的级联失效 过程以及网络中信息流的异质权重特性，级联失效过程由初始扰动诱发， 失效节点的负载向周围节点扩散，周围节点的负载增量按其节点的负载在 周围节点所有负载中所占的比例进行分配。基于上述最近邻重分配策略， 现有的节点重要性评估方法考虑了过载机制下的节点重要性演化，随着网 络中节点失效引起的负载重新分配导致节点负载的不断变化，其重要性逐 步演化。

现有的复杂负载网络(例如电力网络、交通网络、能源运输网络)级 联失效模型中负载重分配策略大部分依据节点初始负载进行近邻重分配， 失效节点的负载向周围节点扩散，周围节点的负载增量按其节点的负载在 周围节点所有负载中所占的比例进行分配，并没有考虑节点实时负载的变 化情况，或者仅仅考虑了节点实时负载的变化忽略了节点负载的再转移情 况，从而使得网络抵抗级联失效的能力较低。这种重分配策略在只有初始 负载信息而没有实时的局部负载信息的条件下具有一定的合理性。但是现 有大部分的基础设施网络均具有监督机制，能够实时掌握周围节点负载的 变化情况。

发明内容

本发明基于上述问题，提出了一种基于节点状态演化的负载重分配策 略，重分配策略中不仅考虑了节点的实时负载变化情况，而且考虑了节点 负载的再转移情况，这种重分配策略能够充分利用全局的节点负载信息， 实时分配负载，增强了整个负载网络抵抗级联失效的能力，并且在这种策 略的基础上，提出了一种新的节点重要性评估方法，依据此评估结果可以 重点保护关键节点，增强网络抵抗级联失效的能力。具体技术方案如下：

一种基于节点状态演化的复杂网络节点重要性评估方法，包括以下步 骤：

步骤一：输入复杂负载网络数据，计算出相应节点的度；

网络数据包括相应的节点以及连边，节点的度由与该节点相连接的连 边累计而得；

步骤二：根据初始负载模型以及极限容量模型，计算复杂负载网络中 节点的初始负载和极限容量，并初始化级联失效级数t＝1，t为整数；

初始时刻节点负载为：

F_i⁰＝bk_i^α(b＞0)，i＝1,2,...,N

其中，i表示节点，F_i⁰为节点i的初始负载，k_i表示节点i的度，b和α为 调节参数，N表示节点总数；

极限容量表示为：

C_i＝(1+β)F_i⁰,i＝1,2,...,N，

C_i表示节点i的极限容量，i表示节点编号，β表示网络的最大忍受度， β≥0且为常数。

步骤三：计算节点i在级联失效t级后的状态，节点i在级联失效t级后 的状态包括此时节点自身的剩余负载容纳能力和相邻节点的剩余负载容纳 能力，统计级联失效t级时的所有失效节点个数n^t；

节点i在级联失效t级后自身的剩余负载容纳能力：

${Y_i}^t=\left(\begin{array}{c}{C}_i-{F_i}^t,{F_i}^t\le C_i\\ 0,{F_i}^t>C_i\end{array}\right),i=\mathrm{1,2},...,N$

节点i在级联失效t级后的状态：

其中，F_i^t-1表示节点i在级联失效t-1级时的负载；i,j表示节点编号，表示节点i在级联失效t级后的状态，Y_i^t表示节点i在级联失效t级后的剩余 负载容纳能力，Γ_i表示节点i的邻接节点集合,γ为权重参数；

初始化n^t＝0，当某个节点i在级联失效t级后的负载F_i^t-1＞C_i时，认为 该节点已经过载，则此时失效节点i自身负载变为0，更新n^t＝n^t+1；直至所 有节点i∈1,2,...,N均遍历完，得出t级时的过载节点数目n^t；若n^t＝0，则整 个级联失效过程结束，转至步骤六，否则，进入步骤四；

步骤四：计算级联失效t级时由单个失效节点引起的节点负载更新；

设级联失效t级后某个节点失效，其中，f^t表示级联 失效t级时的所有失效节点，表示级联失效t级时失效节点中第h个失效 节点，更新由单个节点引起的整个网络中节点的负载；

当节点i为失效节点的邻接节点时，其中，F_i^t-1为更新之前的负载，为更新之后的负载，ΔF_i^t为更新时的增量，

${{\mathrm{\Delta F}}_i}^t=F_{f_h^t}^t*\frac{S_i^t}{\left(\underset{j\in {\Gamma }_{f_h^t}}{\Sigma }{S}_j^t\right)},i\in {\Gamma }_{f_h^t}$

其中，为节点的邻接节点集合，为失效节点在级联失效t级 后的负载，为相邻节点i在级联失效t级后的节点状态；

当节点i不是失效节点的邻接节点时，即：不是失 效节点的邻接节点，节点负载值保持不变。

步骤五：计算级联失效t级时由所有失效节点引起的节点负载更新；

设f^t表示级联失效t级时的所有失效节点，表示级联失效t级时失效 节点中第h个失效节点，n^t表示级联失效t级时的所有失效节点个数，

记此时的网络级联失效级数为T(即级联失效 过程发生的级联失效总层级数)，将级联失效级数t自增加1级，即t＝t+1， 返回步骤三；

步骤六：计算整个网络在整个级联失效过程的过载崩溃节点的数目以 及失效节点比例；

整个网络在整个级联失效过程的过载崩溃节点的数目n：

$n=\underset{t=1}{\overset{T}{\Sigma }}{n}^t,$

失效节点比例L：

L＝n/N,

其中，n^t为级联失效第t级的失效节点数目，N表示节点总数。

为进一步理解本发明，下面对本发明中相关原理进行阐述：

(1)节点状态

节点状态是节点负载的直接体现，这里用节点能够容纳转移负载的能 力来表示，即节点能够容纳转移负载能力的最大值，它由两个方面的因素 决定：首要因素即考虑节点自身的负载剩余容纳能力，其次需要考虑相邻 节点的负载剩余容纳能力。从上述描述的过程来看，它可以分为两个阶段， 首先考虑节点剩余容纳能力，假设节点i的实时负载为F_i，节点的极限容量 为C_i，那么节点的剩余负载容纳能力Y_i，可用公式(1)表示：

$Y_i=\left(\begin{array}{c}{C}_i-F_i,F_i\le C_i\\ 0,F_i>C_i\end{array}\right),i=\mathrm{1,2},...,N---\left(1\right)$

即节点剩余负载容纳能力为节点容量与现有负载的差值，当负载超过 容量时，其负载剩余容纳能力为0。节点剩余负载容纳能力体现的是节点还 能够处理或者容纳负载的能力，Y_i值越大，说明其处理能力更强，在负载 重分配时应该占有优势，其分配的比例应该更高，反之更低。它是随着节 点负载的变化而不断变化的。

考虑到相邻节点剩余负载容纳能力的影响，本技术中提出了能够真实 衡量节点剩余负载容纳能力的节点状态，节点状态是该节点自身的剩余负 载容纳能力与相邻节点剩余负载容纳能力的有机结合，共同构成了节点的 真实的剩余负载容纳能力，这里对节点状态的指标进行定义，如式(2)所 示：

其中，S_i表示节点状态，Y_i表示节点的剩余负载容纳能力，Γ_i表示节点 i的邻接节点,γ为权重参数，表示空集，通过调节γ的值可以调节整个 节点状态在负载充分配时所占的比例。当γ＝0时，上式为局部负载均匀重 分配。式(2)反映的是节点能够容纳负载的能力，它取自身节点剩余负载 容纳能力与相邻节点剩余负载容纳能力总和中的最小值，当没有相邻节点 时，节点剩余负载容纳能力即为自身的节点剩余负载容纳能力。

(2)负载重分配策略

负载重分配策略是描述节点失效后其上的负载向网络中其他节点进行 转移的规则。本技术中的负载重分配策略的级联失效效果为如图3所示，节 点f失效后，原本打算通过该节点f的负载(例如信息流、交通流)将会 重新选择通过路径，其上的负载将会转移到与之相邻的节点，以保证整个 网络的有效运行。那么整个网络会由于节点的失效而进行负载的全面更新， 即F_i′＝F_i+ΔF_i,i∈Γ_f，其中F_i为更新之前的负载，F_i′为更新之后的负载，ΔF_i为更新时的增量，Γ_f为失效节点f的所有邻接节点。假设失效节点f的负 载为F_f，相邻节点的节点状态为S_i,i∈Γ_f，所以在相邻节点上重新分配的负 载增量可以用公式(3)表示，它是与节点状态相关而不是与节点负载相关 的经典近邻重分配策略，

${\mathrm{\Delta F}}_i=F_f*\frac{S_i}{\left(\underset{j\in {\Gamma }_f}{\Sigma }{S}_j\right)},i\in {\Gamma }_f---\left(3\right)$

采用本发明获得的技术效果：首先采用了节点状态的概念，不仅考虑 了节点的实时负载变化情况，而且考虑了节点负载的再转移情况，这种重 分配策略能够充分利用全局的节点负载信息，实时分配负载，增强了整个 负载网络抵抗级联失效的能力，提供了一种很好的根据网络中的实时负载 信息控制负载网络抵抗级联失效的方法，有效地降低了负载网络由于级联 失效造成的损失；其次，在这种重分配策略的基础上提出了一种新的节点 重要性评估方法，利用评估结果可以有效地识别网络中的重要节点，对重 要节点加以保护，控制网络发生级联失效的频率，减少损失。

附图说明

图1为本发明的流程示意图；

图2为两种负载重分配模型的效果对比情况；

图3为依次使得节点失效从而引起整个航空网络级联失效的数目比例 情况。

具体实施方式

下面，结合附图和具体实施例对本发明作进一步说明。

如图1所示，本发明按照下述步骤基于节点状态演化的复杂网络节点 重要性评估方法，

步骤一：输入复杂负载网络数据，计算出相应节点的度；

步骤二：根据初始负载模型以及极限容量模型，计算复杂负载网络中 节点的初始负载和极限容量，并初始化级联失效级数t＝1，t为整数；

步骤三：评估节点i的重要性，计算节点i在级联失效t级后的状态，节 点i在级联失效t级后的状态包括此时节点自身的剩余负载容纳能力和相邻 节点的剩余负载容纳能力，统计级联失效t级时的所有失效节点个数n^t；

步骤四：计算级联失效t级时由单个失效节点的引起的节点负载更新；

步骤五：计算级联失效t级时由所有失效节点引起的节点负载更新；

步骤六：计算整个网络在整个级联失效过程的过载崩溃节点的数目以 及失效节点比例。

本发明在标准的北美航空网络上进行了测试，如附图2所示，图中给出 了经典重分配策略和本发明中提出的模型的对比，其中横坐标表示初始负 载参数，纵坐标表示级联失效节点比例，选取了容量参数为β＝0.03，初始 负载参数α∈(0.1,2)，每次增加0.1，按节点负载从大到小排序选取负载最大 的前50个节点依次使其失效，取其失效节点比例的平均值作为衡量网络脆 弱性的指标。结果显示基于节点状态演化的重分配策略的网络健壮性要明 显优于经典的基于负载的近邻重分配策略，实验结果证明了本发明相较于 经典重分配模型具有更强的抵抗级联失效的能力。

在上述基于节点状态演化的级联失效模型的基础上，同样在北美航空 网络上运用本发明中提出的节点重要性评估方法对节点重要性进行评估。 节点失效顺序如附表1所示，表中给出了由一种节点重要性排序方法给出的 排名前30位的节点编号以及相应的重要度得分。附图2中给出了按照上述节 点失效顺序依次使得节点失效时，网络的级联失效节点比例L的情况，图 中结果显示各个节点能够引起网络发生级联失效的规模的情况，对节点的 重要性进行评估，节点比例L越大，说明该节点越重要，需要重点保护。

表1中给出了由一种节点重要性排序方法得出的排名前30位的节点编 号以及相应的重要度得分，同样在北美航空网络上进行了测试，运用本发 明中提出的节点重要性评估方法进行评估。

表1

图3，给出了根据经典排序值依次使得节点失效从而引起整个航空网络 级联失效的数目比例情况，从1到235分别为节点的重要性排序序号，纵坐 标表示网络的级联失效比例。从图中可以得出各个节点失效所引起的网络 级联失效的数目。这也说明了本发明的用武之地，能够依据评估结果将关 键的节点发掘出来，对于重点保护这些关键节点具有重要的现实意义。

以上仅是实施例仅用于说明本发明的效果，本发明的保护范围并不仅 局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护 范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明 原理前提下的若干改进和润饰，应视为本发明的保护范围。