Comparison of cascading failures in small-world and scale-free networks subject to vertex and edge attacks

Complex networks may undergo a global cascade of overload failures when a single highly loaded vertex or edge is intentionally attacked. Here we use the recent load model of cascading failures to investigate the performance of the small-world (SW) and scale-free (SF) networks subject to deliberate attacks on vertex and edge. Simulation results suggest that compared with the SW network, the SF network is more vulnerable to deliberate vertex attacks and more robust to deliberate edge attacks. In the SF network, deliberate vertex attacks can result in larger cascading failures than deliberate edge attacks; however, in the SW network the situation is opposite. Furthermore, with the increase of the rewiring probability the SW network becomes more and more robust to deliberate vertex and edge attacks.     

Continuous Weight Attack on Complex Network

We introduce a continuous weight attack strategy and numerically investigate the effect of continuous weight attack strategy on the Barabasi-Albert （BA） scale-free network and the Erdos-Rdnyi （ER） random network. We use a weight coefficient ω to define the attack intensity. The weight coefficient ω increases continuously from 1 to infinity, where 1 represents no attack and infinity represents complete destructive attack. Our results show that the continuous weight attack on two selected nodes with small ω （ω≈ 3） could achieve the same damage of complete elimination of a single selected node on both BA and ER networks. It is found that the continuous weight attack on a single selected edge with small ω （ω≈ 2） can reach the same effect of complete elimination of a single edge on BA network, but on ER network the damage of the continuous weight attack on a single edge is c/ose to but always smaller than that of complete elimination of edge even if ω is very large.     

Hierarchical Characterization of Complex Networks

While the majority of approaches to the characterization of complex networks has relied on measurements considering only the immediate neighborhood of each network node, valuable information about the network topological properties can be obtained by considering further neighborhoods. The current work considers the concept of virtual hierarchies established around each node and the respectively defined hierarchical node degree and clustering coefficient (introduced in cond-mat/0408076), complemented by new hierarchical measurements, in order to obtain a powerful set of topological features of complex networks. The interpretation of such measurements is discussed, including an analytical study of the hierarchical node degree for random networks, and the potential of the suggested measurements for the characterization of complex networks is illustrated with respect to simulations of random, scale-free and regular network models as well as real data (airports, proteins and word associations). The enhanced characterization of the connectivity provided by the set of hierarchical measurements also allows the use of agglomerative clustering methods in order to obtain taxonomies of relationships between nodes in a network, a possibility which is also illustrated in the current article.     

Error and attack tolerance of evolving networks with local preferential attachment

Networks generated by local-world evolving network model display a transition from exponential network to power-law network with respect to connectivity distribution. We investigate statistical properties of the evolving networks and the responses of these networks under random errors and intentional attacks. It has been found that local world size M has great effect on the network's heterogeneity, thus leading to transitional behaviors in network's robustness against errors and attacks. Numerical results show that networks constructed with local preferential attachment mechanism can maintain the robustness of scale-free networks under random errors and concurrently improve reliance against targeted attacks on highly connected nodes.     

Robustness analysis of static routing on networks

Robustness is one of the crucial properties that needs to be considered in the design of routing strategies on networks. We study the robustness of three typical routing strategies, which are the SP (shortest path), EP (efficient path), and OP (optimal path) strategies, by simulating several different kinds of attacks including random attacks, target attacks and cascading failures on scale-free networks. Results of the average path length, betweenness centrality, network capacity, etc., demonstrate that the EP strategy is more robust than the other two, and the OP strategy is more reliable than the SP strategy in general. However, on the power-grid network, the OP strategy is more resistant against cascading failures than the EP and SP strategies.     

Enhancement of scale-free network attack tolerance

Despite the large size of most communication and transportation systems,there are short paths between nodes in these networks which guarantee the efficient information,data and passenger delivery;furthermore these networks have a surprising tolerance under random errors thanks to their inherent scale-free topology.However,their scale-free topology also makes them fragile under intentional attacks,leaving us a challenge on how to improve the network robustness against intentional attacks without losing their strong tolerance under random errors and high message and passenger delivering capacity.Here we propose two methods (SL method and SH method) to enhance scale-free network’s tolerance under attack in different conditions.     

Complex networks: Dynamics and security

This paper presents a perspective in the study of complex networks by focusing on how dynamics may affect network security under attacks. In particular, we review two related problems: attack-induced cascading breakdown and range-based attacks on links. A cascade in a network means the failure of a substantial fraction of the entire network in a cascading manner, which can be induced by the failure of or attacks on only a few nodes. These have been reported for the internet and for the power grid (e.g., the August 10, 1996 failure of the western United States power grid). We study a mechanism for cascades in complex networks by constructing a model incorporating the flows of information and physical quantities in the network. Using this model we can also show that the cascading phenomenon can be understood as a phase transition in terms of the key parameter characterizing the node capacity. For a parameter value below the phase-transition point, cascading failures can cause the network to disintegrate almost entirely. We will show how to obtain a theoretical estimate for the phase-transition point. The second problem is motivated by the fact that most existing works on the security of complex networks consider attacks on nodes rather than on links. We address attacks on links. Our investigation leads to the finding that many scale-free networks are more sensitive to attacks on short-range than on long-range links. Considering that the small-world phenomenon in complex networks has been identified as being due to the presence of long-range links, i.e., links connecting nodes that would otherwise be separated by a long node-to-node distance, our result, besides its importance concerning network efficiency and security, has the striking implication that the small-world property of scale-free networks is mainly due to short-range links.     

一种能耗均衡的无线传感器网络加权无标度拓扑研究

针对无线传感器网络节点能耗不均衡问题,通过对节点生命期建模,得出节点生命期受节点剩余能量和通信距离的影响,进而将两端节点生命期作为构建拓扑时边权重的影响因子,通过边权重控制节点权重,最终得出了一种能耗均衡的无线传感器网络加权无标度拓扑模型,并理论证明了该模型的点权、边权和节点度均服从幂律分布.实验结果表明,该模型具有无标度拓扑的强容错性,并有效的均衡了网络中的节点能耗,延长了网络的生命期.     

Adaptive bridge control strategy for opinion evolution on social networks

In this paper, we present an efficient opinion control strategy for complex networks, in particular, for social networks. The proposed adaptive bridge control (ABC) strategy calls for controlling a special kind of nodes named bridge and requires no knowledge of the node degrees or any other global or local knowledge, which are necessary for some other immunization strategies including targeted immunization and acquaintance immunization. We study the efficiency of the proposed ABC strategy on random networks, small-world networks, scale-free networks, and the random networks adjusted by the edge exchanging method. Our results show that the proposed ABC strategy is efficient for all of these four kinds of networks. Through an adjusting clustering coefficient by the edge exchanging method, it is found out that the efficiency of our ABC strategy is closely related with the clustering coefficient. The main contributions of this paper can be listed as follows: (1) A new high-order social network is proposed to describe opinion dynamic. (2) An algorithm, which does not require the knowledge of the nodes' degree and other global∕local network structure information, is proposed to control the "bridges" more accurately and further control the opinion dynamics of the social networks. The efficiency of our ABC strategy is illustrated by numerical examples. (3) The numerical results indicate that our ABC strategy is more efficient for networks with higher clustering coefficient.     

Mixing search on complex networks

In this article, we derive the first passage time (FPT) distribution and the mean first passage time (MFPT) of random walks from multiple sources on networks. On the basis of analysis and simulation, we find that the MFPT drops substantially when particle number increases at the first stage, and converges to the shortest distance between the sources and the destination when particle number tends to infinite. Given the fact that a Brownian particle from a high-degree node often needs a large number of steps to reach an expected low-degree node, which is the bottleneck for a single random walk, we propose a mixing search model to improve the efficiency of search processes by using random walks from multiple sources to continue the searches from high-degree nodes to destinations. We compare our model with the mixing navigation model proposed by Zhou on complex networks and find that our model converges much faster with lower hardware cost than Zhou’s model. Moreover, simulations on scale-free networks show that the search efficiency of our model is much higher than that of a single random walk, and comparable to that of multiple random walks which have much higher hardware cost than our model. Finally, we discuss the traffic cost of our model, and propose an absorption strategy for our model to recover the additional walkers in networks. Simulations indicate that this strategy reduces the traffic cost of our model effectively.     

Two-peak and three-peak optimal complex networks

A central issue in complex networks is tolerance of random failures and intentional attacks. Current literature emphasizes the dichotomy between networks with a power-law node connectivity distribution, which are robust to random failures but fragile to targeted attacks, versus networks with an exponentially decaying connectivity distribution, which are less tolerant to failures but more resilient to attacks. We prove analytically that the optimal network configuration under a classic measure of robustness is altogether different from both of the above: in all cases, failure and/or attack, there are no more than three distinct node connectivities in the optimal network.     

基于综合故障的无线传感器网络无标度容错拓扑模型研究

针对无线传感器网络实际应用中遇到的环境损毁和能量耗尽的问题,本文首先对网络综合故障进行建模,获取满足综合故障容忍能力和网络生命期双重需求的网络节点度和节点度上限值的取值规律,并结合由无标度特征导出的两者关系,从而求得最优节点度上限值,最终引入关于节点度上限值的适应度函数,提出了容忍环境损毁和能量耗尽综合故障的无标度容错拓扑演化模型.仿真实验结果表明,该模型演化生成的无标度拓扑对环境损毁和能量耗尽具有较好的容错性,并能够有效地延长网络生命期.     

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.     

A self-organizing shortest path finding strategy on complex networks

The shortcomings of traditional methods to find the shortest path are revealed, and a strategy of finding the self-organizing shortest path based on thermal flux diffusion on complex networks is presented. In our method, the shortest paths between the source node and the other nodes are found to be self-organized by comparing node temperatures. The computation complexity of the method scales linearly with the number of edges on underlying networks. The effects of the method on several networks, including a regular network proposed by Ravasz and Barabási which is called the RB network, a real network, a random network proposed by Ravasz and Barabási which is called the ER network and a scale-free network, are also demonstrated. Analytic and simulation results show that the method has a higher accuracy and lower computational complexity than the conventional methods.     

Robustness analysis of network controllability

Structural controllability, which is an interesting property of complex networks, attracts many researchers from various fields. The maximum matching algorithm was recently applied to explore the minimum number of driver nodes, where control signals are injected, for controlling the whole network. Here we study the controllability of directed Erdös–Rényi and scale-free networks under attacks and cascading failures. Results show that degree-based attacks are more efficient than random attacks on network structural controllability. Cascade failures also do great harm to network controllability even if they are triggered by a local node failure.     

Systemic risk on different interbank network topologies

In this paper we develop an interbank market with heterogeneous financial institutions that enter into lending agreements on different network structures. Credit relationships (links) evolve endogenously via a fitness mechanism based on agents’ performance. By changing the agent’s trust on its neighbor’s performance, interbank linkages self-organize themselves into very different network architectures, ranging from random to scale-free topologies. We study which network architecture can make the financial system more resilient to random attacks and how systemic risk spreads over the network. To perturb the system, we generate a random attack via a liquidity shock. The hit bank is not automatically eliminated, but its failure is endogenously driven by its incapacity to raise liquidity in the interbank network. Our analysis shows that a random financial network can be more resilient than a scale free one in case of agents’ heterogeneity.     

Biased trapping issue on weighted hierarchical networks

In this paper, we present trapping issues of weight-dependent walks on weighted hierarchical networks which are based on the classic scale-free hierarchical networks. Assuming that edge’s weight is used as local information by a random walker, we introduce a biased walk. The biased walk is that a walker, at each step, chooses one of its neighbours with a probability proportional to the weight of the edge. We focus on a particular case with the immobile trap positioned at the hub node which has the largest degree in the weighted hierarchical networks. Using a method based on generating functions, we determine explicitly the mean first-passage time (MFPT) for the trapping issue. Let parameter a (0 < a < 1) be the weight factor. We show that the efficiency of the trapping process depends on the parameter a; the smaller the value of a, the more efficient is the trapping process.     

复杂交通运输网络上的拥挤与效率问题研究

本文研究复杂交通运输网络上的拥挤与效率问题. 在无标度网络、随机网络以及小世界网络等不同拓扑结构中, 探讨了不同的能力分配方式和不同的OD (Origin-Destination) 交通需求分布对网络拥挤度和效率的影响. 随着平均交通需求的增加, 分析无标度网络、随机网络以及小世界网络从自由流状态到交通拥堵状态的变化规律. 为便于比较, 本文侧重研究网络拥挤度的倒数, 并将其定义为通畅度. 研究发现网络中的通畅度与效率之间存在线性相关关系, 并且不同网络中的线性比例系数 (或斜率)是不同的, 从而体现了不同网络具有不同的运输性能. 关键词： 复杂网络 拥挤 效率     

Concentric characterization and classification of complex network nodes: Application to an institutional collaboration network

Differently from theoretical scale-free networks, most real networks present multi-scale behavior, with nodes structured in different types of functional groups and communities. While the majority of approaches for classification of nodes in a complex network has relied on local measurements of the topology/connectivity around each node, valuable information about node functionality can be obtained by concentric (or hierarchical) measurements. This paper extends previous methodologies based on concentric measurements, by studying the possibility of using agglomerative clustering methods, in order to obtain a set of functional groups of nodes, considering particular institutional collaboration network nodes, including various known communities (departments of the University of São Paulo). Among the interesting obtained findings, we emphasize the scale-free nature of the network obtained, as well as identification of different patterns of authorship emerging from different areas (e.g. human and exact sciences). Another interesting result concerns the relatively uniform distribution of hubs along concentric levels, contrariwise to the non-uniform pattern found in theoretical scale-free networks such as the BA model.     

Impact of core-periphery structure on cascading failures in interdependent scale-free networks

Core-periphery structure is a typical meso-scale structure in networks. Previous studies on core-periphery structure mainly focus on the improvement of detection methods, while the research on the impact of core-periphery structure on cascading failures in interdependent networks is still missing. Therefore, we investigate the cascading failures of interdependent scale-free networks with different core-periphery structures and coupling preferences in the paper. First, we introduce an evaluation index to calculate the goodness of core-periphery structure. Second, we propose a new scale-free network evolution model, which can generate tunable core-periphery structures, and its degree distribution is analyzed mathematically. Finally, based on a degree-load-based cascading failure model, we mainly investigate the impact of goodness of core-periphery structure on cascading failures in both symmetrical and asymmetrical interdependent networks. Through numerical simulations, we find that with the same average degree, the networks with weak core-periphery structure will be more robust, while the initial load on node will influence the improvement of robustness. In addition, we also find that the inter-similarity coupling performs better than random coupling. These findings may be helpful for building resilient interdependent networks.