Extreme events and event size fluctuations in biased random walks on networks

Dynamical Fluctuations of Random Walks in Higher-Order Networks

Although higher-order interactions are known to affect the typical state of dynamical processes giving rise to new collective behavior, how they drive the emergence of rare events and fluctuations is still an open problem. We investigate how fluctuations of a dynamical quantity of a random walk exploring a higher-order network arise over time. In the quenched case, where the hypergraph structure is fixed, through large deviation theory we show that the appearance of rare events is hampered in nodes with many higher-order interactions, and promoted elsewhere. Dynamical fluctuations are further boosted in an annealed scenario, where both the diffusion process and higher-order interactions evolve in time. Here, extreme fluctuations generated by optimal higher-order configurations can be predicted in the limit of a saddle-point approximation. Our study lays the groundwork for a wide and general theory of fluctuations and rare events in higher-order networks.

Dynamical phase transition in the occupation fraction statistics for noncrossing Brownian particles

We consider a system of N noncrossing Brownian particles in one dimension. We find the exact rate function that describes the long-time large deviation statistics of their occupation fraction in a finite interval in space. Remarkably, we find that, for any general N≥2, the system undergoes N-1 dynamical phase transitions of second order. The N-1 transitions are the boundaries of N phases that correspond to different numbers of particles which are in the vicinity of the interval throughout the dynamics. We achieve this by mapping the problem to that of finding the ground-state energy for N noninteracting spinless fermions in a square-well potential. The phases correspond to different numbers of single-body bound states for the quantum problem. We also study the process conditioned on a given occupation fraction and the large-N limiting behavior.

Optimal exploration of random walks with local bias on networks

We propose local-biased random walks on general networks where a Markovian walker is defined by different types of biases in each node to establish transitions to its neighbors depending on their degrees. For this ergodic dynamics, we explore the capacity of the random walker to visit all the nodes characterized by a global mean first passage time. This quantity is calculated using eigenvalues and eigenvectors of the transition matrix that defines the dynamics. In the first part, we illustrate how our framework leads to optimal exploration for small-size graphs through the analysis of all the possible bias configurations. In the second part, we study the most favorable configurations in each node by using simulated annealing. This heuristic algorithm allows obtaining approximate solutions of the optimal bias in different types of networks. The results show how the local bias can optimize the exploration of the network in comparison with the unbiased random walk. The methods implemented in this research are general and open the doors to a broad spectrum of tools applicable to different random walk strategies and dynamical processes on networks.

Biased random walkers and extreme events on the edges of complex networks

Extreme events have low occurrence probabilities and display pronounced deviation from their average behavior, such as earthquakes or power blackouts. Such extreme events occurring on the nodes of a complex network have been extensively studied earlier through the modeling framework of unbiased random walks. They reveal that the occurrence probability for extreme events on nodes of a network has a strong dependence on the nodal properties. Apart from these, a recent work has shown the independence of extreme events on edges from those occurring on nodes. Hence, in this work, we propose a more general formalism to study the properties of extreme events arising from biased random walkers on the edges of a network. This formalism is applied to biases based on a variety network centrality measures including PageRank. It is shown that with biased random walkers as the dynamics on the network, extreme event probabilities depend on the local properties of the edges. The probabilities are highly variable for some edges of the network, while they are approximately a constant for some other edges on the same network. This feature is robust with respect to different biases applied to the random walk algorithm. Further, using the results from this formalism, it is shown that a network is far more robust to extreme events occurring on edges when compared to those occurring on the nodes.

Mean encounter times for multiple random walkers on networks

We introduce a general approach for the study of the collective dynamics of noninteracting random walkers on connected networks. We analyze the movement of R independent (Markovian) walkers, each defined by its own transition matrix. By using the eigenvalues and eigenvectors of the R independent transition matrices, we deduce analytical expressions for the collective stationary distribution and the average number of steps needed by the random walkers to start in a particular configuration and reach specific nodes the first time (mean first-passage times), as well as global times that characterize the global activity. We apply these results to the study of mean first-encounter times for local and nonlocal random walk strategies on different types of networks, with both synchronous and asynchronous motion.

Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks

Numerous problems of both theoretical and practical interest are related to finding shortest (or otherwise optimal) paths in networks, frequently in the presence of some obstacles or constraints. A somewhat related class of problems focuses on finding optimal distributions of weights which, for a given connection topology, maximize some kind of flow or minimize a given cost function. We show that both sets of problems can be approached through an analysis of the large-deviation functions of random walks. Specifically, a study of ensembles of trajectories allows us to find optimal paths, or design optimal weighted networks, by means of an auxiliary stochastic process (the generalized Doob transform). The paths are not limited to shortest paths, and the weights must not necessarily optimize a given function. Paths and weights can in fact be tailored to a given statistics of a time-integrated observable, which may be an activity or current, or local functions marking the passing of the random walker through a given node or link. We illustrate this idea with an exploration of optimal paths in the presence of obstacles, and networks that optimize flows under constraints on local observables.

Extreme events in stochastic transport on networks

Extreme events are emergent phenomena in multi-particle transport processes on complex networks. In practice, such events could range from power blackouts to call drops in cellular networks to traffic congestion on roads. All the earlier studies of extreme events on complex networks had focused only on the nodal events. If random walks are used to model the transport process on a network, it is known that degree of the nodes determines the extreme event properties. In contrast, in this work, it is shown that extreme events on the edges display a distinct set of properties from that of the nodes. It is analytically shown that the probability for the occurrence of extreme events on an edge is independent of the degree of the nodes linked by the edge and is dependent only on the total number of edges on the network and the number of walkers on it. Further, it is also demonstrated that non-trivial correlations can exist between the extreme events on the nodes and the edges. These results are in agreement with the numerical simulations on synthetic and real-life networks.

Large deviations of random walks on random graphs

We study the rare fluctuations or large deviations of time-integrated functionals or observables of an unbiased random walk evolving on Erdös-Rényi random graphs, and construct a modified, biased random walk that explains how these fluctuations arise in the long-time limit. Two observables are considered: the sum of the degrees visited by the random walk and the sum of their logarithm, related to the trajectory entropy. The modified random walk is used for both quantities to explain how sudden changes in degree fluctuations, similar to dynamical phase transitions, are related to localization transitions. For the second quantity, we also establish links between the large deviations of the trajectory entropy and the maximum entropy random walk.

Dependence of extreme events on spatial location

To model the dependence of extreme events on locations, we consider extreme events of Brownian particles in a potential. We find that barring the exception of very large potentials and/or very small regions, in general, the probability of extreme events increases with the potential. Our approach is general and can be useful for studying several complex systems.

Extreme events in multilayer, interdependent complex networks and control

We investigate the emergence of extreme events in interdependent networks. We introduce an inter-layer traffic resource competing mechanism to account for the limited capacity associated with distinct network layers. A striking finding is that, when the number of network layers and/or the overlap among the layers are increased, extreme events can emerge in a cascading manner on a global scale. Asymptotically, there are two stable absorption states: a state free of extreme events and a state of full of extreme events, and the transition between them is abrupt. Our results indicate that internal interactions in the multiplex system can yield qualitatively distinct phenomena associated with extreme events that do not occur for independent network layers. An implication is that, e.g., public resource competitions among different service providers can lead to a higher resource requirement than naively expected. We derive an analytical theory to understand the emergence of global-scale extreme events based on the concept of effective betweenness. We also articulate a cost-effective control scheme through increasing the capacity of very few hubs to suppress the cascading process of extreme events so as to protect the entire multi-layer infrastructure against global-scale breakdown.

Convergence of large-deviation estimators

We study the convergence of statistical estimators used in the estimation of large-deviation functions describing the fluctuations of equilibrium, nonequilibrium, and manmade stochastic systems. We give conditions for the convergence of these estimators with sample size, based on the boundedness or unboundedness of the quantity sampled, and discuss how statistical errors should be defined in different parts of the convergence region. Our results shed light on previous reports of "phase transitions" in the statistics of free energy estimators and establish a general framework for reliably estimating large-deviation functions from simulation and experimental data and identifying parameter regions where this estimation converges.

Robustness of scale-free networks to cascading failures induced by fluctuating loads

Taking into account the fact that overload failures in real-world functional networks are usually caused by extreme values of temporally fluctuating loads that exceed the allowable range, we study the robustness of scale-free networks against cascading overload failures induced by fluctuating loads. In our model, loads are described by random walkers moving on a network and a node fails when the number of walkers on the node is beyond the node capacity. Our results obtained by using the generating function method show that scale-free networks are more robust against cascading overload failures than Erdős-Rényi random graphs with homogeneous degree distributions. This conclusion is contrary to that predicted by previous works, which neglect the effect of fluctuations of loads.

Controlling extreme events on complex networks

Extreme events, a type of collective behavior in complex networked dynamical systems, often can have catastrophic consequences. To develop effective strategies to control extreme events is of fundamental importance and practical interest. Utilizing transportation dynamics on complex networks as a prototypical setting, we find that making the network “mobile” can effectively suppress extreme events. A striking, resonance-like phenomenon is uncovered, where an optimal degree of mobility exists for which the probability of extreme events is minimized. We derive an analytic theory to understand the mechanism of control at a detailed and quantitative level, and validate the theory numerically. Implications of our finding to current areas such as cybersecurity are discussed.

Extreme-value statistics of brain networks: importance of balanced condition

Despite the key role played by inhibitory-excitatory couplings in the functioning of brain networks, the impact of a balanced condition on the stability properties of underlying networks remains largely unknown. We investigate properties of the largest eigenvalues of networks having such couplings, and find that they follow completely different statistics when in the balanced situation. Based on numerical simulations, we demonstrate that the transition from Weibull to Fréchet via the Gumbel distribution can be controlled by the variance of the column sum of the adjacency matrix, which depends monotonically on the denseness of the underlying network. As a balanced condition is imposed, the largest real part of the eigenvalue emulates a transition to the generalized extreme-value statistics, independent of the inhibitory connection probability. Furthermore, the transition to the Weibull statistics and the small-world transition occur at the same rewiring probability, reflecting a more stable system.

Manipulation of extreme events on scale-free networks

Extreme events taking place on networks are not uncommon. We show that it is possible to manipulate the extreme event occurrence probabilities and distribution over the nodes of a scale-free network by tuning the nodal capacity. This can be used to reduce the number of extreme event occurrences. However, monotonic nodal capacity enhancements, beyond a point, do not lead to any substantial reduction in the number of extreme events. We point out the practical implication of this result for network design in the context of reducing extreme event occurrences.

Structural robustness of scale-free networks against overload failures

We study the structural robustness of scale-free networks against overload failures induced by loads exceeding the node capacity, based on analytical and numerical approaches to the percolation problem in which a fixed number of nodes are removed according to the overload probability. Modeling fluctuating loads by random walkers in a network, we find that the degree dependence of the overload probability drastically changes with respect to the total load. We also elucidate that there exist two types of structural robustness of networks against overload failures. One is measured by the critical total load W(c) and the other is by the critical node removal fraction f(c). Enhancing the scale-free property, networks become fragile in both senses of W(c) and f(c). By contrast, increasing the node tolerance, scale-free networks become robust in the sense of the critical total load, while they come to be fragile in the sense of the critical node removal fraction. Furthermore, we show that these trends are not affected by degree-degree correlations, although assortative mixing makes networks robust in both senses of W(c) and f(c).