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).

Random propagation in complex systems : nonlinear matrix recursions and epidemic spread

This dissertation studies long-term behavior of random Riccati recursions and mathematical epidemic model. Riccati recursions are derived from Kalman filtering. The error covariance matrix of Kalman filtering satisfies Riccati recursions. Convergence condition of time-invariant Riccati recursions are well-studied by researchers. We focus on time-varying case, and assume that regressor matrix is random and identical and independently distributed according to given distribution whose probability distribution function is continuous, supported on whole space, and decaying faster than any polynomial. We study the geometric convergence of the probability distribution. We also study the global dynamics of the epidemic spread over complex networks for various models. For instance, in the discrete-time Markov chain model, each node is either healthy or infected at any given time. In this setting, the number of the state increases exponentially as the size of the network increases. The Markov chain has a unique stationary distribution where all the nodes are healthy with probability 1. Since the probability distribution of Markov chain defined on finite state converges to the stationary distribution, this Markov chain model concludes that epidemic disease dies out after long enough time. To analyze the Markov chain model, we study nonlinear epidemic model whose state at any given time is the vector obtained from the marginal probability of infection of each node in the network at that time. Convergence to the origin in the epidemic map implies the extinction of epidemics. The nonlinear model is upper-bounded by linearizing the model at the origin. As a result, the origin is the globally stable unique fixed point of the nonlinear model if the linear upper bound is stable. The nonlinear model has a second fixed point when the linear upper bound is unstable. We work on stability analysis of the second fixed point for both discrete-time and continuous-time models. Returning back to the Markov chain model, we claim that the stability of linear upper bound for nonlinear model is strongly related with the extinction time of the Markov chain. We show that stable linear upper bound is sufficient condition of fast extinction and the probability of survival is bounded by nonlinear epidemic map.

Terahertz time domain spectroscopy of amino acids and sugars

A time-domain spectrometer for use in the terahertz (THz) spectral range was designed and constructed. Due to there being few existing methods of generating and detecting THz radiation, the spectrometer is expected to have vast applications to solid, liquid, and gas phase samples. In particular, knowledge of complex organic chemistry and chemical abundances in the interstellar medium (ISM) can be obtained when compared to astronomical data. The THz spectral region is of particular interest due to reduced line density when compared to the millimeter wave spectrum, the existence of high resolution observatories, and potentially strong transitions resulting from the lowest-lying vibrational modes of large molecules.

The heart of the THz time-domain spectrometer (THz-TDS) is the ultrafast laser. Due to the femtosecond duration of ultrafast laser pulses and an energy-time uncertainty relationship, the pulses typically have a several-THz bandwidth. By various means of optical rectification, the optical pulse carrier envelope shape, i.e. intensity-time profile, can be transferred to the phase of the resulting THz pulse. As a consequence, optical pump-THz probe spectroscopy is readily achieved, as was demonstrated in studies of dye-sensitized TiO₂, as discussed in chapter 4. Detection of the terahertz radiation is commonly based on electro-optic sampling and provides full phase information. This allows for accurate determination of both the real and imaginary index of refraction, the so-called optical constants, without additional analysis. A suite of amino acids and sugars, all of which have been found in meteorites, were studied in crystalline form embedded in a polyethylene matrix. As the temperature was varied between 10 and 310 K, various strong vibrational modes were found to shift in spectral intensity and frequency. Such modes can be attributed to intramolecular, intermolecular, or phonon modes, or to some combination of the three.