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.

Catalytic conversion of nitrogen to ammonia by an iron model complex

Threefold symmetric Fe phosphine complexes have been used to model the structural and functional aspects of biological N₂ fixation by nitrogenases. Low-valent bridging Fe-S-Fe complexes in the formal oxidation states Fe(II)Fe(II), Fe(II)/Fe(I), and Fe(I)/Fe(I) have been synthesized which display rich spectroscopic and magnetic behavior. A series of cationic tris-phosphine borane (TPB) ligated Fe complexes have been synthesized and been shown to bind a variety of nitrogenous ligands including N₂H₄, NH₃, and NH₂-. These complexes are all high spin S = 3/2 and display EPR and magnetic characteristics typical of this spin state. Furthermore, a sequential protonation and reduction sequence of a terminal amide results in loss of NH₃ and uptake of N₂. These stoichiometric transformations represent the final steps in potential N₂ fixation schemes.

Treatment of an anionic FeN₂ complex with excess acid also results in the formation of some NH₃, suggesting the possibility of a catalytic cycle for the conversion of N₂ to NH₃ mediated by Fe. Indeed, use of excess acid and reductant results in the formation of seven equivalents of NH₃ per Fe center, demonstrating Fe mediated catalytic N₂ fixation with acids and protons for the first time. Numerous control experiments indicate that this catalysis is likely being mediated by a molecular species.

A number of other phosphine ligated Fe complexes have also been tested for catalysis and suggest that a hemi-labile Fe-B interaction may be critical for catalysis. Additionally, various conditions for the catalysis have been investigated. These studies further support the assignment of a molecular species and delineate some of the conditions required for catalysis.

Finally, combined spectroscopic studies have been performed on a putative intermediate for catalysis. These studies converge on an assignment of this new species as a hydrazido(2-) complex. Such species have been known on group 6 metals for some time, but this represents the first characterization of this ligand on Fe. Further spectroscopic studies suggest that this species is present in catalytic mixtures, which suggests that the first steps of a distal mechanism for N₂ fixation are feasible in this system.

Intramolecular conflict : conformation and self-assembly of architecturally complex macromolecules in solution

The solution behavior of linear polymer chains is well understood, having been the subject of intense study throughout the previous century. As plastics have become ubiquitous in everyday life, polymer science has grown into a major field of study. The conformation of a polymer in solution depends on the molecular architecture and its interactions with the surroundings. Developments in synthetic techniques have led to the creation of precision-tailored polymeric materials with varied topologies and functionalities. In order to design materials with the desired properties, it is imperative to understand the relationships between polymer architecture and their conformation and behavior. To meet that need, this thesis investigates the conformation and self-assembly of three architecturally complex macromolecular systems with rich and varied behaviors driven by the resolution of intramolecular conflicts. First we describe the development of a robust and facile synthetic approach to reproducible bottlebrush polymers (Chapter 2). The method was used to produce homologous series of bottlebrush polymers with polynorbornene backbones, which revealed the effect of side-chain and backbone length on the overall conformation in both good and theta solvent conditions (Chapter 3). The side-chain conformation was obtained from a series of SANS experiments and determined to be indistinguishable from the behavior of free linear polymer chains. Using deuterium-labeled bottlebrushes, we were able for the first time to directly observe the backbone conformation of a bottlebrush polymer which showed self-avoiding walk behavior. Secondly, a series of SANS experiments was conducted on a homologous series of Side Group Liquid Crystalline Polymers (SGLCPs) in a perdeuterated small molecule liquid crystal (5CB). Monodomain, aligned, dilute samples of SGLCP-b-PS block copolymers were seen to self-assemble into complex micellar structures with mutually orthogonally oriented anisotropies at different length scales (Chapter 4). Finally, we present the results from the first scattering experiments on a set of fuel-soluble, associating telechelic polymers. We observed the formation of supramolecular aggregates in dilute (≤0.5wt%) solutions of telechelic polymers and determined that the choice of solvent has a significant effect on the strength of association and the size of the supramolecules (Chapter 5). A method was developed for the direct estimation of supramolecular aggregation number from SANS data. The insight into structure-property relationships obtained from this work will enable the more targeted development of these molecular architectures for their respective applications.

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.