Navigational bottlenecks in nonconservative diffusion dynamics on networks

Abstract

Diffusion is a ubiquitous process in real-world syetems. In many complex systems, ranging from neuronal networks to traffic in cities, diffusion is nonconservative (NC) in the sense that diffusive particles can be created/annihilated at the entities of the system. Here, we consider the important problem of identifying potential navigational bottlenecks in NC diffusion occurring in the networks representing skeletons of complex systems. We develop a first-principles approach based on an NC diffusion using the Lerman-Ghosh Laplacian on graphs. By solving analytically this NC diffusion equation at two different times, we get an index which characterizes the capacity of every vertex in a network to spread the diffusive particles across the network in a short time. Vertices having such capacity diminished are potential navigational bottlenecks in this kind of dynamics. We solve analytically the situations in which the vertices with the highest degree (hubs) are at different distances in the network, allowing us to understand the structural significance of the index. Using algebraic methods, we derive a Euclidean distance between vertices in the context of NC diffusion with potential navigational bottlenecks. We then apply these indices to study several real-world networks. First, we confronted our theoretical results with experimental data about traffic congestion in a city. Then, we illustrated the application of the new methodologies to the study of a neuronal system, an air transportation network and two urban street networks.

Keywords

• complex networks
• diffusion
• communicability function
• spectral graph theory
• urban traffic
• network navigability