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.

Phase behavior of complex superprotonic solid acids

Superprotonic phase transitions and thermal behaviors of three complex solid acid systems are presented, namely Rb3H(SO4)2-RbHSO4 system, Rb3H(SeO4)2-Cs3H(SeO4)2 solid solution system, and Cs6(H2SO4)3(H1.5PO4)4. These material systems present a rich set of phase transition characteristics that set them apart from other, simpler solid acids. A.C. impedance spectroscopy, high-temperature X-ray powder diffraction, and thermal analysis, as well as other characterization techniques, were employed to investigate the phase behavior of these systems.

Rb3H(SO4)2 is an atypical member of the M3H(XO4)2 class of compounds (M = alkali metal or NH4+ and X = S or Se) in that a transition to a high-conductivity state involves disproportionation into two phases rather than a simple polymorphic transition [1]. In the present work, investigations of the Rb3H(SO4)2-RbHSO4 system have revealed the disproportionation products to be Rb2SO4 and the previously unknown compound Rb5H3(SO4)4. The new compound becomes stable at a temperature between 25 and 140 °C and is isostructural to a recently reported trigonal phase with space group P3̅m of Cs5H3(SO4)4 [2]. At 185 °C the compound undergoes an apparently polymorphic transformation with a heat of transition of 23.8 kJ/mol and a slight additional increase in conductivity.

The compounds Rb3H(SeO4)2 and Cs3H(SeO4)2, though not isomorphous at ambient temperatures, are quintessential examples of superprotonic materials. Both adopt monoclinic structures at ambient temperatures and ultimately transform to a trigonal (R3̅m) superprotonic structure at slightly elevated temperatures, 178 and 183 °C, respectively. The compounds are completely miscible above the superprotonic transition and show extensive solubility below it. Beyond a careful determination of the phase boundaries, we find a remarkable 40-fold increase in the superprotonic conductivity in intermediate compositions rich in Rb as compared to either end-member.

The compound Cs6(H2SO4)3(H1.5PO4)4 is unusual amongst solid acid compounds in that it has a complex cubic structure at ambient temperature and apparently transforms to a simpler cubic structure of the CsCl-type (isostructural with CsH2PO4) at its transition temperature of 100-120 °C [3]. Here it is found that, depending on the level of humidification, the superprotonic transition of this material is superimposed with a decomposition reaction, which involves both exsolution of (liquid) acid and loss of H2O. This reaction can be suppressed by application of sufficiently high humidity, in which case Cs6(H2SO4)3(H1.5PO4)4 undergoes a true superprotonic transition. It is proposed that, under conditions of low humidity, the decomposition/dehydration reaction transforms the compound to Cs6(H2-0.5xSO4)3(H1.5PO4)4-x, also of the CsCl structure type at the temperatures of interest, but with a smaller unit cell. With increasing temperature, the decomposition/dehydration proceeds to greater and greater extent and unit cell of the solid phase decreases. This is identified to be the source of the apparent negative thermal expansion behavior.

References

[1] L.A. Cowan, R.M. Morcos, N. Hatada, A. Navrotsky, S.M. Haile, Solid State Ionics 179 (2008) (9-10) 305.

[2] M. Sakashita, H. Fujihisa, K.I. Suzuki, S. Hayashi, K. Honda, Solid State Ionics 178 (2007) (21-22) 1262.

[3] C.R.I. Chisholm, Superprotonic Phase Transitions in Solid Acids: Parameters affecting the presence and stability of superprotonic transitions in the MHnXO4 family of compounds (X=S, Se, P, As; M=Li, Na, K, NH4, Rb, Cs), Materials Science, California Institute of Technology, Pasadena, California (2003).

Neural and computational representations of decision variables

These studies explore how, where, and when representations of variables critical to decision-making are represented in the brain. In order to produce a decision, humans must first determine the relevant stimuli, actions, and possible outcomes before applying an algorithm that will select an action from those available. When choosing amongst alternative stimuli, the framework of value-based decision-making proposes that values are assigned to the stimuli and that these values are then compared in an abstract “value space” in order to produce a decision. Despite much progress, in particular regarding the pinpointing of ventromedial prefrontal cortex (vmPFC) as a region that encodes the value, many basic questions remain. In Chapter 2, I show that distributed BOLD signaling in vmPFC represents the value of stimuli under consideration in a manner that is independent of the type of stimulus it is. Thus the open question of whether value is represented in abstraction, a key tenet of value-based decision-making, is confirmed. However, I also show that stimulus-dependent value representations are also present in the brain during decision-making and suggest a potential neural pathway for stimulus-to-value transformations that integrates these two results.

More broadly speaking, there is both neural and behavioral evidence that two distinct control systems are at work during action selection. These two systems compose the “goal-directed system”, which selects actions based on an internal model of the environment, and the “habitual” system, which generates responses based on antecedent stimuli only. Computational characterizations of these two systems imply that they have different informational requirements in terms of input stimuli, actions, and possible outcomes. Associative learning theory predicts that the habitual system should utilize stimulus and action information only, while goal-directed behavior requires that outcomes as well as stimuli and actions be processed. In Chapter 3, I test whether areas of the brain hypothesized to be involved in habitual versus goal-directed control represent the corresponding theorized variables.

The question of whether one or both of these neural systems drives Pavlovian conditioning is less well-studied. Chapter 4 describes an experiment in which subjects were scanned while engaged in a Pavlovian task with a simple non-trivial structure. After comparing a variety of model-based and model-free learning algorithms (thought to underpin goal-directed and habitual decision-making, respectively), it was found that subjects’ reaction times were better explained by a model-based system. In addition, neural signaling of precision, a variable based on a representation of a world model, was found in the amygdala. These data indicate that the influence of model-based representations of the environment can extend even to the most basic learning processes.

Knowledge of the state of hidden variables in an environment is required for optimal inference regarding the abstract decision structure of a given environment and therefore can be crucial to decision-making in a wide range of situations. Inferring the state of an abstract variable requires the generation and manipulation of an internal representation of beliefs over the values of the hidden variable. In Chapter 5, I describe behavioral and neural results regarding the learning strategies employed by human subjects in a hierarchical state-estimation task. In particular, a comprehensive model fit and comparison process pointed to the use of "belief thresholding". This implies that subjects tended to eliminate low-probability hypotheses regarding the state of the environment from their internal model and ceased to update the corresponding variables. Thus, in concert with incremental Bayesian learning, humans explicitly manipulate their internal model of the generative process during hierarchical inference consistent with a serial hypothesis testing strategy.

Extension theorems for functions of vanishing mean oscillation

A locally integrable function is said to be of vanishing mean oscillation (VMO) if its mean oscillation over cubes in R^d converges to zero with the volume of the cubes. We establish necessary and sufficient conditions for a locally integrable function defined on a bounded measurable set of positive measure to be the restriction to that set of a VMO function.

We consider the similar extension problem pertaining to BMO(ρ) functions; that is, those VMO functions whose mean oscillation over any cube is O(ρ(l(Q))) where l(Q) is the length of Q and ρ is a positive, non-decreasing function with ρ(0⁺) = 0.

We apply these results to obtain sufficient conditions for a Blaschke sequence to be the zeros of an analytic BMO(ρ) function on the unit disc.