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.

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.

The Mechanical Genome in Regulation and Infection

Biological information storage and retrieval is a dynamic process that requires the genome to undergo dramatic structural rearrangements. Recent advances in single-molecule techniques have allowed precise quantification of the nano-mechanical properties of DNA [1, 2], and direct in vivo observation of molecules in action [3]. In this work, we will examine elasticity in protein-mediated DNA looping, whose structural rearrangement is essential for transcriptional regulation in both prokaryotes and eukaryotes. We will look at hydrodynamics in the process of viral DNA ejection, which mediates information transfer and exchange and has prominent implications in evolution. As in the case of Kepler's laws of planetary motion leading to Newton's gravitational theory, and the allometric scaling laws in biology revealing the organizing principles of complex networks [4], experimental data collapse in these biological phenomena has guided much of our studies and urged us to find the underlying physical principles.

Distributed optimization in power networks and general multi-agent systems

The dissertation studies the general area of complex networked systems that consist of interconnected and active heterogeneous components and usually operate in uncertain environments and with incomplete information. Problems associated with those systems are typically large-scale and computationally intractable, yet they are also very well-structured and have features that can be exploited by appropriate modeling and computational methods. The goal of this thesis is to develop foundational theories and tools to exploit those structures that can lead to computationally-efficient and distributed solutions, and apply them to improve systems operations and architecture.

Specifically, the thesis focuses on two concrete areas. The first one is to design distributed rules to manage distributed energy resources in the power network. The power network is undergoing a fundamental transformation. The future smart grid, especially on the distribution system, will be a large-scale network of distributed energy resources (DERs), each introducing random and rapid fluctuations in power supply, demand, voltage and frequency. These DERs provide a tremendous opportunity for sustainability, efficiency, and power reliability. However, there are daunting technical challenges in managing these DERs and optimizing their operation. The focus of this dissertation is to develop scalable, distributed, and real-time control and optimization to achieve system-wide efficiency, reliability, and robustness for the future power grid. In particular, we will present how to explore the power network structure to design efficient and distributed market and algorithms for the energy management. We will also show how to connect the algorithms with physical dynamics and existing control mechanisms for real-time control in power networks.

The second focus is to develop distributed optimization rules for general multi-agent engineering systems. A central goal in multiagent systems is to design local control laws for the individual agents to ensure that the emergent global behavior is desirable with respect to the given system level objective. Ideally, a system designer seeks to satisfy this goal while conditioning each agent’s control on the least amount of information possible. Our work focused on achieving this goal using the framework of game theory. In particular, we derived a systematic methodology for designing local agent objective functions that guarantees (i) an equivalence between the resulting game-theoretic equilibria and the system level design objective and (ii) that the resulting game possesses an inherent structure that can be exploited for distributed learning, e.g., potential games. The control design can then be completed by applying any distributed learning algorithm that guarantees convergence to the game-theoretic equilibrium. One main advantage of this game theoretic approach is that it provides a hierarchical decomposition between the decomposition of the systemic objective (game design) and the specific local decision rules (distributed learning algorithms). This decomposition provides the system designer with tremendous flexibility to meet the design objectives and constraints inherent in a broad class of multiagent systems. Furthermore, in many settings the resulting controllers will be inherently robust to a host of uncertainties including asynchronous clock rates, delays in information, and component failures.

Geological evolution of two crustal scale shear zones. Part I. The Rand thrust complex, northwestern Mojave Desert, California. Part II. The Magdalena metamorphic core complex, north central Sonora, Mexico

The geology and structure of two crustal scale shear zones were studied to understand the partitioning of strain within intracontinental orogenic belts. Movement histories and regional tectonic implications are deduced from observational data. The two widely separated study areas bear the imprint of intense Late Mesozoic through Middle Cenozoic tectonic activity. A regional transition from Late Cretaceous-Early Tertiary plutonism, metamorphism, and shortening strain to Middle Tertiary extension and magmatism is preserved in each area, with contrasting environments and mechanisms. Compressional phases of this tectonic history are better displayed in the Rand Mountains, whereas younger extensional structures dominate rock fabrics in the Magdalena area.

In the northwestern Mojave desert, the Rand Thrust Complex reveals a stack of four distinctive tectonic plates offset along the Garlock Fault. The lowermost plate, Rand Schist, is composed of greenschist facies metagraywacke, metachert, and metabasalt. Rand Schist is structurally overlain by Johannesburg Gneiss (= garnet-amphibolite grade orthogneisses, marbles and quartzites), which in turn is overlain by a Late Cretaceous hornblende-biotite granodiorite. Biotite granite forms the fourth and highest plate. Initial assembly of the tectonic stack involved a Late Cretaceous? south or southwest vergent overthrusting event in which Johannesburg Gneiss was imbricated and attenuated between Rand Schist and hornblende-biotite granodiorite. Thrusting postdated metamorphism and deformation of the lower two plates in separate environments. A post-kinematic stock, the Late Cretaceous Randsburg Granodiorite, intrudes deep levels of the complex and contains xenoliths of both Rand Schist and mylonitized Johannesburg? gneiss. Minimum shortening implied by the map patterns is 20 kilometers.

Some low angle faults of the Rand Thrust Complex formed or were reactivated between Late Cretaceous and Early Miocene time. South-southwest directed mylonites derived from Johannesburg Gneiss are commonly overprinted by less penetrative north-northeast vergent structures. Available kinematic information at shallower structural levels indicates that late disturbance(s) culminated in northward transport of the uppermost plate. Persistence of brittle fabrics along certain structural horizons suggests a possible association of late movement(s) with regionally known detachment faults. The four plates were juxtaposed and significant intraplate movements had ceased prior to Early Miocene emplacement of rhyolite porphyry dikes.

In the Magdalena region of north central Sonora, components of a pre-Middle Cretaceous stratigraphy are used as strain markers in tracking the evolution of a long lived orogenic belt. Important elements of the tectonic history include: (1) Compression during the Late Cretaceous and Early Tertiary, accompanied by plutonism, metamorphism, and ductile strain at depth, and thrust driven? syntectonic sedimentation at the surface. (2) Middle Tertiary transition to crustal extension, initially recorded by intrusion of leucogranites, inflation of the previously shortened middle and upper crustal section, and surface volcanism. (3) Gravity induced development of a normal sense ductile shear zone at mid crustal levels, with eventual detachment and southwestward displacement of the upper crustal stratigraphy by Early Miocene time.

Elucidation of the metamorphic core complex evolution just described was facilitated by fortuitous preservation of a unique assemblage of rocks and structures. The "type" stratigraphy utilized for regional correlation and strain analysis includes a Jurassic volcanic arc assemblage overlain by an Upper Jurassic-Lower Cretaceous quartz pebble conglomerate, in turn overlain by marine strata with fossiliferous Aptian-Albian limestones. The Jurassic strata, comprised of (a) rhyolite porphyries interstratified with quartz arenites, (b) rhyolite cobble conglomerate, and (c) intrusive granite porphyries, are known to rest on Precambrian basement north and east of the study area. The quartz pebble conglomerate is correlated with the Glance Conglomerate of southeastern Arizona and northeastern Sonora. The marine sequence represents part of an isolated arm? of the Bisbee Basin.

Crosscutting structural relationships between the pre-Middle Cretaceous supracrustal section, younger plutons, and deformational fabrics allow the tectonic sequence to be determined. Earliest phases of a Late Cretaceous-Early Tertiary orogeny are marked by emplacement of the 78 ± 3 Ma Guacomea Granodiorite (U/Pb zircon, Anderson et al., 1980) as a sill into deep levels of the layered Jurassic series. Subsequent regional metamorphism and ductile strain is recorded by a penetrative schistosity and lineation, and east-west trending folds. These fabrics are intruded by post-kinematic Early Tertiary? two mica granites. At shallower crustal levels, the orogeny is represented by north directed thrust faulting, formation of a large intermontane basin, and development of a pronounced unconformity. A second important phase of ductile strain followed Middle Tertiary? emplacement of leucogranites as sills and northwest trending dikes into intermediate levels of the deformed section (surficial volcanism was also active during this transitional period to regional extension). Gravitational instabilities resulting from crustal swelling via intrusion and thermal expansion led to development of a ductile shear zone within the stratigraphic horizon occupied by a laterally extensive leucogranite sill. With continued extension, upper crustal brittle normal faults (detachment faults) enhanced the uplift and tectonic denudation of this mylonite zone, ultimately resulting in southwestward displacement of the upper crustal stratigraphy.

Strains associated with the two ductile deformation events have been successfully partitioned through a multifaceted analysis. R_f/Ø measurements on various markers from the "type" stratigraphy allow a gradient representing cumulative strain since Middle Cretaceous time to be determined. From this gradient, noncoaxial strains accrued since emplacement of the leucogranites may be removed. Irrotational components of the postleucogranite strain are measured from quartz grain shapes in deformed granites; rotational components (shear strains) are determined from S-C fabrics and from restoration of rotated dike and vein networks. Structural observations and strain data are compatable with a deformation path of: (1) coaxial strain (pure shear?), followed by (2) injection of leucogranites as dikes (perpendicular to the minimum principle stress) and sills (parallel to the minimum principle stress), then (3) southwest directed simple shear. Modeling the late strain gradient as a simple shear zone permits a minimum displacement of 10 kilometers on the Magdalena mylonite zone/detachment fault system. Removal of the Middle Tertiary noncoaxial strains yields a residual (or pre-existing) strain gradient representative of the Late Cretaceous-Early Tertiary deformation. Several partially destrained cross sections, restored to the time of leucogranite emplacement, illustrate the idea that the upper plate of the core complex bas been detached from a region of significant topographic relief. 50% to 100% bulk extension across a 50 kilometer wide corridor is demonstrated.

Late Cenozoic tectonics of the Magdalena region are dominated by Basin and Range style faulting. Northeast and north-northwest trending high angle normal faults have interacted to extend the crust in an east-west direction. Net extension for this period is minor (10% to 15%) in comparison to the Middle Tertiary detachment related extensional episode.

Selective data gathering in community sensor networks

Smartphones and other powerful sensor-equipped consumer devices make it possible to sense the physical world at an unprecedented scale. Nearly 2 million Android and iOS devices are activated every day, each carrying numerous sensors and a high-speed internet connection. Whereas traditional sensor networks have typically deployed a fixed number of devices to sense a particular phenomena, community networks can grow as additional participants choose to install apps and join the network. In principle, this allows networks of thousands or millions of sensors to be created quickly and at low cost. However, making reliable inferences about the world using so many community sensors involves several challenges, including scalability, data quality, mobility, and user privacy.

This thesis focuses on how learning at both the sensor- and network-level can provide scalable techniques for data collection and event detection. First, this thesis considers the abstract problem of distributed algorithms for data collection, and proposes a distributed, online approach to selecting which set of sensors should be queried. In addition to providing theoretical guarantees for submodular objective functions, the approach is also compatible with local rules or heuristics for detecting and transmitting potentially valuable observations. Next, the thesis presents a decentralized algorithm for spatial event detection, and describes its use detecting strong earthquakes within the Caltech Community Seismic Network. Despite the fact that strong earthquakes are rare and complex events, and that community sensors can be very noisy, our decentralized anomaly detection approach obtains theoretical guarantees for event detection performance while simultaneously limiting the rate of false alarms.

Programming chemical kinetics: engineering dynamic reaction networks with DNA strand displacement

Over the last century, the silicon revolution has enabled us to build faster, smaller and more sophisticated computers. Today, these computers control phones, cars, satellites, assembly lines, and other electromechanical devices. Just as electrical wiring controls electromechanical devices, living organisms employ "chemical wiring" to make decisions about their environment and control physical processes. Currently, the big difference between these two substrates is that while we have the abstractions, design principles, verification and fabrication techniques in place for programming with silicon, we have no comparable understanding or expertise for programming chemistry.

In this thesis we take a small step towards the goal of learning how to systematically engineer prescribed non-equilibrium dynamical behaviors in chemical systems. We use the formalism of chemical reaction networks (CRNs), combined with mass-action kinetics, as our programming language for specifying dynamical behaviors. Leveraging the tools of nucleic acid nanotechnology (introduced in Chapter 1), we employ synthetic DNA molecules as our molecular architecture and toehold-mediated DNA strand displacement as our reaction primitive.

Abstraction, modular design and systematic fabrication can work only with well-understood and quantitatively characterized tools. Therefore, we embark on a detailed study of the "device physics" of DNA strand displacement (Chapter 2). We present a unified view of strand displacement biophysics and kinetics by studying the process at multiple levels of detail, using an intuitive model of a random walk on a 1-dimensional energy landscape, a secondary structure kinetics model with single base-pair steps, and a coarse-grained molecular model that incorporates three-dimensional geometric and steric effects. Further, we experimentally investigate the thermodynamics of three-way branch migration. Our findings are consistent with previously measured or inferred rates for hybridization, fraying, and branch migration, and provide a biophysical explanation of strand displacement kinetics. Our work paves the way for accurate modeling of strand displacement cascades, which would facilitate the simulation and construction of more complex molecular systems.

In Chapters 3 and 4, we identify and overcome the crucial experimental challenges involved in using our general DNA-based technology for engineering dynamical behaviors in the test tube. In this process, we identify important design rules that inform our choice of molecular motifs and our algorithms for designing and verifying DNA sequences for our molecular implementation. We also develop flexible molecular strategies for "tuning" our reaction rates and stoichiometries in order to compensate for unavoidable non-idealities in the molecular implementation, such as imperfectly synthesized molecules and spurious "leak" pathways that compete with desired pathways.

We successfully implement three distinct autocatalytic reactions, which we then combine into a de novo chemical oscillator. Unlike biological networks, which use sophisticated evolved molecules (like proteins) to realize such behavior, our test tube realization is the first to demonstrate that Watson-Crick base pairing interactions alone suffice for oscillatory dynamics. Since our design pipeline is general and applicable to any CRN, our experimental demonstration of a de novo chemical oscillator could enable the systematic construction of CRNs with other dynamic behaviors.

Functional, clustered, feedforward, and mesoscale brain networks

The brain is a network spanning multiple scales from subcellular to macroscopic. In this thesis I present four projects studying brain networks at different levels of abstraction. The first involves determining a functional connectivity network based on neural spike trains and using a graph theoretical method to cluster groups of neurons into putative cell assemblies. In the second project I model neural networks at a microscopic level. Using diferent clustered wiring schemes, I show that almost identical spatiotemporal activity patterns can be observed, demonstrating that there is a broad neuro-architectural basis to attain structured spatiotemporal dynamics. Remarkably, irrespective of the precise topological mechanism, this behavior can be predicted by examining the spectral properties of the synaptic weight matrix. The third project introduces, via two circuit architectures, a new paradigm for feedforward processing in which inhibitory neurons have the complex and pivotal role in governing information flow in cortical network models. Finally, I analyze axonal projections in sleep deprived mice using data collected as part of the Allen Institute's Mesoscopic Connectivity Atlas. After normalizing for experimental variability, the results indicate there is no single explanatory difference in the mesoscale network between control and sleep deprived mice. Using machine learning techniques, however, animal classification could be done at levels significantly above chance. This reveals that intricate changes in connectivity do occur due to chronic sleep deprivation.