异质依存网络衰退特征与关键节点辨识
  自动化学报  2018, Vol. 44 Issue (5): 953-960   PDF    
异质依存网络衰退特征与关键节点辨识
吴舜裕, 许刚     
华北电力大学电气与电子工程学院 北京 102206
摘要: 针对传统复杂网络理论通常以同质单层网络作为研究对象,忽视现有工业复杂网络具有多异质节点与多层网络互耦合性的问题,提出异质依存网络(Heterogeneous-interdependent network,HI net)理论及其关键节点辨识方法.以含多类型节点的异质依存网络作为研究对象,分析异质节点依存关系以及网络衰退机理.构建分块结构下异质节点依存矩阵,将多层异质依存网络归并于单层网络.提出节点效用耦合系数,描述不同故障类型下邻居节点效用耦合性.建立节点邻域效用耦合系数计算方法及其影响力传播方法,识别节点对网络状态的影响,实现关键节点识别.通过对典型的含多电源电网系统与电力信息物理异质依存网络进行仿真实验,分别验证了所提方法对不同故障类型下关键节点识别的有效性.
关键词: 异质依存网络     网络衰退     效用耦合     影响力传播    
Degeneration Characters of Heterogeneous-interdependent Network and Key Node Identification
WU Shun-Yu, XU Gang     
School of Electrical and Electronic Engineering, North ChinaElectric Power University, Beijing 102206
Manuscript received : July 11, 2017, accepted: December 6, 2017.
Foundation Item: Supported by National Key Research and Development Program of China (2016YFB0901200)
Author brief: XU Gang  Professor at the School of Electrical and Electronic Engineering, North China Electric Power University. His research interest covers smart grid and big data analysis in power grid
Corresponding author. WU Shun-Yu  Ph. D. candidate at the School of Electrical and Electronic Engineering, North China Electric Power University. His research interest covers smart grid and interdependent networks in power system. Corresponding author of this paper
Recommended by Associate Editor WANG Zhuo
Abstract: In order to solve the problem that traditional complex network theory usually takes homogeneous single-layer network as research object, and neglects mutual coupling relations among heterogeneous nodes or multi-layer networks in industrial complex networks, the heterogeneous-interdependent network (HI net) theory with key node identification method is proposed. Taking the HI net with multi types of nodes as the object, we study the dependency relations of nodes and the mechanism of network degeneration. Then, the dependency matrix of heterogeneous nodes is established to combine the multi-layer HI networks into one layer. To describe the effectiveness coupling for neighboring node under different fault mode, the effectiveness coupling coefficient is designed. Finally, the effectiveness coupling coefficient of neighborhood nodes and its propagation method are given to calculate the influence from node to networks to identify the key nodes in HI net. The effectiveness of the key nodes identification method is verified by the simulations of two typical HI nets, including the power system with multi generations and power-information HI net.
Key words: Heterogeneous-interdependent network (HI net)     degeneration of networks     effectiveness coupling     influence propagation    

随着信息科技、能源技术等工业领域的技术发展, 人们生活已极度依存于由通信、电网、社交传媒等形成的复杂网络[1].复杂网络结构特征分析与关键节点辨识一直是相关学者的研究重点之一, 通过保护复杂网络中关键节点, 可有效保障网络运行完整性、可靠性以及传输性能.实际工业领域复杂网络通常由各类具有不同功能特征的节点所组成, 形成单层或多层异质异构网络[2].同时, 工业异质复杂网络大多采用固定路径进行节点间介质(信息、能量)的有向传递, 是一种有向复杂网络.在介质传输过程中, 若节点$i$其所依存节点$j$失效($i$$j$可以是同类节点, 也可以是不同类型节点), 则必然导致节点$i$随之失效, 并进一步引起依存于节点$i$的其他节点失效, 形成网络故障传播.例如:当含分布式电源的配电网进行独立供电时, 负荷节点依存供电能力范围内的电源, 离电源较远负荷节点的供电又依存于供电路径上离电源较近的负荷点; 社交网络中, 网络群众的信息获取依赖于某一个关键的信息传播用户, 而信息传播用户又可能依存于特定的信息来源.当上述网络中上级节点失效时, 必然导致下级节点能源或信息获取的中断.因此, 针对此类含多种类型节点的网络进行节点间依存关系分析, 识别关键节点并进行有效保护, 可有效降低由节点故障或被攻击导致的网络破坏.

现有在评估复杂网络节点时采用的网络故障模式可分为两类: 1)链路中断[3-4]; 2)级联失效[5-6].采用链路中断的思想去评估复杂网络中关键节点时, 通常假设网络中某一节点失效后, 仅对相邻连通支路产生影响, 并分析节点失效对复杂网络结构、节点间最短路径、介数等特征参数的影响.该辨识方法是基于网络静态特征进行的关键节点辨识, 而真实网络具备显著的动态特征, 网络结构变化会影响非故障节点存在的有效性, 从而引起进一步的节点连锁失效[7-8].级联失效是指如果网络中一个或少量的元素(节点或边)因发生故障而不可用, 会引发网络中介质或负荷的重分配, 反过来又会引起其他节点因负载过高而崩溃失效, 由此使得故障逐步传播产生级联效应, 最终导致网络中相当一部分节点甚至整个网络的崩溃[9].级联失效考虑了复杂网络失效节点与隐藏链路、节点负载能力之间的关系, 通过计算负载转移判断相邻节点连锁故障效应, 对物流、交通、无线传感等不具固定传输路径的网络结构进行关键节点辨识具有较好的应用价值.然而, 对于通信骨干网架、社交网络、电网等异质依存网络(Heterogeneous-interdependent network, HI net)中, 通常存在大量异质节点之间可能并不存在直接有效的介质传输路径, 却存在相互依存关系.而现有级联失效分析通常只是通过单纯的物理路径进行故障分析, 无法体现节点中异质依存关系.同时, 异质节点故障类型不同所导致的网络衰退结果也存在很大区别, 可能是对网络运行稳定性的影响, 也可能是对网络结构的直接影响.若统一采用级联故障进行关键节点识别无法区分异质节点故障类型的故障扩散程度.因此, 采用级联故障分析异质依存网络中关键节点具有一定不适用性.

在网络依存特征方面, Buldyrev等首次在Nature中提出了相互依存网络理论, 描述了不同网络间耦合节点依存性对复杂网络的影响[10-11], 并以电力系统中的信息物理系统为例, 描述了单边网络节点失效导致另一网络对应耦合节点的直接失效以及后续故障扩散过程.而工业网络中通常含有不同类型的节点或边, 是一种典型的异质网络, 且单个工业异质网络中上下游节点之间存在直接或间接的有效性耦合.此外, 上述方面均无法体现网络中节点跨越中间节点的依存关系, 对工业复杂网络应用具有一定的局限性.

针对工业领域普遍存在的异质依存网络, 给出了异质依存网络定义与特征.综合分析了异质节点间的依存关系, 并将异质依存网络衰退分为:网络状态衰退与结构衰退两类.提出了异质依存网络中节点依存关系的数学描述方法, 实现多层网络的节点依存关系描述.根据异质依存网络特征, 考虑节点依存关系, 提出节点邻域效用耦合系数计算方法, 并通过改进后的PageRank算法分析节点故障对网络效用关联性.以电力系统作为典型的异质依存网络进行仿真计算验证, 分别验证了所提方法对不同节点故障类型下关键节点识别的有效性.

1 异质依存网络定义及其特征 1.1 异质依存网络基本性质

异质网络指拥有不同属性元素的复杂网络.异质网络根据网络中元素类型细化了各节点、边之间的关联关系, 形成包含多类节点或边的复杂网络.在数据结构的变现形式上, 异质网络可描述为一种特殊的有向图[12].

定义1.异质网络

给定有向图$G=(V, E; \phi, \psi; A, R)$, 其中: $V = {v_1}, {v_2}, \cdots , {v_N}\} $为节点集合, $E = \{ {e_1}, {e_2}, \cdots , {e_M}\}$为边集合.存在节点类型映射函数: $\phi: V\rightarrow A$, 满足$\phi(v)\in A(v\in V)$, 存在边类型映射函数: $\psi: E \rightarrow R$, 满足$\psi(e)\in R (e\in E)$.当节点类型数量$|A|>0$或边类型数量$|R|>0$, 则称$G$为一种异质网络.

区别于传统的复杂网络, 异质网络对内部节点或边的所属类型均应有明确的区分.同样, 对边集合的异质性区分可按边介质传输方向特征也可按具体系统中边的其他物理属性.特别的, 设节点$v_{i}$$v_{j} (i, j\in N)$间存在连通路径$v_{i}e_{ij}v_{j}$, 节点$v_{j}$$v_{i}$间路径记为$v_{j}e_{ji}v_{i}$, 在异质网络中可能$e_{ij}\neq e_{ji}$.

在工业异质网络或社交异质网络中, 异质节点间状态通常存在一定关联特征.即当异质依存网络中某节点的状态(一般指节点的运行状态、节点内部结构、节点有效性等)发生变化时, 通常会对由多个邻居节点构成的邻域节点群形成一定影响, 并通过邻域节点群进而将这种状态变化扩散至整个网络, 形成类似马尔科夫过程的网络状态转移.这种状态转移可以是改变了异质节点的状态, 也可能致使其直接失效.此外, 根据不同复杂网络中节点异质性、耦合关系以及网络结构, 异质节点间状态耦合传递方向(单向传递或双向传递)与程度均存在差异.以电网为例, 当供电母线出现暂态振荡时(电压与频率的波动), 故障会沿供电路径进行双向传递, 而不是只沿着电流方向.对于含多分布式电源配电网, 电源点母线与负荷点母线出现不稳定现象时, 对整个电网的稳定性显然是不同的, 这也说明了异质节点对系统影响的差异性.

定义2.异质依存网络(Heterogeneousinterdependent network, HI Net)

设有向图$G=(V, E; \phi, \psi; A, R)$为一个异质网络, 元素集合$T_{a}$$T_{b}$为节点集合$V$或边集合$E$的子集, 且$T_{a}\bigcap T_{b}=\emptyset$$|T_{a}|>0$$|T_{b}|>0$.若存在集合$T_{a}$的状态$f(T_{a})$失稳(或失效)后会引起$T_{b}$状态$f(T_{b})$随着趋向于不稳定状态甚至失效, 记作:

$ \begin{split} \left\{ \begin{aligned} &f(T_{a})\rightarrow f'(T_{a})\sim f'(T_{b})\\ &f'(T_{b})_{\infty}\not\in[\zeta_{\rm{min}}, \zeta_{\rm{max}}]\\ \end{aligned} \right. \end{split} $ (1)

则称$G$为一个异质依存网络.其中$\zeta_{\rm{min}}$$\zeta_{\rm{max}}$为节点有效运行状态阈值.当$|T_{a}|=1$时, 称$T_{b}$$T_{a}$完全依存; $|T_{a}|>1$时, 称$T_{b}$$T_{a}$中元素部分依存.

定义2描述了异质依存网络的主要特征与性质, 所述异质节点间的依存关系可以是单向依存也可以为双向依存, 主要取决于不同系统中异质节点特性.

1.2 异质依存网络结构及其描述方法

对于异质依存网络节点的区分, 可以是根据节点介质出入度关系、节点功能、节点承载介质, 也可是网络中节点对应具体物理系统或信息系统的物理意义.同时, 根据不同的研究目标, 异质依存网络的表现形式可以是多样化的.以电力系统为例, 其异质依存网络的结构形式大致可分为三类.

图 1所示为根据节点异质性, 对电网进行多层网络分离或节点划分后的网络结构示意图. Sergey等根据节点承载介质特征, 将电力系统分割为图 1 (a)所示电力通信网与电网两层, 形成类似电力信息物理系统的概念来描述电网中多层异质网络依存关联, 并规定单边网络中节点均为同质节点.单层网络中节点通过网络路径进行介质(信息或电能)传递的有效路径.同时, 由于上层信息网负责下层电网节点的监控与控制, 而下层电网节点又对上层信息网节点进行供电, 两者是一种“相辅相成”的关系.

图 1 (b)根据电压等级对整个电网进行分层, 上层高压电网通过变电站降压之后对下层低压电网进行供电.同时, 各层电网中又由电源节点、变电节点、负荷节点三类基本异质节点构成, 形成有向异质网络.当上游节点失效后, 必然导致下层无其他供电路径的节点处于失电状态, 即异质节点间又存在依存关系, 是一种典型的分层结构下异质依存网络.此外, 得益于智能电网技术发展与电网深化改造, 现阶段电网已实现部分区域电网互联功能, 使得区域电网上级供电点故障失效后可由邻近互联电网进行供电, 在一定程度提升了网络可靠性.

图 1 (c)为一种典型的含多种分布式电源智能配电网结构, 可视作对图 1 (b)中单层网络异质节点细化分类, 将电源节点进一步划分为发电机单元与可再生能源单元(光伏、风机等).该网络具备之前所提高低压分层电网的分层特征, 但由于可再生能源节点输出功率的随机性与波动性, 无法对负荷节点进行独立供电.因此, 图 1 (c)中可再生能源节点对发电机节点也存在依存关系, 即负荷节点依存于异质电源节点, 而电源节点中可再生能源节点又依存于发电机单元节点.

图 1 (a)(b)对复杂网络进行了分层处理, 形成多层结构下的异质依存网络, 这种分层处理形象化体现了网络中异质节点间依存关系.然而, 即使是对异质网络进行一定程度的分层, 同一层网络其实依然存在进一步进行分层划分的可能.例如图 1 (a)中的信息网, 我们可以根据信息网中节点功能, 将信息节点区分为状态监测节点与调度节点, 且调度节点的有效性依存于状态监测节点.由此可知, 在进行异质节点区分和计算过程中, 分层处理可能是一个无止尽的过程.且当网络层数较多时, 由于需要对分层网络矩阵进行节点关联, 会进一步降低计算效率.

图 1 典型异质电网节点结构示例 Figure 1 Examples of heterogeneous power grid structure

此外, 由于将多层异质依存网络进行合并, 形成单层多异质依存网络并不改变网络中异质节点之间的依存关系.因此, 在实际计算分析过程中, 我们可将多层网络中异质节点融合在同一单层复杂网络中, 并构建对应的节点依存矩阵, 而不影响异质节点间依存关系表达.

图 2所示为一种具有$d$层结构的异质依存网络, 各层网络内部以及不同层中的节点可以是同质节点也可以是异质节点.不同网络层间节点的依存关系一般可分为三类: “一对一”、“一对多”、“多对一”. “一对一”依存关系指:两个节点数量相同的依存网络中, 各网络中节点在目标网络中有且只有一个依存节点对象, 具有唯一性(例如: 图 2中Layer2与Layer3之间的节点依存关系). “一对多”与“多对一”依存关系指不同异质依存网络中存在一个节点依存于不同层中多个节点或网络中存在多个节点同时依存于不同层中的某一节点(例如: 图 2中Layer1与Layer2之间的节点依存关系).对于此类多层异质依存网络, 可将其视为多个平行分区的单层异质依存网络, 并构建依存矩阵$S$:

$ S{\rm{ = }}\left[ \begin{array}{l} {S_{12}}\;\;\;{S_{13}}\;\;\; \cdots \;\;\;{S_{1d}}\\ {S_{21}}\;\;\; \ddots \;\;\;\;\;\;\;\;\;\;\; \vdots \\ \; \vdots \;\;\;\;\;\;\;\;\;\;\;\; \ddots \;\;\;\;\; \vdots \\ {S_{1d}}\;\; \cdots \;\;\;\; \cdots \;\;\;\;{S_{dd}} \end{array} \right] $ (2)
图 2 一种简单的多层异质依存网络 Figure 2 A simple multi-layer HI network

式中, $S$是由分块矩阵组成的多层异质依存网络依存矩阵, 通常为稀疏矩阵; 对角线矩阵${S_{dd}}$表示第$d$层网络内部节点依存关系, 且${S_{dd}}$中对角线元素全为零.非对角线上的矩阵元素为不同异质网络层之间异质节点的依存关系矩阵, 如${S_{d1}}$表示第$d$层网络中节点对第1层网络中节点的依存关系.

若不同层之间的节点依存关系为“一对一“依存, 则进一步存在:

$ \begin{equation} {S}_{d_{1}d_{2}}+{S}_{d_{2}d_{1}}=\varepsilon {I} \end{equation} $ (3)

式中, $d_{1}$$d_{2}$表示不同网络层的编号; ${I}$为单位矩阵; $\varepsilon$为依存关系系数, $\varepsilon\in \left\{1, 2\right\}$, $ \varepsilon =1$表示节点间为单向“一对一”依存, $\varepsilon =2$表示节点间双向“一对一”依存.

异质依存网络描述了一种含多类型元素(节点或边)复杂网络中, 同质元素、异质元素之间的依存性关联.例如:通信骨干网中, 路由群依存于上级服务器节点, 同时单一路径上离服务器较远的路由节点又依存于离服务器较近的节点.

定义3.异质节点间接依存

在异质依存网络$G=(V, E; \phi, \psi; A, R)$中, 存在元素集合$T_{a}$$T_{b}$$T_{c}$, 且集合间两两交集为${\emptyset}$. $T_{a}$$T_{b}$$T_{b}$$T_{c}$之间的依存路径集合$\Gamma_{ab}$$\Gamma_{bc}$为非空集合, $T_{a}$$T_{c}$之间依存路径集合$\Gamma_{ac}=\Gamma_{ab}\bigcup \Gamma_{bc}$.若当$f(T_{a})\rightarrow f'(T_{a})$时, 同时存在:

$ \begin{split} \left\{ \begin{aligned} &f'(T_{b})_{\infty}\not\in[\zeta^{b}_{\rm{min}}, \zeta^{b}_{\rm{max}}]\\ &f'(T_{c})_{\infty}\not\in[\zeta^{c}_{\rm{min}}, \zeta^{c}_{\rm{max}}]\\ \end{aligned} \right. \end{split} $ (4)

则称$T_{c}$$T_{a}$存在间接依存关系.

定义3给出了异质依存网络中非邻域节点之间状态耦合性与依存性之间关系.在异质依存网络中, 沿依存路径上的非邻居节点均存在效用互耦合性.且随着故障传播路径上异质节点对扰动的吸收, 故障节点对其远端节点的扰动影响可能随着下降.

$ \begin{equation} \Delta f'(t_{c})=\gamma_{a\rightarrow c}\Delta f'(t_{a}) \end{equation} $ (5)

式中, $t_{a}$$t_{c}$为异质依存网络中存在于可达依存路径上的元素对象; $\Delta f'(t_{c})$为由$t_{a}$状态变化水平$\Delta f'(t_{a})$引起的$t_{c}$状态变化程度; $\gamma_{a\rightarrow c}$$t_{c}$$t_{a}$的效用耦合系数, 其中: $\gamma_{a\rightarrow c}\in (0, 1]$.当$\gamma_{a\rightarrow c}=1$时, $t_{c}$$t_{a}$的状态变化具有一致性特征.特别说明的是, 若异质依存网络中节点为双向依存, $t_{a}$$t_{c}$之间的效用互耦合系数可能不同, 即$\gamma_{a\rightarrow c}\neq \gamma_{c\rightarrow a}$.

2 异质依存网络衰退过程

根据上述异质依存网络定义及相关特征, 可知异质节点之间依存关系可分为:完全依存、部分依存、间接依存3类.当异质依存网络中节点状态发生变化, 会直接完全作用于完全依存节点, 并通过依存路径影响网络其他节点运行状态.这种运行状态的转移可能是效用水平下降也可能是节点失效, 并通过依存节点间的传递扩散至整个网络, 形成异质依存网络的衰退.在工业系统中, 节点效用水平下降也可能最终导致节点失效.以图 3所示电力中信息物理网的典型异质依存网络为例, 进一步描述异质依存网络中某节点失效后对网络结构以及其他节点的衰退过程.

图 3 电力信息异质依存网络衰退过程 Figure 3 Degeneration process of power-information HI Net

图 3所示为典型工业系统中电力信息异质依存网络, 其中信息节点由电力节点进行供电(即当电网节点实效后其供电的信息节点立即失效), 是一种完全依存关系.网络共包含12个异质节点, 网络中异质节点类型有:信息节点、负荷节点、发电机节点以及可再生能源节点, 路径方向为各节点间不完全依赖于实际物理路径的依存路径方向.由图 3所示结构衰退过程可知, 当电力信息异质依存网络中发电机节点失效后, 依存于该发电机的信息节点、负荷节点以及可再生能源节点失效.然而, 通过失效节点形成网络结构的衰退, 并最终退化为一个不完全依赖于失效节点, 可独立存在的异质依存网络.

根据上述典型异质依存网络衰退过程, 可知:对于一个异质依存网络, 当某一节点失效引起网络衰退时, 该衰退过程只能通过依存路径在可达距离内进行传播.且对于部分依存节点, 故障不一定会导致其失效.此外, 区别于现有依存网络概念, 异质依存网络的依存路径可能并不依赖于实际网络链路, 可以是一种跨越网络介质传输路径方向的异质节点依存关系.例如图 3中可再生能源节点与发电机节点并非直接相连, 但由于节点功率特征的依存关系, 当可再生能源节点所依存的发电机失效时, 可再生能源节点也直接失效.

性质1.  对于异质依存网络$G=(V, E; \phi, \psi; A, R)$, 存在节点$v_{i}$$v_{j}$$v_{k}$满足: $f(v_{i})\sim f(v_{j})$, $f(v_{i})\sim f(v_{k})$, 若$\gamma_{i\rightarrow j}=1$, $\gamma_{i\rightarrow k}\in (0, 1)$, 则当$v_{i}$失效后, $v_{j}$必然趋于不稳定直至失效, 而$v_{k}$可能依然存在.

性质2.  异质依存网络$G=(V, E; \phi, \psi; A, R)$中异质节点$v_{i}$$v_{j}$, 若异质节点间介质传输路径$E_{ij}={\emptyset}$, 依存路径$\Gamma_{ki}\neq {\emptyset}$, 且$v_{j}$对于网络中其他节点存在$\Gamma_{ki}= {\emptyset}$, 则当$f'(v_{i})\not\in[\zeta^{i}_{\rm{min}}, \zeta^{i}_{\rm{max}}]$时, 依然会导致$v_{j}$趋向于失效$f'(v_{j})_{\infty}\not\in[\zeta^{j}_{\rm{min}}, \zeta^{j}_{\rm{max}}]$.

3 关键节点识别方法 3.1 邻域节点效用耦合

异质依存网络中节点重要性程度可转换为节点失效后对网络运行稳定性、完整性以及剩余节点生存强度等方面的影响.在网络结构固定时, 网络内异质节点间的依存关系相对固定.以单层异质依存网络为研究对象, 根据异质依存网络依存路径、异质节点类型, 建立节点依存矩阵:

$ \mathit{\boldsymbol{S}}{\rm{ = }}\left[ \begin{array}{l} \;0\;\;\;{s_{12}}\;\;\; \cdots \;\;\;{s_{1L}}\\ {s_{21}}\;\;\;0\;\;\;\; \cdots \;\;\;{s_{2L}}\\ \; \vdots \;\;\;\;\; \vdots \;\;\;\;\; \ddots \;\;\;\; \vdots \\ {s_{L1}}\;\;{s_{L2}}\;\;\; \cdots \;\;\;0 \end{array} \right] $ (6)

式中, $L$为节点个数; $s_{ji}$表示节点$v_{j}$在网络中有效存在性对$v_{i}$的效用依存程度.特别的, 对于异质网络中不依存于介质传输路径的节点间依存关系, 构建图 5所示虚拟依存路径.

图 5 邻域节点群依存结构 Figure 5 Dependency structure of neighborhood nodes

图 5所示为在异质依存网络中, $v_{i}$部分依存于$v_{j}$, 然而$v_{i}$$v_{j}$之间虽然存在链路, 但并不存在可行依存路径, 无法直接根据网络邻接矩阵表达$v_{i}$依存于$v_{j}$的关系.因此, 建立虚拟依存路径$s_{ij}$, 并借鉴基尔霍夫定律, 可得:

$ \begin{equation} s_{ij}=\sum s_{ki}-\sum s_{ih} \end{equation} $ (7)

式中, $s_{ki}$为节点集合$\left\{ v_{k} \right\}$$v_i$的效用值, $v_{k}$依存于$v_{j}$; $s_{ih}$$v_{i}$对节点集合$\left\{ v_{h} \right\}$的效用值, $v_{i}$依存于$v_{h}$.

图 4 节点虚拟依存路径示意图 Figure 4 Virtual dependency path between nodes

在异质依存网络中节点故障失效首先影响的是其邻域节点群, 其次再是通过依存路径传播至网络其他异质节点.在故障传播过程中, 异质节点可能是故障接收点, 也是故障传播者.因此, 综合考虑$v_{i}$依存于其他节点以及被其他节点依存强度来评估节点重要性.以图 5所示邻域节点依存结构论述节点$v_{i}$对邻域节点重要性计算方法.

图 5所示为一种典型的邻域节点依存关系结构, 边方向表示节点依存关系(包含了直接依存与虚拟依存), 边权重$s$为节点依存水平.由于$v_{k}$同时依存于$v_{i}$$v_{h}$, 因此考虑节点间效用耦合性与依存关联, 对效用依存度进行二次分配.

$ \begin{equation} w_{ki}=\dfrac{\dfrac{S_{ki}}{\sum\limits_{h\in \Omega^{\rm{out}}_{k}}S_{kh}}}{\sum\limits_{k\in \Omega^{\rm{in}}_{i}}\left(\dfrac{S_{ki}}{\sum\limits_{h\in \Omega^{\rm{out}}_{k}}S_{kh}}\right)}\gamma_{k} \end{equation} $ (8)

式中, $w_{ki}$为二次分配后的边权重; $\Omega^{\rm{out}}_{k}$$v_{k}$依存的节点集合, $\Omega^{\rm{in}}_{i}$为依存于$v_{i}$的节点集合; $\gamma_{k}$$v_{k}$与其邻域节点群的初始效用耦合系数之和, $\gamma_{k}=\sum_{h'\in\Omega^{\rm{in}}_{k}}\gamma_{kh'}+\sum_{h''\in \Omega^{\rm{in}}_{k}\gamma_{kh''}}$

$w_{ki}$表征了依存路径上相邻节点间有效存在的依赖程度.同理, 可得:

$ \begin{equation} w_{ij}=\frac{S_{ij}}{\sum\limits_{j\in \Omega^{\rm{out}}_{i}}}\gamma_{j} \end{equation} $ (9)

式中, $\Omega^{\rm{out}}_{i}$为被$v_{i}$所依存的节点集合.为进一步评估节点失稳或失效对网络风险的不确定性, 即系统可能崩溃的不确定性测度, 采用效用耦合反应异质节点对邻域节点群构成的邻域节点网络风险的影响力.首先对二次分配后的边权重分别进行归一化处理.

$ \begin{equation} \begin{split} \left\{ \begin{aligned} &p_{ki}=\dfrac{s_{ki}}{\sum \limits_{{k}\in \Omega^{\rm{in}}_{i}}s_{ki}}\\ &p_{ij}=\dfrac{s_{ij}}{\sum \limits_{{j}\in \Omega^{\rm{out}}_{i}}s_{ij}} \end{aligned} \right. \end{split} \end{equation} $ (10)

由于$\sum p_{ki}=\sum p_{ij}=1$, 可得分别由依存于$v_{i}$的节点以及被$v_{i}$所依存节点构成的邻域节点网络效用耦合为

$ \begin{split} \left\{ \begin{aligned} &T^{\rm{in}}_{i}=\left(1-\sum p_{ki}\ln p_{ki}\right)\sum w_{ki}\\ &T^{\rm{out}}_{i}=\left(1-\sum p_{ij}\ln p_{ij}\right)\sum w_{ij} \end{aligned} \right. \end{split} $ (11)

式中, $T^{\rm{in}}_{i}$$T^{\rm{out}}_{i}$分别为依存于$v_{i}$和被$v_{i}$依存的邻域网络效用耦合.

由此可得$v_{i}$对整个邻域节点群构成的邻域依存节点网络综合效用耦合$T_{i}$ :

$ \begin{equation} T_{i}=T^{\rm{in}}_{i}+T^{\rm{out}}_{i} \end{equation} $ (12)
3.2 耦合性动态传播策略

局部依存网络效用耦合系数$T_{i}$反映了节点$v_{i}$对邻域局部网络的重要性.在故障传播过程中, 故障节点首先将状态变化耦合传播至邻域节点, 再通过邻域节点逐步传递至其相邻的节点群, 直至故障扩散至整个异质依存网络其他节点.对于异质依存网络而言, 我们可以将其视作由$N$个邻域局部网络组成($N$为节点个数), 且邻域局部网络之间必然存在节点交集.

图 6所示, 异质依存网络中各相邻的邻域网络存在一个或多个相交节点, 形成多个效用互耦合的邻域节点网络.在节点效用耦合计算过程中, 由于邻域节点网络的互耦合性, 各节点的效用耦合值会随着其邻居节点的效用耦合变化而变化.例如: 图 6中节点$v_{1}$$v_{2}$$v_{3}$为三个相邻的异质节点, 并分别形成以各自为中心的三个邻域节点网络.在第一次节点评估过程中, 各节点均根据其邻域节点初始的耦合性水平进行邻域网络效用耦合计算.然而, 由于$T_{v1}$$T_{v2}$$T_{v3}$的效用水平是互相关联的, 当任意相邻的节点效用发生变化时, 自身的效用值也应得到相应的更新.因此, 节点效用耦合的计算是一个动态迭代变化的过程, 并最终达到一个平衡状态.

图 6 邻域网络状态耦合反馈 Figure 6 State coupling feedback of neighborhood network

在复杂网络研究中, 通常采用PageRank算法分析该类节点互相状态下的节点评估[13-14].考虑异质依存网络中节点间接依存关以及异质节点间的依存关系, 基于PageRank算法思想进行节点交叉依存强度传播, 实现节点间沿依存方向的影响力二次传播.该算法根据节点依存路径方向, 采用式(13)所示平均分配的方法[13], 通过对不同节点间影响力的迭代传播, 计算依存路径末端节点获得起点的影响力程度, 实现节点重要度二次排序.

$ \begin{equation} {\rm PR}(x)=\frac{1-\sigma}{L}+\sigma\sum\limits_{i=1}\limits^{L}\frac{{\rm PR}(Y_{i})}{c^{\rm{out}}_{Y_{i}}} \end{equation} $ (13)

式中, ${\rm PR}(x)$为节点$x$的PageRank值; ${\rm PR}(Y_{i})$为链接至$x$的节点PageRank值; $L$为节点总数, 即节点数量; $\sigma$为阻尼系数, 通常设置$\sigma=0.85$[15]; $c^{\rm{out}}_{Y_{i}}$为第$i$个链接至节点$x$的出度值.

由于PageRank算法通过固定路径, 以依存路径方向为传播方向进行节点状态传播与迭代, 即节点的重要性只与依存路径上依存方向的指向有关, 依存指向越多的节点则其越重要, 该方法忽略了节点失效对依存路径上游节点功能有效性的影响, 即网络结构完整性.由此, 本文对PageRank算法进一步改进, 提出Bi-PageRank算法, 实现节点间双向效用耦合传播.

$ \begin{split} &T^{(t+1)}_{i}=T^{(t)}_{i}+\sigma\left(\dfrac{w_{ij}} {\sum\limits_{j\in \Omega^{\rm{out}}_{i}}w_{ij}}T_{j}^{(t)}+ \dfrac{w_{ki}}{\sum\limits_{k\in \Omega^{\rm{in}}_{i}}w_{ki}}T_{k}^{(t)}\right)=\\ &T^{(t)}_{i}+\sigma\left(\dfrac{S_{ij}}{\sum\limits_{j\in \Omega^{\rm{out}}_{i}}S_{ij}}T_{j}^{(t)}+\dfrac{\dfrac{S_{ki}}{\sum\limits_{h\in \Omega^{\rm{out}}_{k}}S_{kh}}}{\sum\limits_{k\in\Omega^{\rm{in}}_{i}}\left(\dfrac{S_{ki}}{\sum\limits_{k\in \Omega^{\rm{out}}_{i}}S_{kh}}\right)}T_{k}^{(t)}\right) \end{split} $ (14)

图 7所示为关键节点评估算法流程图, 其中, ${\rm norm}(\cdot)$为节点耦合效用耦合系数向量的1-范数; $sig$为迭代终止阈值.评估过程中, 首先, 固定异质节点类型与介质传输路径, 分析异质节点间效用依存关系, 确定网络节点间的依存路径.然后, 所有节点形成各自领域节点网络, 并根据邻域效用耦合系数对效用依存度进行二次分配, 并采用效用耦合系数评估节点对其领域节点群运行状态(运行稳定性或运行有效性)的影响.为进一步辨识节点状态对整个异质依存网络运行状态的影响, 采用所提Bi-PageRank算法实现节点效用耦合系数在网络中的双向传播, 实现关键节点评估.特别说明的是, 应用所提方法进行关键节点评估时, 应根据异质依存网络特征以及故障类型, 选择相应节点效用耦合系数取值方法, 以评判特定故障背景下的节点对网络运行状态的影响程度.

图 7 关键节点评估流程 Figure 7 Flow chart of key nodes assessment
3.3 算法复杂度分析

对于一个具有$L$个异质节点, $M$条依存路径的异质依存网络, 其依存矩阵${ S}$一般为稀疏矩阵.因此, 关键节点辨识方法的空间复杂度为O$(n^{2})$.对于时间复杂度而言, 在迭代过程中依存矩阵与效用耦合向量相乘的时间复杂度为O$(n^{2})$.假设Bi-PageRank算法迭代次数为常数$\epsilon$, 则关键节点辨识过程迭代计算的总体时间复杂度为O$(\epsilon n^{2})$.

4 仿真计算与结果分析 4.1 仿真实验对象

由于节点故障类型的不同, 系统的故障特征与传播范围也会不同.因此, 以IEEE标准电力节点测试系统作为典型的异质依存网络, 分别以网络状态衰退与结构衰退作为实验故障类型, 辨识不同故障类型下关键节点.

网络状态衰退指异质节点发生运行状态振荡或失稳时, 对网络整体运行稳定性的影响.结构衰退指节点直接失效引起依存路径上其他节点失效时, 主要针对网络结构完整性, 即网络运行可靠性.

4.2 网络状态衰退

IEEE39节点测试系统有10台发电机单元与17个负载节点构成, 运行频率为60 Hz[16].系统结构如图 8所示.

图 8 IEEE 39节点测试系统 Figure 8 IEEE 39-node test system

以电力系统节点三相接地短路引起电压波动, 导致系统其他节点运行暂态振荡作为故障类型, 辨识在该故障情形下的关键节点.根据文献[17-18]可知, 电力系统中节点间运行稳定性耦合关联可用等效电气阻抗来表示.因此, 定义节点效用耦合系数$\gamma_{ij}$

$ \begin{split} \begin{aligned} \gamma_{ij}= &{\rm ln}\frac{1}{Z_{ij}}={\rm ln}\left[\frac{1}{(Z_{ii}-Z_{ij})-(Z_{ij}-Z_{jj})}\right]=\\ &{\rm ln}\left[\frac{1}{Z_{ii}+Z_{jj}-2Z_{ij}}\right]\\ \end{aligned} \end{split} $ (15)

式中, $Z_{ij}$为邻居节点$v_{i}$$v_{j}$之间的等效电气阻抗; $Z_{ii}$$Z_{jj}$为节点自阻抗; $Z_{ij}$为节点间线路阻抗.

在PSCAD电磁暂态仿真软件中对测试系统各节点分别进行三相接地故障仿真实验, 分析节点状态变化对系统状态稳定性影响, 得到图 9所示系统电压振荡幅度曲线与不同振荡幅度节点数量.

图 9 IEEE 39节点系统不同节点三相接地时系统暂态状态 Figure 9 Transient state of IEEE 39-node system when three-phase ground fault occurs to different node

图 9所示, 不同异质节点发生故障导致系统电压振荡幅度百分比$\Delta U \%$与传播范围均存在一定差异性.若节点故障引起系统电压振荡越大, 则该关键节点出现重大故障时, 较易导致系统失稳甚至崩溃.因此, 进一步将节点故障引起的系统与其重要性评估结果进行关联.

图 10所示为将计算所得节点重要度与其故障引起的系统电压振荡幅度的关联散点图.由图 10可知, 采用所提关键节点评估可较好地辨识对系统稳定性较大的关键节点.同时, 所提方法在考虑节点故障对系统状态的基础上, 辅助考虑了系统状态衰退范围因素.例如节点6与节点10网络效用耦合系数分别为: $T_{6}=0.3847$, $T_{10}=0.3852$.出现三相接地故障后, 导致的系统电压振荡分别为$\Delta U_{6} \%=6.495 \%$, $\Delta U_{10} \%=6.275 \%$.然而, 由于节点10故障后, 依存路径上存在较多电压振荡超5 %的节点, 在依存路径上具有较强的状态耦合传播能力.即当节点10出现故障时, 该故障导致的节点状态衰退可传播至更多的节点.因此, 在最终的关键节点评估结果中, 节点6与节点10的重要性近似相等.

图 10 IEEE 39节点系统节点重要度与状态衰退时节点电压振荡 Figure 10 Node importance and the voltage oscillation caused by state degeneration in IEEE 39-node system
4.3 网络结构衰退

以电力系统中的信息物理融合系统作为异质依存网络, 验证所提关键节点辨识方法对网络结构衰退故障下的关键节点辨识有效性.在IEEE 118节点电网测试系统中采用Barabasi-Albert模型随机生成信息系统链路结构, 并规定电网物理层节点与信息层节点为“一对一”依存.即电网层的节点对信息层中节点进行供电, 当电网节点实效后, 其对应的信息节点也立即失效, 导致2个网络结构的衰退.对于有效性依存的电力信息异质依存网络, 节点效用耦合系数$\gamma_{ij}=1/n_{\rm{dep}}$, $n_{\rm{dep}}$为节点依存对象数量.

根据式(2)构建电力信息物理依存网络矩阵:

$ \begin{equation} {{S}} = \left[ {\begin{array}{*{20}{c}} {{{{{s}}}_{\rm{inf}}}}&{{I}}\\ {{0}}&{{{{{s}}}_{\rm{gri}}}} \end{array}} \right] \end{equation} $ (16)

式中, ${S}$为信息物理网络依存矩阵; ${{{{s}}}_{\rm{inf}}}$为信息网络节点依存矩阵; ${{{{s}}}_{\rm{gri}}}$为电网层节点依存矩阵; $I$为单位矩阵.

采用网络失效节点比例判定节点失效对网络结构完整性的影响.

$ \begin{equation} \eta=\frac{L^{\rm{loss}}_{\rm{inf}}+L^{\rm{loss}}_{\rm{gri}}}{L_{\rm{inf}}+L_{\rm{gri}}} \end{equation} $ (17)

式中, $L^{\rm{loss}}_{\rm{inf}}$$L^{\rm{loss}}_{\rm{gri}}$分别为信息网与电网中节点失效数量; $L_{\rm{inf}}$$L_{\rm{gri}}$分别为信息网与电网的节点总数, 在“一对一”依存的电力信息异质依存网络中, $L_{\rm{inf}}=L_{\rm{gri}}$.

为保证结果的一般性, 对电力信息物理异质依存网络进行20次网络结构衰退测试, 得到图 11所示节点重要度指标与对应网络结构衰退失效节点比例关联图.

图 11 IEEE 118节点系统节点重要度与网络结构衰退失效节点比例 Figure 11 Node importance and failure node ratio caused by network structure degeneration in IEEE 118-node system

图 11所示为电力信息物理异质依存网络中节点重要度与网络结构衰退引起的失效节点比例散点关联图.由于电力节点与信息节点是“一对一”依存, 因此纵轴节点重要度为电力节点与对应信息网节点的重要度之和.由图 11可知, 所提关键节点可较好地识别出对网络结构完整性较大的节点, 即关键节点失效引起网络结构衰退时, 异质依存网络中会出现较多的依存路径上的其他节点失效.对于实际电力信息物理网络, 相关规划人员可根据所提方法识别结果对关键节点进行针对性保护, 防止物理设备故障失效后引起网络结构衰退, 导致电网供电中断.

5 结语

针对现实工业网中节点多样化、传输路径与结构相对固定等特征, 通过分析现有网络中各节点类型与依存关系, 提出了异质依存网络理论, 并异质网络理论中异质节点依存关系与网络衰退特征.针对现有复杂网络节点重要性评估方法对未考虑节点间依存性与连锁故障之间关系的问题, 提出基于邻域节点效用耦合与影响力传播的关键节点识别方法, 用于评估节点运行状态变化对网络结构、传播路径上其他节点运行状态方面的影响.

另外, 现实异质依存网络可能存在因同质元素特征参数差异导致各元素间依存关系或程度不同的现象.例如:通信网络中同层同类路由节点单元最大传输速度与容量限制对网络性能的影响; 电力网络因发电机单元最大输出功率限制, 其功率可达路径有限, 导致网络中不同位置可再生能源对发电机的依存性不同等.因此, 在进行后续异质依存网络研究工作时, 可在本文已有研究成果的基础上, 根据具体技术需求对网络元素特征进一步细化分析.同时, 本文为简化异质依存网络分析过程, 并满足关键节点辨识方法的一般通用性, 在进行仿真实验时假设各同质节点具有特征一致性.

参考文献
1
Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, 2017, 66(3): Article No.038902.
( 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): Article No.038902.)
2
Wei Xiang, Zhao Jun-Chan, Hu Chun-Hua. Generalized synchronization and system parameters identification between two different complex networks. Acta Automatica Sinica, 2017, 43(4): 595-603.
( 韦相, 赵军产, 胡春华. 两个异构复杂网络的广义同步与参数识别. 自动化学报, 2017, 43(4): 595-603.)
3
Xie Qiong-Yao, Deng Chang-Hong, Zhao Hong-Sheng, Weng Yi-Xuan. Evaluation method for node importance of power grid based on the weighted network model. Automation of Electric Power Systems, 2009, 33(4): 21-24.
( 谢琼瑶, 邓长虹, 赵红生, 翁毅选. 基于有权网络模型的电力网节点重要度评估. 电力系统自动化, 2009, 33(4): 21-24. DOI:10.7500/AEPS200805140)
4
Yu Xin, Li Yan-He, Zheng Xiao-Ping, Zhang Han-Yi, Guo Yi-Li. Node importance evaluation based on communication network performance grads. Journal of Tsinghua University (Science & Technology), 2008, 48(4): 541-544.
( 余新, 李艳和, 郑小平, 张汉一, 郭奕理. 基于网络性能变化梯度的通信网络节点重要程度评价方法. 清华大学学报(自然科学版), 2008, 48(4): 541-544.)
5
Fu Xiu-Wen, Li Wen-Feng, Duan Ying. Invulnerability of clustering wireless sensor network towards cascading failures. Journal of Computer Research and Development, 2016, 53(12): 2882-2892.
( 符修文, 李文锋, 段莹. 分簇无线传感器网络级联失效抗毁性研究. 计算机研究与发展, 2016, 53(12): 2882-2892. DOI:10.7544/issn1000-1239.2016.20150455)
6
Wu Run-Ze, Zhang Bao-Jian, Tang Liang-Rui. A cascading failure based nodal importance evaluation method applied in dual network coupling model. Power System Technology, 2015, 39(4): 1053-1058.
( 吴润泽, 张保健, 唐良瑞. 双网耦合模型中基于级联失效的节点重要度评估. 电网技术, 2015, 39(4): 1053-1058.)
7
Zhao L, Park K, Lai Y C. Attack vulnerability of scale-free networks due to cascading breakdown. Physical Review E, 2004, 70(2): Article No.035101.
8
Tang L, Jing K, He J, Stanley H E. Complex interdependent supply chain networks:cascading failure and robustness. Physica A:Statistical Mechanics and Its Applications, 2016, 443: 58-69. DOI:10.1016/j.physa.2015.09.082
9
Xie Feng, Cheng Su-Qi, Chen Dong-Qing, Zhang Guo-Qiang. Cascade-based attack vulnerability in complex networks. Journal of Tsinghua University (Science & Technology), 2011, 51(10): 1252-1257.
( 谢丰, 程苏琦, 陈冬青, 张国强. 基于级联失效的复杂网络抗毁性. 清华大学学报(自然科学版), 2011, 51(10): 1252-1257.)
10
Buldyrev S V, Parshani R, Paul G, Stanley H E, Havlin S. Catastrophic cascade of failures in interdependent networks. Nature, 2010, 464(7291): 1025-1028. DOI:10.1038/nature08932
11
Gao J X, Buldyrev S V, Stanley H E, Havlin S. Networks formed from interdependent networks. Nature Physics, 2012, 8(1): 40-48. DOI:10.1038/nphys2180
12
Sun Y Z, Han J W, Yan X F, Yu P S, Wu T Y. PathSim:meta path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB Endowment, 2011, 4(11): 992-1003.
13
Boldi P, Santini M, Vigna S. PageRank:functional dependencies. ACM Transactions on Information Systems, 2009, 27(4): Article No.19.
14
Eom Y H, Shepelyansky D L. Opinion formation driven by PageRank node influence on directed networks. Physica A:Statistical Mechanics and Its Applications, 2015, 436: 707-715. DOI:10.1016/j.physa.2015.05.095
15
Wu X D, Kumar V, Quinlan J R, Ghosh J, Yang Q, et al. Top 10 algorithms in data mining. Knowledge and Information Systems, 2008, 14(1): 1-37.
16
Pai M A. Energy Function Analysis for Power System Stability. London: Kluwer Academic Publishers, 1989.
17
Wang K, Zhang B H, Zhang Z, Yin X G, Wang B. An electrical betweenness approach for vulnerability assessment of power grids considering the capacity of generators and load. Physica A:Statistical Mechanics and Its Applications, 2011, 390(23-24): 4692-4701. DOI:10.1016/j.physa.2011.07.031
18
Arianos S, Bompard E, Carbone A, Xue F. Power grid vulnerability:a complex network approach. Chaos, 2009, 19(1): Article No.013119.