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.     

Scale-free networks by super-linear preferential attachment rule

A network growth model with geographic limitation of accessible information about the status of existing nodes is investigated. In this model, the probability Π(k) of an existing node of degree k is found to be super-linear with Π(k)∼k^α and α>1 when there are links from new nodes. The numerical results show that the constructed networks have typical power-law degree distributions P(k)∼k^−γ and the exponent γ depends on the constraint level. An analysis of local structural features shows the robust emergence of scale-free network structure in spite of the super-linear preferential attachment rule. This local structural feature is directly associated with the geographical connection constraints which are widely observed in many real networks.     

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.     

Influence of network structure on rumor propagation

Rumor propagation in complex networks is studied analytically and numerically by using the SIR model. Analytically, a mean-field theory is worked out by considering the influence of network topological structure and the unequal footings of neighbors of an infected node in propagating the rumor. It is found that the final infected density of population with degree k   is ρ(k)=1−exp(−αk)$\rho (k)=1-\exp (-\alpha k)$, where α is a parameter related to network structure. The number of the total final infected nodes depends on the network topological structure and will decrease when the structure changes from random to scale-free network. Numerical simulations confirm the theoretical predictions.     

Growing networks with preferential deletion and addition of edges

A preferential attachment model for a growing network incorporating the deletion of edges is studied and the expected asymptotic degree distribution is analyzed. At each time step t=1,2,…, with probability π₁>0 a new vertex with one edge attached to it is added to the network and the edge is connected to an existing vertex chosen proportionally to its degree, with probability π₂ a vertex is chosen proportionally to its degree and an edge is added between this vertex and a randomly chosen other vertex, and with probability π₃=1−π₁−π₂<1/2 a vertex is chosen proportionally to its degree and a random edge of this vertex is deleted. The model is intended to capture a situation where high-degree vertices are more dynamic than low-degree vertices in the sense that their connections tend to be changing. A recursion formula is derived for the expected asymptotic fraction p_k of vertices with degree k, and solving this recursion reveals that, for π₃<1/3, we have p_k∼k^{−(3−7π₃)/(1−3π₃)}, while, for π₃>1/3, the fraction p_k decays exponentially at rate (π₁+π₂)/2π₃. There is hence a non-trivial upper bound for how much deletion the network can incorporate without losing the power-law behavior of the degree distribution. The analytical results are supported by simulations.     

A weighted network evolution with traffic flow

In this paper, we propose a simple weighted network model that generalizes the complex network model evolution with traffic flow previously presented to investigate the relationship between traffic flow and network structure. In the model, the nodes in the network are represented by the traffic flow states, the links in the network are represented by the transform of the traffic flow states, and the traffic flow transported when performing the transform of the traffic flow states is considered as the weight of the link. Several topological features of this generalized weighted model, such as the degree distribution and strength distribution, have been numerically studied. A scaling behavior between the strength and degree s∼klogk is obtained. By introducing some constraints to the generalized weighted model, we study its subnetworks and find that the scaling behavior between the strength and degree is conserved, though the topology properties are quite sensitive to the constraints.     

Edge-based-attack induced cascading failures on scale-free networks

Most previous existing works on cascading failures only focused on attacks on nodes rather than on edges. In this paper, we discuss the response of scale-free networks subject to two different attacks on edges during cascading propagation, i.e., edge removal by either the descending or ascending order of the loads. Adopting a cascading model with a breakdown probability p of an overload edge and the initial load (k_ik_j)^α of an edge ij, where k_i and k_j are the degrees of the nodes connected by the edge ij and α is a tunable parameter, we investigate the effects of two attacks for the robustness of Barabási-Albert (BA) scale-free networks against cascading failures. In the case of α<1, our investigation by the numerical simulations leads to a counterintuitive finding that BA scale-free networks are more sensitive to attacks on the edges with the lowest loads than the ones with the highest loads, not relating to the breakdown probability. In addition, the same effect of two attacks in the case of α=1 may be useful in furthering studies on the control and defense of cascading failures in many real-life networks. We then confirm by the theoretical analysis these results observed in simulations.     

A new deterministic complex network model with hierarchical structure

We introduce a new simple pseudo tree-like network model, deterministic complex network (DCN). The proposed DCN model may simulate the hierarchical structure nature of real networks appropriately and have the unique property of ‘skipping the levels’, which is ubiquitous in social networks. Our results indicate that the DCN model has a rather small average path length and large clustering coefficient, leading to the small-world effect. Strikingly, our DCN model obeys a discrete power-law degree distribution P(k)∝k^−γ, with exponent γ approaching 1.0. We also discover that the relationship between the clustering coefficient and degree follows the scaling law C(k)∼k⁻¹, which quantitatively determines the DCN's hierarchical structure.     

Connectivity of growing networks with link constraints

We propose a growing network model with link constraint, in which new nodes are continuously introduced into the system and immediately connected to preexisting nodes, and any arbitrary node cannot receive new links when it reaches a maximum number of links k_m. The connectivity of the network model is then investigated by means of the rate equation approach. For the connection kernel A(k)=k^γ, the degree distribution n_k takes a power law if γ≥1 and decays stretched exponentially if 0≤γ< 1. We also consider a network system with the connection kernel A(k)=k^α(k_m-k)^β. It is found that n_k approaches a power law in the α> 1 case and has a stretched exponential decay in the 0≤α< 1 case, while it can take a power law with exponential truncation in the special α=β=1 case. Moreover, n_k may have a U-type structure if α> β.     

A local-world node deleting evolving network model

A new type network growth rule which comprises node addition with the concept of local-world connectivity and node deleting is studied. A series of theoretical analysis and numerical simulation to the LWD network are conducted in this Letter. Firstly, the degree distribution p(k) of this network changes no longer pure scale free but truncates by an exponential tail and the truncation in p(k) increases as pa decreases. Secondly, the connectivity is tighter, as the local-world size M increases. Thirdly, the average path length L increases and the clustering coefficient 〈C〉 decreases as generally node deleting increases. Finally, 〈C〉 trends up when the local-world size M increases, so as to kmax. Hence, the expanding local-world can compensate the infection of the node deleting.     

A complex network model based on the Gnutella protocol

Gnutella is one of the basic protocols for P2P software. In this paper, a novel network model based on Gnutella is introduced. The mechanism of this network is based on resource occupancy and search activities of peers. As for the structure, the power-law exponent of in-degree γ_in≈4.2, the length of the average shortest path 〈l〉=57.74, and the diameter of the network is 156; these topological properties of the proposed structure differ from known results.     

Traffic dynamics in scale-free networks with limited packet-delivering capacity

We propose a limited packet-delivering capacity model for traffic dynamics in scale-free networks. In this model, the total node’s packet-delivering capacity is fixed, and the allocation of packet-delivering capacity on node i is proportional to , where k_i is the degree of node i and ? is a adjustable parameter. We have applied this model on the shortest path routing strategy as well as the local routing strategy, and found that there exists an optimal value of parameter ? leading to the maximal network capacity under both routing strategies. We provide some explanations for the emergence of optimal ?.     

Cooperation in N-person evolutionary snowdrift game in scale-free Barabási-Albert networks

Cooperation in the N-person evolutionary snowdrift game (NESG) is studied in scale-free Barabási-Albert (BA) networks. Due to the inhomogeneity of the network, two versions of NESG are proposed and studied. In a model where the size of the competing group varies from agent to agent, the fraction of cooperators drops as a function of the payoff parameter. The networking effect is studied via the fraction of cooperative agents for nodes with a particular degree. For small payoff parameters, it is found that the small-k agents are dominantly cooperators, while large-k agents are of non-cooperators. Studying the spatial correlation reveals that cooperative agents will avoid to be nearest neighbors and the correlation disappears beyond the next-nearest neighbors. The behavior can be explained in terms of the networking effect and payoffs. In another model with a fixed size of competing groups, the fraction of cooperators could show a non-monotonic behavior in the regime of small payoff parameters. This non-trivial behavior is found to be a combined effect of the many agents with the smallest degree in the BA network and the increasing fraction of cooperators among these agents with the payoff for small payoffs.     

Evolutionary prisoner’s dilemma game on weighted scale-free networks

This paper investigates the evolutionary prisoner’s dilemma on weighted scale-free networks. The weighted networks are generated by adopting Barabási-Albert scale-free network and assigning link weight with w_ij=(k_i×k_j)^β. Simulation results show that the cooperation frequency has a strong dependence on β. The value of β which is associated with the maximal cooperation frequency has been sought out. Moreover, Gini coefficient and Pareto exponent of the system’s wealth distribution are investigated. The inequality of wealth distribution is minimized at β≈−1.     

Resonances in a circular dielectric cavity

We study resonance distributions in a circular dielectric cavity. It is shown that the decay-rate distribution has a peak structure and the details of the peak are consistent with the classical survival probability time distribution. We also investigate the behavior of the complex resonance positions at the small opening limit (n→∞, n is the refractive index of the cavity). At the large n limit, the real part of complex resonance positions approaches the solutions with different m of Dirichlet problem with a scale n⁻² and the imaginary part goes zero as n−2m for TM and n−2(m+1) for TE polarization, where m is the order of the resonance.     

Spectral methods and cluster structure in correlation-based networks

We investigate how in complex systems the eigenpairs of the matrices derived from the correlations of multichannel observations reflect the cluster structure of the underlying networks. For this we use daily return data from the NYSE and focus specifically on the spectral properties of weight W_ij=|C|_ij−δ_ij and diffusion matrices D_ij=W_ij/s_j−δ_ij, where C_ij is the correlation matrix and s_i=∑_jW_ij the strength of node j. The eigenvalues (and corresponding eigenvectors) of the weight matrix are ranked in descending order. As in the earlier observations, the first eigenvector stands for a measure of the market correlations. Its components are, to first approximation, equal to the strengths of the nodes and there is a second order, roughly linear, correction. The high ranking eigenvectors, excluding the highest ranking one, are usually assigned to market sectors and industrial branches. Our study shows that both for weight and diffusion matrices the eigenpair analysis is not capable of easily deducing the cluster structure of the network without a priori knowledge. In addition we have studied the clustering of stocks using the asset graph approach with and without spectrum based noise filtering. It turns out that asset graphs are quite insensitive to noise and there is no sharp percolation transition as a function of the ratio of bonds included, thus no natural threshold value for that ratio seems to exist. We suggest that these observations can be of use for other correlation based networks as well.     

Emergence of scale-free behavior in networks from limited-horizon linking and cost trade-offs

We study network growth from a fixed set of initially isolated nodes placed at random on the surface of a sphere. The growth mechanism we use adds edges to the network depending on strictly local gain and cost criteria. Only nodes that are not too far apart on the sphere may be considered for being joined by an edge. Given two such nodes, the joining occurs only if the gain of doing it surpasses the cost. Our model is based on a multiplicative parameter λ that regulates, in a function of node degrees, the maximum geodesic distance that is allowed between nodes for them to be considered for joining. For n nodes distributed uniformly on the sphere, and for within limits that depend on cost-related parameters, we have found that our growth mechanism gives rise to power-law distributions of node degree that are invariant for constant . We also study connectivity- and distance-related properties of the networks.     

Multistability in bidirectional associative memory neural networks

In this Letter, the multistability issue is studied for Bidirectional Associative Memory (BAM) neural networks. Based on the existence and stability analysis of the neural networks with or without delay, it is found that the 2n-dimensional networks can have n³ equilibria and n² equilibria of them are locally exponentially stable, where each layer of the BAM network has n neurons. Furthermore, the results has been extended to (n+m)-dimensional BAM neural networks, where there are n and m neurons on the two layers respectively. Finally, two numerical examples are presented to illustrate the validity of our results.     

Geographical dispersal of mobile communication networks

In this paper, we analyze statistical properties of a communication network constructed from the records of a mobile phone company. The network consists of 2.5 million customers that have placed 810 million communications (phone calls and text messages) over a period of 6 months and for whom we have geographical home localization information. It is shown that the degree distribution in this network has a power-law degree distribution k⁻⁵ and that the probability that two customers are connected by a link follows a gravity model, i.e. decreases as d⁻², where d is the distance between the customers. We also consider the geographical extension of communication triangles and we show that communication triangles are not only composed of geographically adjacent nodes but that they may extend over large distances. This last property is not captured by the existing models of geographical networks and in a last section we propose a new model that reproduces the observed property. Our model, which is based on the migration and on the local adaptation of agents, is then studied analytically and the resulting predictions are confirmed by computer simulations.     

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.