Bilevel optimization in flow networks: A message-passing approach.

Optimizing embedded systems, where the optimization of one depends on the state of another, is a formidable computational and algorithmic challenge, that is ubiquitous in real world systems. We study flow networks, where bilevel optimization is relevant to traffic planning, network control, and design, and where flows are governed by an optimization requirement subject to the network parameters. We employ message passing algorithms in flow networks with sparsely coupled structures to adapt network parameters that govern the network flows, in order to optimize a global objective. We demonstrate the effectiveness and efficiency of the approach on randomly generated graphs.

Scalable node-disjoint and edge-disjoint multiwavelength routing.

Probabilistic message-passing algorithms are developed for routing transmissions in multiwavelength optical communication networks, under node- and edge-disjoint routing constraints and for various objective functions. Global routing optimization is a hard computational task on its own but is made much more difficult under the node- and edge-disjoint constraints and in the presence of multiple wavelengths, a problem which dominates routing efficiency in real optical communication networks that carry most of the world's internet traffic. The scalable principled method we have developed is exact on trees but provides good approximate solutions on locally treelike graphs. It accommodates a variety of objective functions that correspond to low latency, load balancing, and consolidation of routes and can be easily extended to include heterogeneous signal-to-noise values on edges and a restriction on the available wavelengths per edge. It can be used for routing and managing transmissions on existing topologies as well as for designing and modifying optical communication networks. Additionally, it provides the tool for settling an open and much-debated question on the merit of wavelength-switching nodes and the added capabilities they provide. The methods have been tested on generated networks such as random-regular, Erdos Rényi, and power-law graphs, as well as on optical communication networks in the United Kingdom and United States. They show excellent performance with respect to existing methodology on small networks and have been scaled up to network sizes that are beyond the reach of most existing algorithms.

Estimating urban air pollution contribution to South Platte River nitrogen loads with National Atmospheric Deposition Program data and SPARROW model.

Air pollution is commonly disregarded as a source of nutrient loading to impaired surface waters managed under the Clean Water Act per states' 303(d) list programs. The contribution of air pollution to 2017-2018 South Platte River nitrogen (N) loads was estimated from the headwaters to the gage at Weldona, Colorado, USA (100 km downstream of Denver), using data from the National Atmospheric Deposition Program (NADP) and the SPAtially Referenced Regressions On Watershed attributes (SPARROW) model. The NADP offers wet-deposition raster created by spatial interpolation of data collected from regionally representative monitoring sites, excluding the influences from urban site data. For this study, NADP wet-deposition data obtained from sites within the Denver-Boulder, Colorado, urban corridor were included and excluded in new spatial interpolations of wet-deposition raster, which were used as input for SPARROW to model the influence of urban air pollution sources on South Platte River loads. Because urban air pollution is already incorporated into the NADP Total Deposition modeling methodology, dry N deposition was held constant for each SPARROW modeling scenario when dry deposition was included. By including the urban wet-deposition data in the model, estimated N loading to the South Platte River at Denver increased by 9-11 percent. Factoring in dry deposition at a 1:1.8 dry:wet ratio obtained from the results, urban air pollution was estimated to contribute as much as 20 percent of the nitrate Total Maximum Daily Load for Segment 14 of the South Platte River.

Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis.

Infectious diseases that incorporate presymptomatic transmission are challenging to monitor, model, predict, and contain. We address this scenario by studying a variant of a stochastic susceptible-exposed-infected-recovered model on arbitrary network instances using an analytical framework based on the method of dynamic message passing. This framework provides a good estimate of the probabilistic evolution of the spread on both static and contact networks, offering a significantly improved accuracy with respect to individual-based mean-field approaches while requiring a much lower computational cost compared to numerical simulations. It facilitates the derivation of epidemic thresholds, which are phase boundaries separating parameter regimes where infections can be effectively contained from those where they cannot. These have clear implications on different containment strategies through topological (reducing contacts) and infection parameter changes (e.g., social distancing and wearing face masks), with relevance to the recent COVID-19 pandemic.

Futility of being selfish in optimized traffic.

Optimizing traffic flow is essential for easing congestion. However, even when globally optimal, coordinated, and individualized routes are provided, users may choose alternative routes which offer lower individual costs. By analyzing the impact of selfish route choices on performance using the cavity method, we find that a small ratio of selfish route choices improves the global performance of uncoordinated transportation networks but degrades the efficiency of optimized systems. Remarkably, compliant users always gain in the former and selfish users may gain in the latter, under some parameter conditions. The theoretical results are in good agreement with large-scale simulations. Iterative route switching by a small fraction of selfish users leads to Nash equilibria close to the globally optimal routing solution. Our theoretical framework also generalizes the use of the cavity method, originally developed for the study of equilibrium states, to analyze iterative game-theoretical problems. These results shed light on the feasibility of easing congestion by route coordination when not all vehicles follow the coordinated routes.

Space of Functions Computed by Deep-Layered Machines.

We study the space of functions computed by random-layered machines, including deep neural networks and Boolean circuits. Investigating the distribution of Boolean functions computed on the recurrent and layer-dependent architectures, we find that it is the same in both models. Depending on the initial conditions and computing elements used, we characterize the space of functions computed at the large depth limit and show that the macroscopic entropy of Boolean functions is either monotonically increasing or decreasing with the growing depth.

Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example.

Lower temperature leads to a higher probability of visiting low-energy states. This intuitive belief underlies most physics-inspired strategies for addressing hard optimization problems. For instance, the popular simulated annealing (SA) dynamics is expected to approach a ground state if the temperature is lowered appropriately. Here, we demonstrate that this belief is not always justified. Specifically, we employ the cavity method to analyze the minimum strong defensive alliance problem and discover a bifurcation in the solution space, induced by an inflection point in the entropy-energy profile. While easily accessible configurations are associated with the lower-free-energy branch, the low-energy configurations are associated with the higher-free-energy branch within the same temperature range. There is a discontinuous phase transition between the high-energy configurations and the ground states, which generally cannot be followed by SA. We introduce an energy-clamping strategy to obtain superior solutions by following the higher-free-energy branch, overcoming the limitations of SA.

Slow spin dynamics and self-sustained clusters in sparsely connected systems.

To identify emerging microscopic structures in low-temperature spin glasses, we study self-sustained clusters (SSC) in spin models defined on sparse random graphs. A message-passing algorithm is developed to determine the probability of individual spins to belong to SSC. We then compare the predicted SSC associations with the dynamical properties of spins obtained from numerical simulations and show that SSC association identifies individual slow-evolving spins. Studies of Erdos-Renyi (ER) and random regular (RR) graphs show that spins belonging to SSC are more stable with respect to spin-flip fluctuations, as suggested by the analysis of fully connected models. Further analyses show that SSC association outperforms local fields in predicting the spin dynamics, specifically the group of slow- and fast-evolving spins in RR graphs, for a wide temperature range close to the spin-glass transition. This insight gives rise to a powerful approach for predicting individual spin dynamics from a single snapshot of an equilibrium spin configuration, namely from limited static information. It also implies that single-sample SSC association carries more information than local fields in describing the state of individual spins, when little information can be extracted from the system's topology.

Exploring the Function Space of Deep-Learning Machines.

The function space of deep-learning machines is investigated by studying growth in the entropy of functions of a given error with respect to a reference function, realized by a deep-learning machine. Using physics-inspired methods we study both sparsely and densely connected architectures to discover a layerwise convergence of candidate functions, marked by a corresponding reduction in entropy when approaching the reference function, gain insight into the importance of having a large number of layers, and observe phase transitions as the error increases.

Optimal deployment of resources for maximizing impact in spreading processes.

The effective use of limited resources for controlling spreading processes on networks is of prime significance in diverse contexts, ranging from the identification of "influential spreaders" for maximizing information dissemination and targeted interventions in regulatory networks, to the development of mitigation policies for infectious diseases and financial contagion in economic systems. Solutions for these optimization tasks that are based purely on topological arguments are not fully satisfactory; in realistic settings, the problem is often characterized by heterogeneous interactions and requires interventions in a dynamic fashion over a finite time window via a restricted set of controllable nodes. The optimal distribution of available resources hence results from an interplay between network topology and spreading dynamics. We show how these problems can be addressed as particular instances of a universal analytical framework based on a scalable dynamic message-passing approach and demonstrate the efficacy of the method on a variety of real-world examples.

Chimera-like states in structured heterogeneous networks.

Chimera-like states are manifested through the coexistence of synchronous and asynchronous dynamics and have been observed in various systems. To analyze the role of network topology in giving rise to chimera-like states, we study a heterogeneous network model comprising two groups of nodes, of high and low degrees of connectivity. The architecture facilitates the analysis of the system, which separates into a densely connected coherent group of nodes, perturbed by their sparsely connected drifting neighbors. It describes a synchronous behavior of the densely connected group and scaling properties of the induced perturbations.

Emerging interdependence between stock values during financial crashes.

To identify emerging interdependencies between traded stocks we investigate the behavior of the stocks of FTSE 100 companies in the period 2000-2015, by looking at daily stock values. Exploiting the power of information theoretical measures to extract direct influences between multiple time series, we compute the information flow across stock values to identify several different regimes. While small information flows is detected in most of the period, a dramatically different situation occurs in the proximity of global financial crises, where stock values exhibit strong and substantial interdependence for a prolonged period. This behavior is consistent with what one would generally expect from a complex system near criticality in physical systems, showing the long lasting effects of crashes on stock markets.

Compression by replication.

A recently introduced inference method based on system replication and an online message passing algorithm is employed to complete a previously suggested compression scheme based on a nonlinear perceptron. The algorithm is shown to approach the information theoretical bounds for compression as the number of replicated systems increases, offering superior performance compared to basic message passing algorithms. In addition, the suggested method does not require fine-tuning of parameters or other complementing heuristic techniques, such as the introduction of inertia terms, to improve convergence rates to nontrivial results.

SPARROW Models Used to Understand Nutrient Sources in the Mississippi/Atchafalaya River Basin.

Nitrogen (N) and phosphorus (P) loading from the Mississippi/Atchafalaya River Basin (MARB) has been linked to hypoxia in the Gulf of Mexico. To describe where and from what sources those loads originate, SPAtially Referenced Regression On Watershed attributes (SPARROW) models were constructed for the MARB using geospatial datasets for 2002, including inputs from wastewater treatment plants (WWTPs), and calibration sites throughout the MARB. Previous studies found that highest N and P yields were from the north-central part of the MARB (Corn Belt). Based on the MARB SPARROW models, highest N yields were still from the Corn Belt but centered over Iowa and Indiana, and highest P yields were widely distributed throughout the center of the MARB. Similar to that found in other studies, agricultural inputs were found to be the largest N and P sources throughout most of the MARB: farm fertilizers were the largest N source, whereas farm fertilizers, manure, and urban inputs were dominant P sources. The MARB models enable individual N and P sources to be defined at scales ranging from SPARROW catchments (∼50 km) to the entire area of the MARB. Inputs of P from WWTPs and urban areas were more important than found in most other studies. Information from this study will help to reduce nutrient loading from the MARB by providing managers with a description of where each of the sources of N and P are most important, thus providing a basis for prioritizing management actions and ultimately reducing the extent of Gulf hypoxia.

Self-sustained clusters and ergodicity breaking in spin models.

Self-sustained spin clusters are analytically linked to ergodicity breaking in fully connected Ising and Sherrington-Kirkpatick (SK) models, relating the less understood spin space to the well understood state space. This correspondence is established through the absence of clusters in the paramagnetic phase, the presence of one dominant cluster in the Ising ferromagnet, and the formation of nontrivial clusters in SK spin glass. Yet unobserved phenomena are also revealed such as a first order phase transition in cluster sizes in the SK ferromagnet. The method could be adapted to investigate other spin models.

Replication-based inference algorithms for hard computational problems.

Inference algorithms based on evolving interactions between replicated solutions are introduced and analyzed on a prototypical NP-hard problem: the capacity of the binary Ising perceptron. The efficiency of the algorithm is examined numerically against that of the parallel tempering algorithm, showing improved performance in terms of the results obtained, computing requirements and simplicity of implementation.

From the physics of interacting polymers to optimizing routes on the London Underground.

Optimizing paths on networks is crucial for many applications, ranging from subway traffic to Internet communication. Because global path optimization that takes account of all path choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing suboptimal solutions. We use the physics of interacting polymers and disordered systems to analyze macroscopic properties of generic path optimization problems and derive a simple, principled, generic, and distributed routing algorithm capable of considering all individual path choices simultaneously. We demonstrate the efficacy of the algorithm by applying it to: (i) random graphs resembling Internet overlay networks, (ii) travel on the London Underground network based on Oyster card data, and (iii) the global airport network. Analytically derived macroscopic properties give rise to insightful new routing phenomena, including phase transitions and scaling laws, that facilitate better understanding of the appropriate operational regimes and their limitations, which are difficult to obtain otherwise.

Interacting nonequilibrium systems with two temperatures.

We investigate a simplified model of two fully connected magnetic systems maintained at different temperatures by virtue of being connected to two independent thermal baths while simultaneously being interconnected with each other. Using generating functional analysis, commonly used in statistical mechanics, we find exactly soluble expressions for their individual magnetization that define a two-dimensional nonlinear map, the equations of which have the same form as those obtained for densely connected equilibrium systems. Steady states correspond to the fixed points of this map, separating the parameter space into a rich set of nonequilibrium phases that we analyze in asymptotically high and low (nonequilibrium) temperature limits. The theoretical formalism is shown to revert to the classical nonequilibrium steady state problem for two interacting systems with a nonzero heat transfer between them that catalyzes a phase transition between ambient nonequilibrium states.

Vulnerability of streams to legacy nitrate sources.

The influence of hydrogeologic setting on the susceptibility of streams to legacy nitrate was examined at seven study sites having a wide range of base flow index (BFI) values. BFI is the ratio of base flow to total streamflow volume. The portion of annual stream nitrate loads from base flow was strongly correlated with BFI. Furthermore, dissolved oxygen concentrations in streambed pore water were significantly higher in high BFI watersheds than in low BFI watersheds suggesting that geochemical conditions favor nitrate transport through the bed when BFI is high. Results from a groundwater-surface water interaction study at a high BFI watershed indicate that decades old nitrate-laden water is discharging to this stream. These findings indicate that high nitrate levels in this stream may be sustained for decades to come regardless of current practices. It is hypothesized that a first approximation of stream vulnerability to legacy nutrients may be made by geospatial analysis of watersheds with high nitrogen inputs and a strong connection to groundwater (e.g., high BFI).

Competition for shortest paths on sparse graphs.

Optimal paths connecting randomly selected network nodes and fixed routers are studied analytically in the presence of a nonlinear overlap cost that penalizes congestion. Routing becomes more difficult as the number of selected nodes increases and exhibits ergodicity breaking in the case of multiple routers. The ground state of such systems reveals nonmonotonic complex behaviors in average path length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers. A distributed linearly scalable routing algorithm is also devised.