Mathematical study of complex networks : brain, internet, and power grid

The dissertation is concerned with the mathematical study of various network problems. First, three real-world networks are considered: (i) the human brain network (ii) communication networks, (iii) electric power networks. Although these networks perform very different tasks, they share similar mathematical foundations. The high-level goal is to analyze and/or synthesis each of these systems from a “control and optimization” point of view. After studying these three real-world networks, two abstract network problems are also explored, which are motivated by power systems. The first one is “flow optimization over a flow network” and the second one is “nonlinear optimization over a generalized weighted graph”. The results derived in this dissertation are summarized below.

Brain Networks: Neuroimaging data reveals the coordinated activity of spatially distinct brain regions, which may be represented mathematically as a network of nodes (brain regions) and links (interdependencies). To obtain the brain connectivity network, the graphs associated with the correlation matrix and the inverse covariance matrix—describing marginal and conditional dependencies between brain regions—have been proposed in the literature. A question arises as to whether any of these graphs provides useful information about the brain connectivity. Due to the electrical properties of the brain, this problem will be investigated in the context of electrical circuits. First, we consider an electric circuit model and show that the inverse covariance matrix of the node voltages reveals the topology of the circuit. Second, we study the problem of finding the topology of the circuit based on only measurement. In this case, by assuming that the circuit is hidden inside a black box and only the nodal signals are available for measurement, the aim is to find the topology of the circuit when a limited number of samples are available. For this purpose, we deploy the graphical lasso technique to estimate a sparse inverse covariance matrix. It is shown that the graphical lasso may find most of the circuit topology if the exact covariance matrix is well-conditioned. However, it may fail to work well when this matrix is ill-conditioned. To deal with ill-conditioned matrices, we propose a small modification to the graphical lasso algorithm and demonstrate its performance. Finally, the technique developed in this work will be applied to the resting-state fMRI data of a number of healthy subjects.

Communication Networks: Congestion control techniques aim to adjust the transmission rates of competing users in the Internet in such a way that the network resources are shared efficiently. Despite the progress in the analysis and synthesis of the Internet congestion control, almost all existing fluid models of congestion control assume that every link in the path of a flow observes the original source rate. To address this issue, a more accurate model is derived in this work for the behavior of the network under an arbitrary congestion controller, which takes into account of the effect of buffering (queueing) on data flows. Using this model, it is proved that the well-known Internet congestion control algorithms may no longer be stable for the common pricing schemes, unless a sufficient condition is satisfied. It is also shown that these algorithms are guaranteed to be stable if a new pricing mechanism is used.

Electrical Power Networks: Optimal power flow (OPF) has been one of the most studied problems for power systems since its introduction by Carpentier in 1962. This problem is concerned with finding an optimal operating point of a power network minimizing the total power generation cost subject to network and physical constraints. It is well known that OPF is computationally hard to solve due to the nonlinear interrelation among the optimization variables. The objective is to identify a large class of networks over which every OPF problem can be solved in polynomial time. To this end, a convex relaxation is proposed, which solves the OPF problem exactly for every radial network and every meshed network with a sufficient number of phase shifters, provided power over-delivery is allowed. The concept of “power over-delivery” is equivalent to relaxing the power balance equations to inequality constraints.

Flow Networks: In this part of the dissertation, the minimum-cost flow problem over an arbitrary flow network is considered. In this problem, each node is associated with some possibly unknown injection, each line has two unknown flows at its ends related to each other via a nonlinear function, and all injections and flows need to satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly non-convex due to its nonlinear equality constraints. Under the assumption of monotonicity and convexity of the flow and cost functions, a convex relaxation is proposed, which always finds the optimal injections. A primary application of this work is in the OPF problem. The results of this work on GNF prove that the relaxation on power balance equations (i.e., load over-delivery) is not needed in practice under a very mild angle assumption.

Generalized Weighted Graphs: Motivated by power optimizations, this part aims to find a global optimization technique for a nonlinear optimization defined over a generalized weighted graph. Every edge of this type of graph is associated with a weight set corresponding to the known parameters of the optimization (e.g., the coefficients). The motivation behind this problem is to investigate how the (hidden) structure of a given real/complex valued optimization makes the problem easy to solve, and indeed the generalized weighted graph is introduced to capture the structure of an optimization. Various sufficient conditions are derived, which relate the polynomial-time solvability of different classes of optimization problems to weak properties of the generalized weighted graph such as its topology and the sign definiteness of its weight sets. As an application, it is proved that a broad class of real and complex optimizations over power networks are polynomial-time solvable due to the passivity of transmission lines and transformers.

The global optimization of phase-incoherent signals

The problem of global optimization of M phase-incoherent signals in N complex dimensions is formulated. Then, by using the geometric approach of Landau and Slepian, conditions for optimality are established for N = 2 and the optimal signal sets are determined for M = 2, 3, 4, 6, and 12.

The method is the following: The signals are assumed to be equally probable and to have equal energy, and thus are represented by points ṡ_i, i = 1, 2, …, M, on the unit sphere S₁ in C^N. If W_ik is the halfspace determined by ṡ_i and ṡ_k and containing ṡ_i, i.e. W_ik = {ṙϵC^N:| ≥ | ˂ṙ, ṡ_k˃|}, then the Ʀ_i = ∩/k≠i W_ik, i = 1, 2, …, M, the maximum likelihood decision regions, partition S₁. For additive complex Gaussian noise ṅ and a received signal ṙ = ṡ_ie^jϴ + ṅ, where ϴ is uniformly distributed over [0, 2π], the probability of correct decoding is P_C = 1/π^N ∞/ʃ/0 r^2N-1e^-(r2+1)U(r)dr, where U(r) = 1/M M/Ʃ/i=1 Ʀ_i ʃ/∩ S₁ I₀(2r | ˂ṡ, ṡ_i˃|)dσ(ṡ), and r = ǁṙǁ.

For N = 2, it is proved that U(r) ≤ ʃ/C_α I₀(2r|˂ṡ, ṡ_i˃|)dσ(ṡ) – 2K/M. h(1/2K [Mσ(C_α)-σ(S₁)]), where C_α = {ṡϵS₁:|˂ṡ, ṡ_i˃| ≥ α}, K is the total number of boundaries of the net on S₁ determined by the decision regions, and h is the strictly increasing strictly convex function of σ(C_α∩W), (where W is a halfspace not containing ṡ_i), given by h = ʃ/C_α∩W I₀ (2r|˂ṡ, ṡ_i˃|)dσ(ṡ). Conditions for equality are established and these give rise to the globally optimal signal sets for M = 2, 3, 4, 6, and 12.

Stationary Eddies and Zonal Variations of the Global Hydrological Cycle in a Changing Climate

This thesis advances our physical understanding of the sensitivity of the hydrological cycle to global warming. Specifically, it focuses on changes in the longitudinal (zonal) variation of precipitation minus evaporation (P - E), which is predominantly controlled by planetary-scale stationary eddies. By studying idealized general circulation model (GCM) experiments with zonally varying boundary conditions, this thesis examines the mechanisms controlling the strength of stationary-eddy circulations and their role in the hydrological cycle. The overarching goal of this research is to understand the cause of changes in regional P - E with global warming. An understanding of such changes can be useful for impact studies focusing on water availability, ecosystem management, and flood risk.

Based on a moisture-budget analysis of ERA-Interim data, we establish an approximation for zonally anomalous P - E in terms of surface moisture content and stationary-eddy vertical motion in the lower troposphere. Part of the success of this approximation comes from our finding that transient-eddy moisture fluxes partially cancel the effect of stationary-eddy moisture advection, allowing divergent circulations to dominate the moisture budget. The lower-tropospheric vertical motion is related to horizontal motion in stationary eddies by Sverdrup and Ekman balance. These moisture- and vorticity-budget balances also hold in idealized and comprehensive GCM simulations across a range of climates.

By examining climate changes in the idealized and comprehensive GCM simulations, we are able to show the utility of the vertical motion P - E approximation for splitting changes in zonally anomalous P - E into thermodynamic and dynamic components. Shifts in divergent stationary-eddy circulations dominate changes in zonally anomalous P - E. This limits the local utility of the "wet gets wetter, dry gets drier” idea, where existing P - E patterns are amplified with warming by the increase in atmospheric moisture content, with atmospheric circulations held fixed. The increase in atmospheric moisture content manifests instead in an increase in the amplitude of the zonally anomalous hydrological cycle as measured by the zonal variance of P - E. However, dynamic changes, particularly the slowdown of divergent stationary-eddy circulations, limit the strengthening of the zonally anomalous hydrological cycle. In certain idealized cases, dynamic changes are even strong enough to reverse the tendency towards "wet gets wetter, dry gets drier” with warming.

Motivated by the importance of stationary-eddy vertical velocities in the moisture budget analysis, we examine controls on the amplitude of stationary eddies across a wide range of climates in an idealized GCM with simple topographic and ocean-heating zonal asymmetries. An analysis of the thermodynamic equation in the vicinity of topographic forcing reveals the importance of on-slope surface winds, the midlatitude isentropic slope, and latent heating in setting the amplitude of stationary waves. The response of stationary eddies to climate change is determined primarily by the strength of zonal surface winds hitting the mountain. The sensitivity of stationary-eddies to this surface forcing increases with climate change as the slope of midlatitude isentropes decreases. However, latent heating also plays an important role in damping the stationary-eddy response, and this damping becomes stronger with warming as the atmospheric moisture content increases. We find that the response of tropical overturning circulations forced by ocean heat-flux convergence is described by changes in the vertical structure of moist static energy and deep convection. This is used to derive simple scalings for the Walker circulation strength that capture the monotonic decrease with warming found in our idealized simulations.

Through the work of this thesis, the advances made in understanding the amplitude of stationary-waves in a changing climate can be directly applied to better understand and predict changes in the zonally anomalous hydrological cycle.