基于相继故障信息的网络节点重要度演化机理分析

分析了过载机制下节点重要度的演化机理.首先,在可调负载重分配级联失效模型基础上,根据节点失效后其分配范围内节点的负载振荡程度,提出了考虑级联失效局域信息的复杂网络节点重要度指标.该指标具有两个特点:一是值的大小可以清晰地指出节点的失效后果;二是可以依据网络负载分配范围、负载分配均匀性、节点容量系数及网络结构特征分析节点重要度的演化情况.然后,给出该指标的仿真算法,并推导了最近邻择优分配和全局择优分配规则下随机网络和无标度网络节点重要度的解析表达式.最后,实验验证了该指标的有效性和可行性,并深入分析了网络中节点重要度的演化机理,即非关键节点如何演化成影响网络级联失效行为的关键节点.     

利用重要度评价矩阵确定复杂网络关键节点

为了对复杂网络节点重要度进行评估,针对节点删除法、节点收缩法和介数法的不足,通过定义节点效率和节点重要度评价矩阵, 提出了一种利用重要度评价矩阵来确定复杂网络关键节点的方法.该方法综合考虑了节点效率、节点度值和相邻节点的重要度贡献,用节点度值和效率值来表征其对相邻节点的重要度贡献,其优化算法的时间复杂度为O(Rn²). 实验分析表明该方法可行有效,对于大型复杂网络可以获得理想的计算能力.     

带有层级结构的复杂网络级联失效模型

针对现实世界的网络中普遍存在的层级结构建立一个级联失效模型, 该模型可用于优化金融、物流网络设计. 选择的层级网络模型具有树形骨架和异质的隐含连接, 并且骨架中每层节点拥有的分枝数服从正态分布. 级联失效模型中对底层节点的打击在不完全信息条件下进行, 也即假设打击者无法观察到隐含连接. 失效节点的负载重分配考虑了层级异质性, 它可以选择倾向于向同级或高层级完好节点分配额外负载. 仿真实验表明, 层级网络的拓扑结构随连接参数变化逐渐从小世界网络过渡到随机网络. 网络级联失效规模随隐含连接比例呈现出先增加后降低的规律. 负载重分配越倾向于高层级节点, 网络的抗毁损性越高. 同时, 由于连接参数会改变隐含连接在不同层级之间的分布, 进而对网络的抗毁损性产生显著影响, 为了提高网络抗毁损能力, 设计网络、制定管理控制策略时应合理设定连接参数. 关键词： 复杂网络 级联失效 层级结构     

面向结构洞的复杂网络关键节点排序

复杂网络中的结构洞节点对于信息传播具有重要作用, 现有关键节点排序方法多数没有兼顾结构洞节点和其他类型的关键节点进行排序. 本文根据结构洞理论与关键节点排序相关研究选取了网络约束系数、介数中心性、等级度、效率、网络规模、PageRank值以及聚类系数7个度量指标, 将基于ListNet的排序学习方法引入到复杂网络的关键节点排序问题中, 融合7个度量指标, 构建了一个能够综合评价面向结构洞节点的关键节点排序方法. 采用模拟网络和实际复杂网络进行了大量实验, 人工标准试验结果表明本文排序方法能够综合考虑结构洞节点和核心节点, 关键节点排序与人工排序结果具有较高的一致性. SIR传播模型评估实验结果表明由本文选择TOP-K节点发起的传播能够在较短的传播时间内达到最大的传播范围.     

基于节点负荷失效的网络可控性研究

Liu和Barabasi将现代控制理论应用到线性系统的网络可控性问题上, 提出了最小驱动节点集的计算方法, 解决了复杂网络控制的可计算问题. 针对现实网络中存在的节点因负荷过载而失效的问题, 本文提出了基于节点负荷失效的网络可控性模型. 通过对网络采用介数和Weibull失效模型, 在随机和目标失效机制下进行仿真, 研究结果表明: 维持无标度网络可控性的难度要明显大于随机网络; 在目标节点失效机制下, 即使对网络输入极少的失效信号, 也能极大地破坏网络的可控性; 使高介数节点失效要比使度高节点失效更能破坏网络的可控性, 说明高介数节点在维持网络可控性上发挥着重要作用; 对不同的负荷失效模型, 要合理采取措施, 防止网络发生阶跃性全不可控现象. 关键词： 网络可控性 结构可控性 节点失效     

利用邻域“结构洞”寻找社会网络中最具影响力节点

识别复杂网络中的关键节点对网络结构优化和鲁棒性增强具有十分重要的意义. 经典的关键节点测量方法在一定程度上能够辨识网络中影响力节点, 但存在一定局限性: 局部中心性测量方法仅考虑节点邻居的数目, 忽略了邻居间的拓扑关系, 不能在计算中反映邻居节点间的相互作用; 全局测量方法则由于算法本身的复杂性而不能应用于大规模社会网络的分析, 另外, 经典的关键节点测量方法也没有考虑社会网络特有的社区特征. 为高效、准确地辨识具有社区结构的社会网络中最具影响力节点, 提出了一种基于节点及其邻域结构洞的局部中心性测量方法, 该方法综合考虑了节点的邻居数量及其与邻居间的拓扑结构, 在节点约束系数的计算中同时体现了节点的度属性和“桥接”属性. 利用SIR(易感-感染-免疫)模型在真实社会网络数据上对节点传播能力进行评价后发现, 所提方法可以准确地评价节点的传播能力且具有强的鲁棒性.     

一种基于效率矩阵的网络节点重要度评价算法

为了实现对网络节点重要性的有效评价,提出一种基于网络效率矩阵的节点重要度评价算法.该方法综合考虑节点的度值(局部重要度)和网络节点之间的重要性贡献(全局重要度),利用节点的度和效率矩阵表征网络节点的重要度贡献,克服重要性贡献矩阵法中节点只依赖于邻接节点的不足.考虑实际网络的稀疏性,该算法的时间复杂度为O(n²).通过算例分析验证了该算法的可行性和有效性,结果表明:该算法能够更加直观、简单有效地区分节点的重要度差异,并且对于大型复杂网络具有较理想的计算能力.     

基于度与集聚系数的网络节点重要性度量方法研究

网络中节点重要性度量对于研究网络的鲁棒性具有十分重要的意义. 研究者们普遍运用度或集聚系数来度量节点的重要程度, 然而度指标只考虑节点自身邻居个数而忽略了其邻居之间的信息, 集聚系数只考虑节点邻居之间的紧密程度而忽略了其邻居的规模. 本文综合考虑节点的邻居个数, 以及其邻居之间的连接紧密程度, 提出了一种基于邻居信息与集聚系数的节点重要性评价方法. 对美国航空网络和美国西部电力网进行的选择性攻击实验表明, 采用该方法的效果较k-shell指标可以分别提高24%和112%. 本文的节点重要性度量方法只需要考虑网络局部信息, 因此非常适合于对大规模网络的节点重要性进行有效分析. 关键词： 网络科学 鲁棒性 节点重要性 集聚系数     

无线传感器网络中无标度拓扑的动态容错性分析

增强网络的动态容错性对于抵御级联失效具有重要的现实意义.根据无线传感器网络无标度拓扑中节点可变负载和恒定容量的特点建立级联失效模型,在随机节点失效下研究负载参数和拓扑参数对其级联失效容错性的影响规律,解析推导出该网络大规模级联失效的承载极限,同时模拟结果发现该网络的级联失效容错性与其度分布系数和幂指数正相关.这为从参数优化角度抵御随机节点失效下无线传感器网络无标度拓扑级联失效危害提供了依据.     

基于可调负载重分配的无标度网络连锁效应分析

为了深入研究复杂网络抵制连锁故障的全局鲁棒性,针对现实网络上的负载重分配规则常常是介于全局分配与最近邻分配、均匀分配与非均匀分配的特点,围绕负荷这一影响连锁故障发生和传播最重要的物理量以及节点崩溃后的动力学过程,提出了一种可调负载重分配范围与负载重分配异质性的复杂网络连锁故障模型,并分析了该模型在无标度网络上的连锁故障条件.数值模拟获得了复杂网络抵制连锁故障的鲁棒性与模型中参数的关系.此外,基于网络负载分配规则的分析以及理论解析的推导,验证了数值模拟结论,也证明在最近邻与全局分配两种规则下都存在负载分配均匀性参数等于初始负荷强度参数即β=τ使得网络抵御连锁故障的能力最强.     

Robustness measurement of scale-free networks based on motif entropy

As a classical complex network model, scale-free network is widely used and studied. And motifs, as a high-order subgraph structure, frequently appear in scale-free networks, and have a great influence on the structural integrity, functional integrity and dynamics of the networks. In order to overcome the shortcomings in the existing work on the robustness of complex networks, only nodes or edges are considered, while the defects of high-order structure in the network are ignored. From the perspective of network motif, we propose an entropy of node degree distribution based on motif to measure the robustness of scale-free networks under random attacks. The effectiveness and superiority of our method are verified and analyzed in the BA scale-free networks.     

Analysis of identification methods of key nodes in transportation network

The identification of key nodes plays an important role in improving the robustness of the transportation network. For different types of transportation networks, the effect of the same identification method may be different. It is of practical significance to study the key nodes identification methods corresponding to various types of transportation networks. Based on the knowledge of complex networks, the metro networks and the bus networks are selected as the objects, and the key nodes are identified by the node degree identification method, the neighbor node degree identification method, the weighted k-shell degree neighborhood identification method (KSD), the degree k-shell identification method (DKS), and the degree k-shell neighborhood identification method (DKSN). Take the network efficiency and the largest connected subgraph as the effective indicators. The results show that the KSD identification method that comprehensively considers the elements has the best recognition effect and has certain practical significance.     

Cascading failure in multilayer networks with dynamic dependency groups

The cascading failure often occurs in real networks. It is significant to analyze the cascading failure in the complex network research. The dependency relation can change over time. Therefore, in this study, we investigate the cascading failure in multilayer networks with dynamic dependency groups. We construct a model considering the recovery mechanism.In our model, two effects between layers are defined. Under Effect 1, the dependent nodes in other layers will be disabled as long as one node does not belong to the largest connected component in one layer. Under Effect 2, the dependent nodes in other layers will recover when one node belongs to the largest connected component. The theoretical solution of the largest component is deduced and the simulation results verify our theoretical solution. In the simulation, we analyze the influence factors of the network robustness, including the fraction of dependent nodes and the group size, in our model. It shows that increasing the fraction of dependent nodes and the group size will enhance the network robustness under Effect 1. On the contrary, these will reduce the network robustness under Effect 2. Meanwhile, we find that the tightness of the network connection will affect the robustness of networks. Furthermore, setting the average degree of network as 8 is enough to keep the network robust.     

一种无线传感器网络健壮性可调的能量均衡拓扑控制算法

无线传感器网络中, 应用环境的干扰导致节点间距不能被准确度量. 所以利用以节点间距作为权重的闭包图(EG)模型构建的拓扑没有考虑环境的干扰, 忽略了这部分干扰带来的能耗, 缩短了网络生存时间. 针对无线传感器网络拓扑能量不均的特点和EG模型的缺陷, 首先引入节点度调节因子, 建立通信度量模型和节点实际生存时间模型; 其次量化网络节点度, 从而获取满足能量均衡和网络生命期最大化需求的节点度的取值规律; 然后利用该取值规律和函数极值充分条件解析推导出网络最大能量消耗值和最长生存时间, 并获得最优节点度; 最后基于以上模型提出一种健壮性可调的能量均衡拓扑控制算法. 理论证明该拓扑连通且为双向连通. 仿真结果说明网络能利用最优节点度达到较高的健壮性, 保证信息可靠传输, 且算法能有效平衡节点能耗, 提高网络健壮性, 延长网络生命周期.     

基于自规避随机游走的节点排序算法

评估复杂网络系统的节点重要性有助于提升其系统抗毁性和结构稳定性. 目前, 定量节点重要性的排序算法通常基于网络结构的中心性指标如度数、介数、紧密度、特征向量等. 然而, 这些算法需要以知晓网络结构的全局信息为前提, 很难在大规模网络中实际应用. 基于自规避随机游走的思想, 提出一种结合网络结构局域信息和标签扩散的节点排序算法. 该算法综合考虑了节点的直接邻居数量及与其他节点之间的拓扑关系, 能够表征其在复杂网络系统中的结构影响力和重要性. 基于三个典型的实际网络, 通过对极大连通系数、网络谱距离数、节点连边数和脆弱系数等评估指标的实验对比, 结果表明提出的算法显著优于现有的依据局域信息的节点排序算法.