Transport on Complex Networks: Flow, Jamming and Optimization

Abstract

Many transport processes on networks depend crucially on the underlying network geometry, although the exact relationship between the structure of the network and the properties of transport processes remain elusive. In this paper we address this question by using numerical models in which both structure and dynamics are controlled systematically. We consider the traffic of information packets that include driving, searching and queuing. We present the results of extensive simulations on two classes of networks; a correlated cyclic scale-free network and an uncorrelated homogeneous weakly clustered network. By measuring different dynamical variables in the free flow regime we show how the global statistical properties of the transport are related to the temporal fluctuations at individual nodes (the traffic noise) and the links (the traffic flow). We then demonstrate that these two network classes appear as representative topologies for optimal traffic flow in the regimes of low density and high density traffic, respectively. We also determine statistical indicators of the pre-jamming regime on different network geometries and discuss the role of queuing and dynamical betweenness for the traffic congestion. The transition to the jammed traffic regime at a critical posting rate on different network topologies is studied as a phase transition with an appropriate order parameter. We also address several open theoretical problems related to the network dynamics.

21 pages, eps figs, to appear in International Journal of Bifurcation and Chaos (Volume 17, Issue 7, July 2007)

References in corpus (35)

• Statistical mechanics of complex networks
• Efficient Behavior of Small-World Networks
• The spread of epidemic disease on networks
• Mixing patterns in networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Dynamics of Rumor Spreading in Complex Networks
• Large-scale topological and dynamical properties of Internet
• Optimal network topologies for local search with congestion
• Communication in networks with hierarchical branching
• Fluctuations in network dynamics
• Epidemic spreading in complex networks with degree correlations
• Traffic on complex networks: Towards understanding global statistical properties from microscopic density fluctuations
• Dynamics of jamming transitions in complex networks
• Congestion and centrality in traffic flow on complex networks
• Critical load and congestion instabilities in scale-free networks
• Dynamical properties of model communication networks
• Dynamics of directed graphs: the world-wide Web
• Information Super-Diffusion on Structured Networks
• Extreme self-organization in networks constructed from gene expression data
• Scaling theory of temporal correlations and size dependent fluctuations in the traded value of stocks
• Effect of congestion costs on shortest paths through complex networks
• Random walks on complex networks with inhomogeneous impact
• Random walk and trapping processes on scale-free networks
• A family-network model for wealth distribution in societies
• Risk trading, network topology, and banking regulation
• Adaptive Random Walks on the Class of Web Graph
• Modeling Dynamics of Information Networks
• Internet's Critical Path Horizon
• Navigating Networks with Limited Information
• Temporal fractal structures: Origin of power-laws in the world-wide Web
• Perturbing General Uncorrelated Networks
• Omori's law in the Internet traffic
• Transport Processes on Homogeneous Planar Graphs with Scale-Free Loops
• Voltage Distribution in Growing Conducting Networks
• Random Walks on Complex Networks

Cited by in corpus (30)

• Critical phenomena in complex networks
• Extreme events in dynamical systems and random walkers: A review
• Spectral and Dynamical Properties in Classes of Sparse Networks with Mesoscopic Inhomogeneities
• Extreme events on complex networks
• The weighted random graph model
• Diversity of information pathways drives scaling and sparsity in real-world networks
• Efficient routing strategies in scale-free networks with limited bandwidth
• Extreme events and event size fluctuations in biased random walks on networks
• Prisoner's dilemma on dynamic networks under perfect rationality
• The Dynamics of Internet Traffic: Self-Similarity, Self-Organization, and Complex Phenomena
• Local Empathy provides Global Minimization of Congestion in Communication Networks
• How Many Nodes are Effectively Accessed in Complex Networks?
• Pattern Formation on Networks with Reactions: A Continuous Time Random Walk Approach
• Preferential Behaviour and Scaling in Diffusive Dynamics on Networks
• Mixing navigation on networks
• Jamming transition in traffic flow under the priority queuing protocol
• Biased diffusion on Japanese inter-firm trading network: Estimation of sales from network structure
• Lower bound of assortativity coefficient in scale-free networks
• Manipulation of extreme events on scale-free networks
• Jamming and Correlation Patterns in Traffic of Information on Sparse Modular Networks
• Optimal transport on supply-demand networks
• Collective emotion dynamics in chats with agents, moderators and Bots
• Enhancing Transport Efficiency by Hybrid Routing Strategy
• Efficient priority queueing routing strategy on mobile networks
• Temporal Taylor's scaling of facial electromyography and electrodermal activity in the course of emotional stimulation
• Optimization in task--completion networks
• Network heterogeneity and node capacity lead to heterogeneous scaling of fluctuations in random walks on graphs
• Network modules help the identification of key transport routes, signaling pathways in cellular and other networks
• Queue-length synchronization in a communication networks
• Temporal Correlations of Local Network Losses