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 ?.     

Detrended Fluctuation Analysis of Traffic Data

Different routing strategies may result in different behaviour of traffic on internet. We analyse the correlation of traffic data for three typical routing strategies by the detrended fluctuation analysis （DFA） and lind that the aregree of correlation of the data can be divided into three regions, i.e. weak, medium, and strong correlation. The DFA scalings are constants in both the regions of weak and strong correlations but monotonically increase in the region of medium correlation. We suggest that it is better to consider the traffic on complex network as three phases, i.e. the free, buffer, and congestion phase, than just as two phases believed before, i.e. the free and congestion phase.     

Information traffic in scale-free networks with fluctuations in packet generation rate

We study the information traffic in scale-free networks where the information generation rate varies with time as a periodic function. We observe that when the fluctuation in packet generation rate increases, the average transit time increases and network performance degrades. In order to improve the transportation efficiency in this situation, we propose a new routing method called mixed routing. It operates in two modes: (1) when the packet generation rate is small, the shortest paths are used to deliver the packets to the destination; (2) when the packet generation rate is large, the traffic loads in central nodes are redistributed to other non-central nodes, using the so-called efficient routing method. We find that the time shifting between the two modes is very critical for the routing performance. Consequently, we provide an efficient method to determine the critical times to shift the routing modes for achieving good network performance.     

Decorrelation of networked communication flow via load-dependent routing weights

Clever assignments of link weights are able to change communication routes in such a way that loads are distributed almost evenly across a network. This is achieved by weight assignments based on the link load. As demonstrated for scale-free as well as synthetic Internet networks, they decorrelate the loads of the nodes and links from the network structure and increase the transport capacity of the network. For various Internet scans the increase of transport capacity amounts to a factor of around five when compared to shortest-path routing.     

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.     

Dynamics of traffic networks: From microscopic and macroscopic perspectives

Considering the microscopic characteristics (vehicle speed, road length etc.) of links and macroscopic behaviors of traffic systems, we derive the critical flow generation rate in scale-free networks. And the dynamics of traffic congestion is studied numerically in this paper. It is shown that the queue length increases with microscopic characteristics of links. Additionally, the critical flow generation rate decreases with increase of the network size N, maximum speed v_max and parameter τ. The significance of this finding is that, in order to improve the traffic environment, both the local information for the single link and behaviors of the whole network must be analyzed simultaneously in a traffic system design.     

How non-uniform tolerance parameter strategy changes the response of scale-free networks to failures

In this paper, we introduce a non-uniform tolerance parameter (TP) strategy (the tolerance parameter is characterized by the proportion between the unused capacity and the capacity of a vertex) and study how the non-uniform TP strategy influences the response of scale-free (SF) networks to cascading failures. Different from constant TP in previous work of Motter and Lai (ML), the TP in the proposed strategy scales as a power-law function of vertex degree with an exponent b. The simulations show that under low construction costs D, when b>0 the tolerance of SF networks can be greatly improved, especially at moderate values of b; When b<0 the tolerance gets worse, compared with the case of constant TP in the ML model. While for high D the tolerance declines slightly with the b, namely b<0 is helpful to the tolerance, and b>0 is harmful. Because for smaller b the cascade of the network is mainly induced by failures of most high-degree vertices; while for larger b, the cascade attributes to damage of most low-degree vertices. Furthermore, we find that the non-uniform TP strategy can cause changes of the structure and the load-degree correlation in the network after the cascade. These results might give insights for the design of both network capacity to improve network robustness under limitation of small cost, and for the design of strategies to defend cascading failures of networks.     

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 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.     

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.     

Detect overlapping and hierarchical community structure in networks

Clustering and community structure is crucial for many network systems and the related dynamic processes. It has been shown that communities are usually overlapping and hierarchical. However, previous methods investigate these two properties of community structure separately. This paper proposes an algorithm (EAGLE) to detect both the overlapping and hierarchical properties of complex community structure together. This algorithm deals with the set of maximal cliques and adopts an agglomerative framework. The quality function of modularity is extended to evaluate the goodness of a cover. The examples of application to real world networks give excellent results.     

Jamming transition in air transportation networks

In this work we present a model of an air transportation traffic system from the complex network modelling viewpoint. In the network, every node corresponds to a given airport, and two nodes are connected by means of flight routes. Each node is weighted according to its load capacity, and links are weighted according to the Euclidean distance that separates each pair of nodes. Local rules describing the behaviour of individual nodes in terms of the surrounding flow have been also modelled, and a random network topology has been chosen in a baseline approach. Numerical simulations describing the diffusion of a given number of agents (aircraft) in this network show the onset of a jamming transition that distinguishes an efficient regime with null amount of airport queues and high diffusivity (free phase) and a regime where bottlenecks suddenly take place, leading to a poor aircraft diffusion (congested phase). Fluctuations are maximal around the congestion threshold, suggesting that the transition is critical. We then proceed by exploring the robustness of our results in neutral random topologies by embedding the model in heterogeneous networks. Specifically, we make use of the European air transportation network formed by 858 airports and 11 170 flight routes connecting them, which we show to be scale-free. The jamming transition is also observed in this case. These results and methodologies may introduce relevant decision-making procedures in order to optimize the air transportation traffic.     

Macro-Behaviour of Agents＇ Opinion under Influence of an External Field

We propose a model to study the evolution of opinion under the influence of all external field on small world network. The maero-behaviour of agents＇ opinion and the relative change rate as time elapses are studied. The external field is found to play an important role in making the opinion s（t） balance or increase, and without the influence of the external field, the relative change rate γ（t） shows nonlinear increasing behaviour as time runs. What is more, this nonlinear increasing behaviour is independent of the initial condition, the strength of the external field and the time that we cancel the external field. The results may reflect some phenomena in our society, such as the function of the macro-control in China or the mass media in our society.     

Measuring distances between complex networks

A previously introduced concept of higher order neighborhoods in complex networks, [R.F.S. Andrade, J.G.V. Miranda, T.P. Lobão, Phys. Rev. E 73 (2006) 046101] is used to define a distance between networks with the same number of nodes. With such measure, expressed in terms of the matrix elements of the neighborhood matrices of each network, it is possible to compare, in a quantitative way, how far apart in the space of neighborhood matrices two networks are. The distance between these matrices depends on both the network topologies and the adopted node numberings. While the numbering of one network is fixed, a Monte Carlo algorithm is used to find the best numbering of the other network, in the sense that it minimizes the distance between the matrices. The minimal value found for the distance reflects differences in the neighborhood structures of the two networks that arise only from distinct topologies. This procedure ends up by providing a projection of the first network on the pattern of the second one. Examples are worked out allowing for a quantitative comparison for distances among distinct networks, as well as among distinct realizations of random networks.     

Is the topology of the Internet network really fit to sustain its function?

The Internet is one of the most interesting realizations of a “complex” network. As a non-supervised growing object, it allows the study of the selective pressure which drives the network to assume its current structure. The DIMES and the ROUTEVIEWS projects are ongoing projects aimed at evaluating the topological structure of the Internet (at the Autonomous System or AS grain-level) on the basis of different types of measurements. The topological analysis of the networks produced by the two projects has allowed us to infer a growth mechanism which has been used to build up synthetic networks with similar properties. These networks have been used as test-beds for the implementation of a model of traffic dynamics, with the aim of assessing the ability of the Internet’s topology to support the basic actions for data traffic handling. Results have been compared with those obtained by using a random network of similar size. The effects of some structural perturbations (arcs and nodes’ removal, traffic localization) have been also evaluated in terms of the induced variations of the network’s efficiency. The resulting scenario is consistent with the hypothesis that the structure of the Internet is only partially fit to host communication processes and that the intelligence of the TCP/IP protocol is partly needed to overcome some “structural” deficiencies.     

A unified model for Sierpinski networks with scale-free scaling and small-world effect

In this paper, we propose an evolving Sierpinski gasket, based on which we establish a model of evolutionary Sierpinski networks (ESNs) that unifies deterministic Sierpinski network [Z.Z. Zhang, S.G. Zhou, T. Zou, L.C. Chen, J.H. Guan, Eur. Phys. J. B 60 (2007) 259] and random Sierpinski network [Z.Z. Zhang, S.G. Zhou, Z. Su, T. Zou, J.H. Guan, Eur. Phys. J. B 65 (2008) 141] to the same framework. We suggest an iterative algorithm generating the ESNs. On the basis of the algorithm, some relevant properties of presented networks are calculated or predicted analytically. Analytical solution shows that the networks under consideration follow a power-law degree distribution, with the distribution exponent continuously tuned in a wide range. The obtained accurate expression of clustering coefficient, together with the prediction of average path length reveals that the ESNs possess small-world effect. All our theoretical results are successfully contrasted by numerical simulations. Moreover, the evolutionary prisoner’s dilemma game is also studied on some limitations of the ESNs, i.e., deterministic Sierpinski network and random Sierpinski network.     

A spatial weighted network model based on optimal expected traffic

We propose a spatial weighted network model based on the optimal expected traffic. The expected traffic represents the prediction of the flow created by two vertices and is calculated by the improved gravity equation. The model maximizes the total expected traffic of the network. By changing two parameters which control the fitness and the geographical constraints, the model can vary its topology and give rise to a variety of statistical properties observed in the real-world network. Notably, our study shows that a linear and a nonlinear strength-degree correlation can emerge when considering and neglecting the “transport effect”, respectively.     

Cross-impact balances: Applying pair interaction systems and multi-value Kauffman nets to multidisciplinary systems analysis

Cross-impact analysis is the name for a familiar method for multidisciplinary systems analysis in social sciences and management sciences, especially in technology foresight, technology assessment and scenario planning. A recently proposed form of cross-impact analysis, CIB, may be of interest for physicists, sociophysicists and complex network researchers because the CIB concept reveals considerable relations to some concepts of these research fields.This article describes the basics of CIB analysis framework, its applications in the social sciences, and its relations to the equilibrium points of pair interaction systems, random graphs, and generalized Kauffman nets.Therefore CIB can be seen as a merger of concepts originating in utterly different scientific fields. This may prove to be fruitful for both sides: For sociophysicists as an example of the application of complex network concepts in the social sciences and for cross-impact practitioners as a source of theoretical insights in the background of their tool.     

Evolutionary games on scale-free networks with a preferential selection mechanism

Considering the heterogeneity of individuals’ influence in the real world, we introduce a preferential selection mechanism to evolutionary games (the Prisoner’s Dilemma Game and the Snowdrift Game) on scale-free networks and focus on the cooperative behavior of the system. In every step, each agent chooses an individual from all its neighbors with a probability proportional to k^α indicating the influence of the neighbor, where k is the degree. Simulation results show that the cooperation level has a non-trivial dependence on α. To understand the effect of preferential selection mechanism on the evolution of the system, we investigate the time series of the cooperator frequency in detail. It is found that the cooperator frequency is greatly influenced by the initial strategy of hub nodes when α>0. This observation is confirmed by investigating the system behavior when some hub nodes’ strategies are fixed.