A generalised path-percolation framework is introduced where paths are drawn from a temperature-controlled routing ensemble interpolating between geodesic and noisy transport, clarifying how microscopic routing organisation shapes macroscopic resilience, and identifying path elongation as a measurable precursor of failure in communication and transport infrastructure.
Abstract
Traffic-induced failures, from packet loss in communication networks to congestion breakdown in transport systems, occur when flows progressively exhaust the edges they traverse. Path percolation models this process by removing edges along sampled origin-destination paths. Existing work assumes locally tree-like networks and deterministic shortest-path routing, leaving unclear how path degeneracy and routing stochasticity affect fragmentation in the clustered networks typical of real systems. We introduce a generalised path-percolation framework where paths are drawn from a temperature-controlled routing ensemble interpolating between geodesic and noisy transport. We argue based on box-covering renormalisation and our numerical experiments that, for any finite routing horizon $C$, the process coarse-grains to ordinary mean-field percolation. Routing details affect non-universal quantities, especially the percolation threshold $p_c$, through the entropy of the load distribution and the capacity of finite clusters to accommodate flow. Load entropy therefore acts as a robustness measure for networks under path-based failures. When the routing horizon is tuned to the mean-field correlation length, $C=N^{1/3}$, within a source-uniform ensemble, the system enters a crossover regime with scaling exponents distinct from shortest-path percolation with infinite budget. In this regime, path elongation becomes decoupled in time from structural fragmentation: the characteristic path length reaches a growing maximum, associated with routing temperature, asymptotically ahead of the collapse of the giant component. These results clarify how microscopic routing organisation shapes macroscopic resilience, and identify path elongation as a measurable precursor of failure in communication and transport infrastructure.
Adding links generally improves classical transport by increasing the number of available paths. We show that coherent quantum transport can display the opposite behavior. Using continuous-time quantum walks on a percolated hierarchical small-world network, we identify a coherent overconnectivity penalty: root-to-boundary transport is maximized at intermediate bond probability and decreases as the network approaches full connectivity. The effect is quantified by the final-layer limiting probability $\chi_N$ and by the penalty $P_Q=1-\chi_N(p=1)/\max_p\chi_N(p)$, which measures the loss caused by making the architecture fully connected. The optimum results from a competition between shortcut-assisted spreading and interference-induced intra-layer recirculation. Spectral analysis shows that bond dilution creates motif-induced degeneracies and reorganizes the eigenstates connecting the root to the outermost layer. A comparison with dephased and classical transport shows that the non-monotonic landscape is not a purely geometrical percolation effect, but a coherent architecture-dependent phenomenon. These results provide a design principle for coherent transport in disordered photonic and quantum-network architectures.
Predicting the percolation threshold of highly clustered networks from local statistics remains difficult, because short loops break the independence assumption underlying tree-like message passing. Existing remedies address loopy connectivity either through prescribed local motifs in random-graph ensembles or through a single network's realized topology, leaving an ensemble-level treatment of arbitrary connectivity patterns absent. Here, we develop a loopy message-passing framework for random clustered graph ensembles based on generalized-edge statistics, which characterize overlap patterns among the neighborhoods of different nodes. This yields a progressively refined approximation scheme based on neighborhoods of increasing size around each node. The low-order approximations recover previous equations for random network ensembles, and the new result that yields refined threshold prediction is developed by the second-order approximation. We show that the effectiveness of this framework depends not only on short-cycle density but also on the internal consistency of generalized edges. To diagnose this effectiveness, we introduce the generalized-edge closure coefficient (GECC) to quantify this consistency. Because GECC is computed entirely from local statistics and does not rely on any percolation calculation, it serves as an a priori diagnostic for the reliability of the approximation. Using synthetic and real networks, the threshold is evaluated via the second-order and lower-order approximations. Comparisons with Monte Carlo simulations show that GECC captures key structural features that strongly affect the percolation threshold. These results establish ensemble-based loopy message passing as an efficient route for predicting the percolation threshold in large clustered networks.
The analysis of random walks on networks often relies on global quantities that average over nodes, thereby masking local differences in diffusion speed. This study introduces a vertex-level quantity Hi, defined as the finite-window fitted scaling exponent of the mean squared resistance distance ⟨Ωi2(t)⟩∼Cit2Hi from a given node i. We found nodes with Hi values below 0.5 (echo effect) and above 0.5 (catapult effect). The exponent is computed exactly via matrix powers of the transition matrix. We systematically evaluate Hi on several synthetic network families, generalized Sierpiński graphs, Newman-Watts small-world networks, and a custom grid-path-complete graph, and on two real-world networks (international E-road network and western U.S. power grid). We found nodes with Hi values less than 0.5 (subdiffusive regime) and greater than 0.5 (apparent superdiffusion) in both model networks and real-world networks. Analysis of model networks shows that when a node has an echo effect, its Hi value is less than 0.5, whereas when it has a catapult effect, its Hi value is greater than 0.5. In the two real networks, most nodes are in the subdiffusive regime and the overall heterogeneity of the local diffusion exponents is low, as indicated by Rényi indices of 0.0835 (E-road network) and 0.0555 (power grid). Comparisons with classical centrality measures indicate that Hi provides information not captured by those measures. The local diffusion exponent offers a vertex-level, dynamics-based tool for identifying structural bottlenecks and node roles, complementing global network characterizations.
We present a general computational framework for macroscopic nonlocal traffic flow models on networks with multiple commodities. The model combines scalar conservation laws on edges with nonlocal velocity functions and couples them via buffer-based junction dynamics. Routing is defined in general as a prescription for distributing drivers across outgoing road segments. As an example, we implement dynamic k-shortest-path routing, where travel times along roads and waiting times at intersections are used to compute shortest paths to the commodities'destinations at each time step, and drivers are distributed accordingly. In another example, we optimize routing over a considered time horizon to minimize the total travel time. This framework naturally creates a feedback loop between traffic evolution and route choice. Numerical examples, ranging from small test cases to large grid-like networks, demonstrate the robustness of the approach and allow for a comparison of different routing strategies.
Alexander Keimer, L. Pflug, F. Prohaska· 0 citations
Extreme events play a central role in networked stochastic processes, governing the fastest information spreading, quickest search, and earliest arrival in many real-world systems. In this paper, we develop a unified short-time framework for extreme reachability of continuous-time random walks on networks. We show that both the many-walker limit and the frequent-resetting limit are controlled by the short-time asymptotics of the first-passage time distribution, which is determined by the network's shortest-path structure and transition rates. By introducing an instantaneous arrival intensity based on shortest-path contributions, we derive explicit scaling laws for extreme first-passage times and demonstrate that these seemingly distinct regimes are governed by the same underlying network quantity. Our framework reveals a universal mechanism by which network topology shapes extreme events in continuous-time dynamics, independent of long-time diffusion properties. We further propose an efficient method to compute the short-time arrival intensity on large networks and validate our predictions on both synthetic and real-world graphs. The results provide a principled basis for quantifying extreme reachability, fastest search, and robustness under restarting in networked systems.
Fei Ma, Xincheng Hu, Jinzhi Ouyang et al.· Proceedings of the 32nd ACM...· 0 citations
Probability distributions are central to information theory, statistical inference, and modern probabilistic learning. Maximum entropy selects a probability state under prescribed constraints, but it does not specify how that state is reached, how probability is transported, or how dissipation and external information exchange are accounted for along the path. We develop a path-dependent entropic Lagrangian calculus that extends static state selection to probability-path evolution through restricted generators, upper-limit history terms, and explicit balance--entropy port routing. The construction yields the thermal state relation, conservative probability balance, and nonnegative production under standard mobility closure. Its KL/Shannon sector recovers maximum-entropy and Bayesian laws as stationary no-flux states, while time-dependent information potentials separate internal dissipation from supplied information power. Composable information and structural potentials control tails, sparsity, robustness, regularization, and nonlocal multimodality without changing the accounting architecture. Two numerical examples verify mass conservation, energy decomposition, and the total free-energy ledger.