Robustness of Complex Networks under Attack and Repair

To study the robustness of complex networks under attack and repair, we introduce a repair model of complex networks. Based on the model, we introduce two new quantities, i.e. attack fraction fa and the maximum degree of the nodes that have never been attacked ~Ka, to study analytically the critical attack fraction and the relative size of the giant component of complex networks under attack and repair, using the method of generating function. We show analytically and numerically that the repair strategy significantly enhances the robustness of the scale-free network and the effect of robustness improvement is better for the scale-free networks with a smaller degree exponent. We discuss the application of our theory in relation to the
understanding of robustness of complex networks with reparability.     

Effect of Eliminating Edges on Robustness of Scale-Free Networks under Intentional Attack

We study the robustness of complex networks under edge elimination. We propose three different edge elimination strategies and investigate their effects on the robustness of scale-free networks under intentional attack. We show that deleting a proper fraction of edges connecting hub nodes and hub nodes can enhance the robustness of scale-free networks under intentional attack.     

Natural Connectivity of Complex Networks

The concept of natural connectivity is reported as a robustness measure of complex networks. The natural connectivity has a clear physical meaning and a simple mathematical formulation. It is shown that the natural connectivity can be derived mathematically from the graph spectrum as an average eigenvalue and that it changes strictly monotonically with the addition or deletion of edges. By comparing the natural connectivity with other typical robustness measures within a scenario of edge elimination, it is demonstrated that the naturM connectivity has an acute discrimination which agrees with our intuition.     

Cascading Failures of Complex Networks Based on Two-Step Degree

We propose a new concept, two-step degree. Defining it as the capacity of a node of complex networks, we establish a novel capacity-load model of cascading failures of complex networks where the capacity of nodes decreases during the process of cascading failures. For scale-free networks, we find that the average two-step degree increases with the increase of the heterogeneity of the degree distribution, showing that the average two- step degree can be used for measuring the heterogeneity of the degree distribution of complex networks. In addition, under the condition that the average degree of a node is given, we can design a scale-free network with the optimal robustness to random failures by maximizing the average two-step degree.     

Effect Attack on Scale-Free Networks due to Cascading Failures

Adopting the initial load of a node j to be Lj = [kj ∑mεГkm）]^α with kj and Fj being the degree of the node j and the set of its neighbouring nodes respectively, we propose a cascading model based on a local preferential redistribution rule of the load after removing a node. Assuming that a failed node leads only to a redistribution of the load passing through it to its neighbouring nodes, we explore the response of scale-free networks subject to two different attack strategies on nodes and find some interesting and counterintuitive results in our cascading model. On the one hand, unexpectedly, tile attack on the nodes with the lowest degree is more harmful than the attack on the highest degree nodes when α〈1/2. On the other hand, when α = 1/2, the effects of two attacks for the robustness against cascading failures are almost identical. In addition, the numerical simulations are also verified by the theoretical analysis. These results may be very helpful for real-life networks to protect the key nodes selected effectively and to avoid cascading-failure-induced disasters.     

Opinion Dynamics on Complex Networks with Communities

The Ising or Potts models of ferromagnetism have been widely used to describe locally interacting social or economic systems. We consider a related model, introduced by Sznajd to describe the evolution of consensus in the scale-free networks with the tunable strength （noted by Q） of community structure. In the Sznajd model, the opinion or state of any spins can only be changed by the influence of neighbouring pairs of similar connection spins. Such pairs can polarize their neighbours. Using asynchronous updating, it is found that the smaller the community strength Q, the larger the slope of the exponential relaxation time distribution. Then the effect of the initial upspin concentration p as a function of the final all up probability E is investigated by taking different initialization strategies, the random node-chosen initialization strategy has no difference under different community strengths, while the strategies of community node-chosen initialization and hub node-chosen initialization are different in fina/probability under different Q, and the latter one is more effective in reaching final state.     

High-performance distribution of limited resources via a dynamical reallocation scheme

Using the context of routing efficiency in a complex scale-free network, we study the problem of how a limited amount of resources should be distributed to the nodes in a network so as to achieve a better performance, without imposing a certain pre-determined distribution. A dynamical reallocation scheme, based on the willingness of sharing resources with a busy neighboring node, is proposed as a tool for allowing an initially uniform distribution of resource to evolve to a high-performance distribution. The resulting distribution gives a critical packet generation rate R_c that is significantly enhanced when compared with evenly distributing the same amount of resources on the nodes. There emerges a relation between the resource allocated to a node and the degree of the node in the form of . The exponent γ is found to vary with the packet generation rate R. For R<R_c, γ takes on a high value and shows a weak dependence on R; for R>R_c, γ drops with R; and for R?R_c, γ saturates. For good performance, the values of γ indicate a behavior different from that linear in k, as often assumed in previous studies. The resource distribution is also analyzed in terms of the betweenness of the nodes.     

Dynamics of Symmetric Conserved Mass Aggregation Model on Complex Networks

We investigate the dynamical behaviour of the aggregation process in the symmetric conserved mass aggregation model under three different topological structures. The dispersion a（t, L） = （∑i（mi - ρo ） ^2 / L ）1/2 is defined to describe the dynamical behaviour where Po is the density of particle and mi is the particle number on a site. It is found numerically that for a regular lattice and a scale-free network, σ（t, L） follows a power-law scaling σ（ t, L） ~ t^δ1 and σ（ t, L） ~ t^δ4 from a random initial condition to the stationary states, respectively. However, for a small-world network, there are two power-law scaling regimes, σ（t, L） ~ t^δ2 when t 〈 T and 〈（t, L） ~ t^δ3 when t 〉 T. Moreover, it is found numerically that 62 is near to 61 for small rewiring probability q, and 63 hardly changes with varying q and it is almost the same as 64. We speculate that the aggregation of the connection degree accelerates the mass aggregation in the initial relaxation stage and the existence of the long-distance interactions in the complex networks results in the acceleration of the mass aggregation when t 〉 T for the small-world networks. We also show that the relaxation time r follows a power-law scaling τ ~ L^z and σ（t, L） in the stationary state follows a power-law Gs（L） - L^α for three different structures.     

Connectivity degrees in the threshold preferential attachment model

In this paper we present a study of the connectivity degrees of the threshold preferential attachment model, a generalization of the Barabási-Albert model to heterogeneous complex networks. The threshold model incorporates the states of the nodes in its preferential linking rule and assumes that the affinity between network nodes follows an inverse relationship with the distance between their states. We numerically analyze the connectivity degrees of the model, studying the influence of the main parameters on the distribution of connectivity degrees and its statistics, the average degree and highest degree of the network. We show that such statistics exhibit markedly different behaviors in the dependence on the model parameters, particularly as regards the interaction threshold. Nevertheless, we show that the two statistics converge in the limit of null threshold and often exhibit scaling that can be described by power laws of the model parameters.     

Local Events and Dynamics on Weighted Complex Networks

We examine the weighted networks grown and evolved by local events, such as the addition of new vertices and links and we show that depending on frequency of the events, a generalized power-law distribution of strength can emerge. Continuum theory is used to predict the scaling function as well as the exponents, which is in good agreement with the numerical simulation results. Depending on event frequency, power-law distributions of degree and weight can also be expected. Probability saturation phenomena for small strength and degree in many real world networks can be reproduced. Particularly, the non-trivial clustering coefficient, assortativity coefficient and degree-strength correlation in our model are all consistent with empirical evidences.     

Epidemic Diffusion on Complex Networks

Both diffusion and epidemic are well studied in the stochastic systems and complex networks, respectively. Here we combine these two fields and study epidemic diffusion in complex networks. Instead of studying the threshold of infection, which was focused on in previous works, we focus on the diffusion behayiour. We find that the epidemic diffusion in a complex network is an anomalous superdiffusion with varying diffusion exponent and that γ is influenced seriously by the network structure, such as the clustering coefficient and the degree distribution. Numerical simulations have confirmed the theoretical predictions.     

Walks on Weighted Networks

We investigate the dynamics of random walks on weighted networks. Assuming that the edge weight and the node strength are used as local information by a random walker. Two kinds of walks, weight-dependent walk and strength-dependent walk, are studied. Exact expressions for stationary distribution and average return time are derived and confirmed by computer simulations. The distribution of average return time and the mean-square displacement are calculated for two walks on the Barrat-Barthelemy-Vespignani （BBV） networks. It is found that a weight-dependent walker can arrive at a new territory more easily than a strength-dependent one.     

Attack vulnerability of scale-free networks due to cascading failures

In this paper, adopting the initial load of a node i to be with k_i being the degree of the node i, we propose a cascading model based on a load local redistribution rule and examine cascading failures on the typical network, i.e., the BA network with the scale-free property. We find that the BA scale-free network reaches the strongest robustness level in the case of α=1 and the robustness of the network has a positive correlation with the average degree 〈k〉, where the robustness is quantified by a transition from normal state to collapse. In addition, we further discuss the effects of two different attacks for the robustness against cascading failures on our cascading model and find an interesting result, i.e., the effects of two different attacks, strongly depending to the value α. These results may be very helpful for real-life networks to avoid cascading-failure-induced disasters.     

Robustness of heterogeneous complex networks

In this paper we study the robustness of heterogeneous preferential attachment networks. The robustness of a network measures its structural tolerance to the random removal of nodes and links. We numerically analyze the influence of the affinity parameters on a set of ensemble-averaged robustness metrics. We show that the presence of heterogeneity does not fundamentally alter the smooth nature of the fragmentation process of the models. We also show that a moderate level of locality translates into slight improvements in the robustness metrics, which prompts us to conjecture an evolutionary argument for the existence of real networks with power-law scaling in their connectivity and clustering distributions.     

Networks that optimize a trade-off between efficiency and dynamical resilience

In this Letter we study networks that have been optimized to realize a trade-off between communication efficiency and dynamical resilience. While the first is related to the average shortest pathlength, we argue that the second can be measured by the largest eigenvalue of the adjacency matrix of the network. Best efficiency is realized in star-like configurations, while enhanced resilience is related to the avoidance of short loops and degree homogeneity. Thus crucially, very efficient networks are not resilient while very resilient networks lack in efficiency. Networks that realize a trade-off between both limiting cases exhibit core-periphery structures, where the average degree of core nodes decreases but core size increases as the weight is gradually shifted from a strong requirement for efficiency and limited resilience towards a smaller requirement for efficiency and a strong demand for resilience. We argue that both, efficiency and resilience are important requirements for network design and highlight how networks can be constructed that allow for both.     

A model for cascading failures in scale-free networks with a breakdown probability

Considering that not all overload nodes will be removed from networks due to some effective measures to protect them, we propose a new cascading model with a breakdown probability. Adopting the initial load of a node j to be L_j=[k_j(∑_m∈Γjk_m)]^α with k_j and Γ_j being the degree of the node j and the set of its neighboring nodes, respectively, where α is a tunable parameter, we investigate the relationship between some parameters and universal robustness characteristics against cascading failures on scale-free networks. According to a new measure originated from a phase transition from the normal state to collapse, the numerical simulations show that Barabási-Albert (BA) networks reach the strongest robustness level against cascading failures when the tunable parameter α=0.5, while not relating to the breakdown probability. We furthermore explore the effect of the average degree 〈k〉 for network robustness, thus obtaining a positive correlation between 〈k〉 and network robustness. We then analyze the effect of the breakdown probability on the network robustness and confirm by theoretical predictions this universal robustness characteristic observed in simulations. Our work may have practical implications for controlling various cascading-failure-induced disasters in the real world.     

Role of Clustering Coefficient on Cooperation Dynamics in Homogeneous Networks

Based on previous works, we give further investigations on the Prisoners＇ Dilemma Game （PDG） on two different types of homogeneous networks, i.e. the homogeneous small-world network （HSWN） and the regular ring graph. We find that the so-called resonance-like character can occur on both the networks. Different from the viewpoint in previous publications, we think the small-world effect may be unnecessary to produce this character. Therefore, over these two types of networks, we suggest a common understanding in the viewpoint of clustering coefficient. Detailed simulation results can sustain our viewpoint quite well. Furthermore, we investigate the Snowdrift Game （SG） on the same networks. The difference between the outputs of the PDG and the SG can also sustain our viewpoint.     

Geographical Effects on Complex Networks

We investigate how the geographical structure of a complex network affects its network topology, synchronization and the average spatial length of edges. The geographical structure means that the connecting probability of two nodes is related to the spatial distance of the two nodes. Our simulation results show that the geographical structure changes the network topology. The synchronization tendency is enhanced and the average spatial length of edges is enlarged when the node can randomly connect to the further one. Analytic results support our understanding of the phenomena.     

Step-by-Step Random Walk Network with Power-Law Clique-Degree Distribution

We propose a simple mechanism for generating scale-free networks with degree exponent γ= 3, where the new node is connected to the existing nodes by step-by-step random walk. It is found that the clique-degree distribution based on our model obeys a power-law form, which is in agreement with the recently empirical evidences. In addition, our model displays the small-world effect and the hierarchical structure.     

A Law of Gravitation for Complex Networks

Inspiring Newton＇s law of universal gravitation and empirical studies, we propose a concept of virtual network mass and network gravitational force in complex networks. Then a network gravitational model for complex networks is presented. In the model, each node in the network is described with its position, edges （links） and virtual network mass. The proposed model is examined by experiments to show its potential applications.