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

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

Error and attack tolerance of synchronization in Hindmarsh–Rose neural networks with community structure

Synchronization is one of the most important features observed in large-scale complex networks of interacting dynamical systems. As is well known, there is a close relation between the network topology and the network synchronizability. Using the coupled Hindmarsh–Rose neurons with community structure as a model network, in this paper we explore how failures of the nodes due to random errors or intentional attacks affect the synchronizability of community networks. The intentional attacks are realized by removing a fraction of the nodes with high values in some centrality measure such as the centralities of degree, eigenvector, betweenness and closeness. According to the master stability function method, we employ the algebraic connectivity of the considered community network as an indicator to examine the network synchronizability. Numerical evidences show that the node failure strategy based on the betweenness centrality has the most influence on the synchronizability of community networks. With this node failure strategy for a given network with a fixed number of communities, we find that the larger the degree of communities, the worse the network synchronizability; however, for a given network with a fixed degree of communities, we observe that the more the number of communities, the better the network synchronizability.     

Sensitivity of the resilience of congested random networks to rolloff and offset in truncated power-law degree distributions

Random networks were generated with the random configuration model with prescribed truncated power-law degree distributions, parameterized by an exponent, an offset, and an exponential rolloff. As a model of an attack, each network had exactly one of its highest degree nodes removed, with the result that in some cases, one or more remaining nodes became congested with the reassignment of the load. The congested nodes were then removed, and the “cascade failure” process continued until all nodes were uncongested. The ratio of the number of nodes of the largest remaining cluster to the number of nodes in the original network was taken to be a measure of the network's resiliency to highest-degree node removal. We found that the resiliency is sensitive to both rolloff and offset (but not to cutoff) in the degree distribution, and that rolloff tends to decrease resiliency while offset tends to increase it.     

微博双向“关注”网络节点中心性及传播 影响力的分析

根据新浪微博的实际数据, 建立了两个基于双向“关注”的用户关系网络, 通过分析网络拓扑统计特征, 发现二者均具有小世界、无标度特征. 通过对节点度、紧密度、介数和k-core 四个网络中心性指标进行实证分析, 发现节点度服从分段幂率分布; 介数相比其他中心性指标差异性最为显著; 两个网络均具有明显的层次性, 但不是所有度值大的节点核数也大; 全局范围内各中心性指标之间存在着较强的相关性, 但在度值较大的节点群这种相关性明显减弱. 此外, 借助基于传染病动力学的SIR信息传播模型来分析四种指标在刻画节点传播能力方面的差异性, 仿真结果表明, 选择具有不同中心性指标的初始传播节点, 对信息传播速度和范围均具有不同影响; 紧密度和k-core较其他指标可以更加准确地描述节点在信息传播中所处的网络核心位置, 这有助于识别信息传播拓扑网络中的关键节点.     

The importance of centralities in dark network value chains

This paper introduces three novel centrality measures based on the nodes’ role in the operation of a joint task, i.e., their position in a criminal network value chain. For this, we consider networks where nodes have attributes describing their “capabilities” or “colors”, i.e., the possible roles they may play in a value chain. A value chain here is understood as a series of tasks to be performed in a specific order, each requiring a specific capability. The first centrality notion measures how many value chain instances a given node participates in. The other two assess the costs of replacing a node in the value chain in case the given node is no longer available to perform the task. The first of them considers the direct distance (shortest path length) between the node in question and its nearest replacement, while the second evaluates the actual replacement process, assuming that preceding and following nodes in the network should each be able to find and contact the replacement. In this report, we demonstrate the properties of the new centrality measures using a few toy examples and compare them to classic centralities, such as betweenness, closeness and degree centrality. We also apply the new measures to randomly colored empirical networks. We find that the newly introduced centralities differ sufficiently from the classic measures, pointing towards different aspects of the network. Our results also pinpoint the difference between having a replacement node in the network and being able to find one. This is the reason why “introduction distance” often has a noticeable correlation with betweenness. Our studies show that projecting value chains over networks may significantly alter the nodes’ perceived importance. These insights might have important implications for the way law enforcement or intelligence agencies look at the effectiveness of dark network disruption strategies over time.     

Stability and topology of scale-free networks under attack and defense strategies

We study tolerance and topology of random scale-free networks under attack and defense strategies that depend on the degree k of the nodes. This situation occurs, for example, when the robustness of a node depends on its degree or in an intentional attack with insufficient knowledge of the network. We determine, for all strategies, the critical fraction p(c) of nodes that must be removed for disintegrating the network. We find that, for an intentional attack, little knowledge of the well-connected sites is sufficient to strongly reduce p(c). At criticality, the topology of the network depends on the removal strategy, implying that different strategies may lead to different kinds of percolation transitions.     

网络集聚性对节点中心性指标的准确性影响

节点中心性指标是从特定角度对网络某一方面的结构特点进行刻画的度量指标, 因此网络拓扑结构的改变会对节点中心性指标的准确性产生重要影响. 本文利用Holme-Kim模型构建可变集聚系数的无标度网络, 然后采用Susceptible-Infective-Removal模型进行传播影响力的仿真实验, 接着分析了节点中心性指标在不同集聚系数的无标度网络中的准确性. 结果表明, 度中心性和介数中心性的准确性在低集聚系数的网络中表现更好, 特征向量中心性则在高集聚类网络中更准确, 而紧密度中心性的准确性受网络集聚系数的变化影响较小. 因此当网络的集聚系数较低时, 可选择度或者介数作为中心性指标进行网络节点影响力评价; 反之则选择紧密度指标或特征向量指标较好, 尤其当网络的集聚系数接近0.6时特征向量的准确性可以高达到0.85, 是度量小规模网络的较优选择. 另一方面, 传播过程的感染率越高, 度指标和介数指标越可靠, 紧密度和特征向量则相反. 最后Autonomous System实证网络的断边重连实验, 进一步验证了网络集聚性的改变会对节点中心性指标的准确性产生重要影响.     

Dynamical robustness of networks based on betweenness against multi-node attack

We explore the robustness of a network against failures of vertices or edges where a fraction f of vertices is removed and an overload model based on betweenness is constructed. It is assumed that the load and capacity of vertex i are correlated with its betweenness centrality B_i as B_i~θ and(1 + α)Bθi(θ is the strength parameter, α is the tolerance parameter).We model the cascading failures following a local load preferential sharing rule. It is found that there exists a minimal αc when θ is between 0 and 1, and its theoretical analysis is given. The minimal αc characterizes the strongest robustness of a network against cascading failures triggered by removing a random fraction f of vertices. It is realized that the minimalαc increases with the increase of the removal fraction f or the decrease of average degree. In addition, we compare the robustness of networks whose overload models are characterized by degree and betweenness, and find that the networks based on betweenness have stronger robustness against the random removal of a fraction f of vertices.     

确定度分布条件下可变同配系数的算法构造与影响分析

复杂网络是现实中大量节点和边的抽象拓扑, 如何揭示网络内部拓扑对网络连通性、脆弱性等特征的影响是当前研究的热点. 本文在确定度分布的条件下, 根据Newman提出的同配系数的定义分析其影响因素. 首先在可变同配系数下分别提出了基于度分布的确定算法和基于概率分布的不确定算法, 并分别在三种不同类型的网络(Erdös-Rényi网络, Barabási-Albert网络, Email真实网络)中验证. 实验结果表明: 当网络规模达到一定程度时, 确定算法优于贪婪算法. 以此为基础, 分析了同配系数改变时聚类系数的变化, 发现两者之间存在关联性, 并从网络的微观结构变化中揭示了聚类系数变化的原因.     

Robustness Evaluation of the Open Source Product Community Network Considering Different Influential Nodes

With the rapid development of Internet technology, the innovative value and importance of the open source product community (OSPC) is becoming increasingly significant. Ensuring high robustness is essential to the stable development of OSPC with open characteristics. In robustness analysis, degree and betweenness are traditionally used to evaluate the importance of nodes. However, these two indexes are disabled to comprehensively evaluate the influential nodes in the community network. Furthermore, influential users have many followers. The effect of irrational following behavior on network robustness is also worth investigating. To solve these problems, we built a typical OSPC network using a complex network modeling method, analyzed its structural characteristics and proposed an improved method to identify influential nodes by integrating the network topology characteristics indexes. We then proposed a model containing a variety of relevant node loss strategies to simulate the changes in robustness of the OSPC network. The results showed that the proposed method can better distinguish the influential nodes in the network. Furthermore, the network’s robustness will be greatly damaged under the node loss strategies considering the influential node loss (i.e., structural hole node loss and opinion leader node loss), and the following effect can greatly change the network robustness. The results verified the feasibility and effectiveness of the proposed robustness analysis model and indexes.     

Clarifying How Degree Entropies and Degree-Degree Correlations Relate to Network Robustness

It is often claimed that the entropy of a network’s degree distribution is a proxy for its robustness. Here, we clarify the link between degree distribution entropy and giant component robustness to node removal by showing that the former merely sets a lower bound to the latter for randomly configured networks when no other network characteristics are specified. Furthermore, we show that, for networks of fixed expected degree that follow degree distributions of the same form, the degree distribution entropy is not indicative of robustness. By contrast, we show that the remaining degree entropy and robustness have a positive monotonic relationship and give an analytic expression for the remaining degree entropy of the log-normal distribution. We also show that degree-degree correlations are not by themselves indicative of a network’s robustness for real networks. We propose an adjustment to how mutual information is measured which better encapsulates structural properties related to robustness.     

一种复杂网络路由策略的普适优化算法

现有的复杂网络路由策略很多,改进算法也不断涌现,但是目前还没有一个统一的标准来衡量算法是否达到网络最佳传输效果.针对这一问题,本文提出一种适用于现有路由策略的普适优化算法.首先通过理论分析指出制约网络传输能力的关键因素是最大介数中心度,因而"最大介数中心度是否已经最低"成为评判路由策略是否最优的标准.在此基础上,采用"惩罚选择法"避开网络中介数中心度值比较大的节点,使网络介数中心度值分布更均匀,均衡网络中各个节点的传输负载.仿真结果显示,该优化算法针对现有路由策略均能降低最大介数中心度值,大幅度提高网络的传输能力.     

An Internet-Oriented Multilayer Network Model Characterization and Robustness Analysis Method

The Internet creates multidimensional and complex relationships in terms of the composition, application and mapping of social users. Most of the previous related research has focused on the single-layer topology of physical device networks but ignored the study of service access relationships and the social structure of users on the Internet. Here, we propose a composite framework to understand how the interaction between the physical devices network, business application network, and user role network affects the robustness of the entire Internet. In this paper, a multilayer network consisting of a physical device layer, business application layer and user role layer is constructed by collecting experimental network data. We characterize the disturbance process of the entire multilayer network when a physical entity device fails by designing nodal disturbance to investigate the interactions that exist between the different network layers. Meanwhile, we analyze the characteristics of the Internet-oriented multilayer network structure and propose a heuristic multilayer network topology generation algorithm based on the initial routing topology and networking pattern, which simulates the evolution process of multilayer network topology. To further analyze the robustness of this multilayer network model, we combined a total of six target node ranking indicators including random strategy, degree centrality, betweenness centrality, closeness centrality, clustering coefficient and network constraint coefficient, performed node deletion simulations in the experimental network, and analyzed the impact of component types and interactions on the robustness of the overall multilayer network based on the maximum component change in the network. These results provide new insights into the operational processes of the Internet from a multi-domain data fusion perspective, reflecting that the coupling relationships that exist between the different interaction layers are closely linked to the robustness of multilayer networks.     

Two Novel Methods to Enhance Network Synchronizability

In this paper, we propose two methods to enhance the synchronizability of a class of complex networks which do not hold the positive correlation between betweenness centrality （BC） and degree of a node, and observe other topology characteristics of the network affected by the methods. Numerical simulations show that both methods can effectively enhance the synchronizability of this kind of networks. Furthermore, we show that the maximal BC of all edges is an important factor to affect the network synchronizability, although it is not the unique factor.     

Communicability betweenness in complex networks

Betweenness measures provide quantitative tools to pick out fine details from the massive amount of interaction data that is available from large complex networks. They allow us to study the extent to which a node takes part when information is passed around the network. Nodes with high betweenness may be regarded as key players that have a highly active role. At one extreme, betweenness has been defined by considering information passing only through the shortest paths between pairs of nodes. At the other extreme, an alternative type of betweenness has been defined by considering all possible walks of any length. In this work, we propose a betweenness measure that lies between these two opposing viewpoints. We allow information to pass through all possible routes, but introduce a scaling so that longer walks carry less importance. This new definition shares a similar philosophy to that of communicability for pairs of nodes in a network, which was introduced by Estrada and Hatano [E. Estrada, N. Hatano, Phys. Rev. E 77 (2008) 036111]. Having defined this new communicability betweenness measure, we show that it can be characterized neatly in terms of the exponential of the adjacency matrix. We also show that this measure is closely related to a Fréchet derivative of the matrix exponential. This allows us to conclude that it also describes network sensitivity when the edges of a given node are subject to infinitesimally small perturbations. Using illustrative synthetic and real life networks, we show that the new betweenness measure behaves differently to existing versions, and in particular we show that it recovers meaningful biological information from a protein-protein interaction network.     

一种基于文本互信息的金融复杂网络模型

复杂网络能够解决许多金融问题,能够发现金融市场的拓扑结构特征,反映不同金融主体之间的相互依赖关系.相关性度量在金融复杂网络构建中至关重要.通过将多元金融时间序列符号化,借鉴文本特征提取以及信息论的方法,定义了一种基于文本互信息的相关系数.为检验方法的有效性,分别构建了基于不同相关系数(Pearson和文本互信息)和不同网络缩减方法(阈值和最小生成树)的4个金融复杂网络模型.在阈值网络中提出了使用分位数来确定阈值的方法,将相关系数6等分,取第4部分的中点作为阈值,此时基于Pearson和文本互信息的阈值模型将会有相近的边数,有利于这两种模型的对比.数据使用了沪深两地证券市场地区指数收盘价,时间从2006年1月4日至2016年12月30日,共计2673个交易日.从网络节点相关性看,基于文本互信息的方法能够体现出大约20%的非线性相关关系;在网络整体拓扑指标上,本文计算了4种指标,结果显示能够使所保留的节点联系更为紧密,有效提高保留节点的重要性以及挖掘出更好的社区结构;最后,计算了阈值网络的动态指标,将数据按年分别构建网络,缩减方法只用了阈值方法,结果显示本文提出的方法在小世界动态和网络度中心性等指标上能够成功捕捉到样本区间内存在的两次异常波动.此外,本文构建的地区金融网络具有服从幂律分布、动态稳定性、一些经济欠发达地区在金融地区网络中占据重要地位等特性.     

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

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

Complexity in human transportation networks: a comparative analysis of worldwide air transportation and global cargo-ship movements

We present a comparative network-theoretic analysis of the two largest global transportation networks: the worldwide air-transportation network (WAN) and the global cargo-ship network (GCSN). We show that both networks exhibit surprising statistical similarities despite significant differences in topology and connectivity. Both networks exhibit a discontinuity in node and link betweenness distributions which implies that these networks naturally segregate into two different classes of nodes and links. We introduce a technique based on effective distances, shortest paths and shortest path trees for strongly weighted symmetric networks and show that in a shortest path tree representation the most significant features of both networks can be readily seen. We show that effective shortest path distance, unlike conventional geographic distance measures, strongly correlates with node centrality measures. Using the new technique we show that network resilience can be investigated more precisely than with contemporary techniques that are based on percolation theory. We extract a functional relationship between node characteristics and resilience to network disruption. Finally we discuss the results, their implications and conclude that dynamic processes that evolve on both networks are expected to share universal dynamic characteristics.     

Identifying Important Nodes in Complex Networks Based on Node Propagation Entropy

In recent years, the identification of the essential nodes in complex networks has attracted significant attention because of their theoretical and practical significance in many applications, such as preventing and controlling epidemic diseases and discovering essential proteins. Several importance measures have been proposed from diverse perspectives to identify crucial nodes more accurately. In this paper, we propose a novel importance metric called node propagation entropy, which uses a combination of the clustering coefficients of nodes and the influence of the first- and second-order neighbor numbers on node importance to identify essential nodes from an entropy perspective while considering the local and global information of the network. Furthermore, the susceptible–infected–removed and susceptible–infected–removed–susceptible epidemic models along with the Kendall coefficient are used to reveal the relevant correlations among the various importance measures. The results of experiments conducted on several real networks from different domains show that the proposed metric is more accurate and stable in identifying significant nodes than many existing techniques, including degree centrality, betweenness centrality, closeness centrality, eigenvector centrality, and H-index.     

The gateway coefficient: a novel metric for identifying critical connections in modular networks

The modular structure of a complex network is an important and well-studied topological property. Within this modular framework, particular nodes which play key roles have been previously identified based on the node’s degree, and on the node’s participation coefficient, a measure of the diversity of a node’s intermodular connections. In this contribution, we develop a generalization of the participation coefficient, called the gateway coefficient, which measures not only the diversity of the intermodular connections, but also how critical these connections are to intermodular connectivity; in brief, nodes which form rare or unique “gateways” between sparsely connected modules rank highly in this measure. We illustrate the use of the gateway coefficient with simulated networks with defined modular structure, as well as networks obtained from air transportation data and functional neuroimaging.