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.

Design, specification, and synthesis of aircraft electric power systems control logic

Cyber-physical systems integrate computation, networking, and physical processes. Substantial research challenges exist in the design and verification of such large-scale, distributed sensing, ac- tuation, and control systems. Rapidly improving technology and recent advances in control theory, networked systems, and computer science give us the opportunity to drastically improve our approach to integrated flow of information and cooperative behavior. Current systems rely on text-based spec- ifications and manual design. Using new technology advances, we can create easier, more efficient, and cheaper ways of developing these control systems. This thesis will focus on design considera- tions for system topologies, ways to formally and automatically specify requirements, and methods to synthesize reactive control protocols, all within the context of an aircraft electric power system as a representative application area.

This thesis consists of three complementary parts: synthesis, specification, and design. The first section focuses on the synthesis of central and distributed reactive controllers for an aircraft elec- tric power system. This approach incorporates methodologies from computer science and control. The resulting controllers are correct by construction with respect to system requirements, which are formulated using the specification language of linear temporal logic (LTL). The second section addresses how to formally specify requirements and introduces a domain-specific language for electric power systems. A software tool automatically converts high-level requirements into LTL and synthesizes a controller.

The final sections focus on design space exploration. A design methodology is proposed that uses mixed-integer linear programming to obtain candidate topologies, which are then used to synthesize controllers. The discrete-time control logic is then verified in real-time by two methods: hardware and simulation. Finally, the problem of partial observability and dynamic state estimation is ex- plored. Given a set placement of sensors on an electric power system, measurements from these sensors can be used in conjunction with control logic to infer the state of the system.

Robust near-threshold QDI circuit analysis and design

The two most important digital-system design goals today are to reduce power consumption and to increase reliability. Reductions in power consumption improve battery life in the mobile space and reductions in energy lower operating costs in the datacenter. Increased robustness and reliability shorten down time, improve yield, and are invaluable in the context of safety-critical systems. While optimizing towards these two goals is important at all design levels, optimizations at the circuit level have the furthest reaching effects; they apply to all digital systems. This dissertation presents a study of robust minimum-energy digital circuit design and analysis. It introduces new device models, metrics, and methods of calculation—all necessary first steps towards building better systems—and demonstrates how to apply these techniques. It analyzes a fabricated chip (a full-custom QDI microcontroller designed at Caltech and taped-out in 40-nm silicon) by calculating the minimum energy operating point and quantifying the chip’s robustness in the face of both timing and functional failures.

Spectral analysis and control to obtain sub-5 fs pulses by femtosecond filamentation

A spectral-filter method is numerically demonstrated to obtain sub-5 fs pulses by using femtosecond filamentation in fused silica. Instead of employing spectral phase compensation, by properly employing a high-pass filter to select the broadened high-frequency spectra that are located almost in phase in the tailing edge of the self-compressed pulses owing to self-steepening, as short as single-cycle pulses can be obtained. For instance, for an input pulse with a duration of 50 fs and energy 2.2 mu J, the minimum pulse duration can reach to similar to 4 fs (about 1.5 cycles) by applying a proper spectral filter. (C) 2008 Optical Society of America

Compression of Chinese document images based on morphologic analysis and pattern matching

We propose a highly efficient content-lossless compression scheme for Chinese document images. The scheme combines morphologic analysis with pattern matching to cluster patterns. In order to achieve the error maps with minimal error numbers, the morphologic analysis is applied to decomposing and recomposing the Chinese character patterns. In the pattern matching, the criteria are adapted to the characteristics of Chinese characters. Since small-size components sometimes can be inserted into the blank spaces of large-size components, we can achieve small-size pattern library images. Arithmetic coding is applied to the final compression. Our method achieves much better compression performance than most alternative methods, and assures content-lossless reconstruction. (c) 2006 Society of Photo-Optical Instrumentation Engineers.

Analysis and Use of Information and Communication Tools in Economics of Climate Change

16 p.

On the Role of Delays in Biological Systems : Analysis and Design

This work quantifies the nature of delays in genetic regulatory networks and their effect on system dynamics. It is known that a time lag can emerge from a sequence of biochemical reactions. Applying this modeling framework to the protein production processes, delay distributions are derived in a stochastic (probability density function) and deterministic setting (impulse function), whilst being shown to be equivalent under different assumptions. The dependence of the distribution properties on rate constants, gene length, and time-varying temperatures is investigated. Overall, the distribution of the delay in the context of protein production processes is shown to be highly dependent on the size of the genes and mRNA strands as well as the reaction rates. Results suggest longer genes have delay distributions with a smaller relative variance, and hence, less uncertainty in the completion times, however, they lead to larger delays. On the other hand large uncertainties may actually play a positive role, as broader distributions can lead to larger stability regions when this formalization of the protein production delays is incorporated into a feedback system.

Furthermore, evidence suggests that delays may play a role as an explicit design into existing controlling mechanisms. Accordingly, the reccurring dual-feedback motif is also investigated with delays incorporated into the feedback channels. The dual-delayed feedback is shown to have stabilizing effects through a control theoretic approach. Lastly, a distributed delay based controller design method is proposed as a potential design tool. In a preliminary study, the dual-delayed feedback system re-emerges as an effective controller design.

Numerical modeling of optical levitation and trapping of the "stuck" particles with a pulsed optical tweezers

We present the theoretical analysis and the numerical modeling of optical levitation and trapping of the stuck particles with a pulsed optical tweezers. In our model, a pulsed laser was used to generate a large gradient force within a short duration that overcame the adhesive interaction between the stuck particles and the surface; and then a low power continuous - wave (cw) laser was used to capture the levitated particle. We describe the gradient force generated by the pulsed optical tweezers and model the binding interaction between the stuck beads and glass surface by the dominative van der Waals force with a randomly distributed binding strength. We numerically calculate the single pulse levitation efficiency for polystyrene beads as the function of the pulse energy, the axial displacement from the surface to the pulsed laser focus and the pulse duration. The result of our numerical modeling is qualitatively consistent with the experimental result. (C) 2005 Optical Society of America.

Development of Microfluidic Devices with the Use of Nanotechnology to Aid in the Analysis of Biological Systems Including Membrane Protein Separation, Single Cell Analysis, and Genetic Markers

Computation technology has dramatically changed the world around us; you can hardly find an area where cell phones have not saturated the market, yet there is a significant lack of breakthroughs in the development to integrate the computer with biological environments. This is largely the result of the incompatibility of the materials used in both environments; biological environments and experiments tend to need aqueous environments. To help aid in these development chemists, engineers, physicists and biologists have begun to develop microfluidics to help bridge this divide. Unfortunately, the microfluidic devices required large external support equipment to run the device. This thesis presents a series of several microfluidic methods that can help integrate engineering and biology by exploiting nanotechnology to help push the field of microfluidics back to its intended purpose, small integrated biological and electrical devices. I demonstrate this goal by developing different methods and devices to (1) separate membrane bound proteins with the use of microfluidics, (2) use optical technology to make fiber optic cables into protein sensors, (3) generate new fluidic devices using semiconductor material to manipulate single cells, and (4) develop a new genetic microfluidic based diagnostic assay that works with current PCR methodology to provide faster and cheaper results. All of these methods and systems can be used as components to build a self-contained biomedical device.

Polarization analysis and experimental implementation of PLZT electro-optical switch using fiber Sagnac interferometers

The polarization characteristics of electro-optical (EO) switches using fiber Sagnac interferometer (FSI) structures are theoretically investigated. Analytical solutions of output fields are presented when the twists and birefringence in a Sagnac loop are considered. Numerical calculations show that the twists of fiber, the orientation of the inserted phase retarder, and the splitting ratio of the coupler will influence both the output intensity and the output polarization properties of the proposed switch. A polarization-independent EO switch based on a Sagnac interferometer and a PUT bar was experimentally implemented, which showed good coincidence with the analytical results. The experiment showed a switch with 22 dB extinction ratio and less than 31.1 ns switching time. (c) 2006 Optical Society of America.

The Design and Synthesis of Transition Metal Complexes Supported by Non-innocent Ligand Scaffolds for Small Molecule Activation

This dissertation focuses on the incorporation of non-innocent or multifunctional moieties into different ligand scaffolds to support one or multiple metal centers in close proximity. Chapter 2 focuses on the initial efforts to synthesize hetero- or homometallic tri- or dinuclear metal carbonyl complexes supported by para-terphenyl diphosphine ligands. A series of [M₂M’(CO)₄]-type clusters (M = Ni, Pd; M’ = Fe, Co) could be accessed and used to relate the metal composition to the properties of the complexes. During these studies it was also found that non-innocent behavior was observed in dinuclear Fe complexes that result from changes in oxidation state of the cluster. These studies led to efforts to rationally incorporate central arene moieties capable managing both protons and electrons during small molecule activation.

Chapter 3 discusses the synthesis of metal complexes supported by a novel para-terphenyl diphosphine ligand containing a non-innocent 1,4-hydroquinone moiety as the central arene. A Pd⁰-hydroquinone complex was found to mediate the activation of a variety of small molecules to form the corresponding Pd⁰-quinone complexes in a formal two proton ⁄ two electron transformation. Mechanistic investigations of dioxygen activation revealed a metal-first activation process followed by subsequent proton and electron transfer from the ligand. These studies revealed the capacity of the central arene substituent to serve as a reservoir for a formal equivalent of dihydrogen, although the stability of the M-quinone compounds prevented access to the PdII-quinone oxidation state, thus hindering of small molecule transformations requiring more than two electrons per equivalent of metal complex.

Chapter 4 discusses the synthesis of metal complexes supported by a ligand containing a 3,5-substituted pyridine moiety as the linker separating the phenylene phosphine donors. Nickel and palladium complexes supported by this ligand were found to tolerate a wide variety of pyridine nitrogen-coordinated electrophiles which were found to alter central pyridine electronics, and therefore metal-pyridine π-system interactions, substantially. Furthermore, nickel complexes supported by this ligand were found to activate H-B and H-Si bonds and formally hydroborate and hydrosilylate the central pyridine ring. These systems highlight the potential use of pyridine π-system-coordinated metal complexes to reversibly store reducing equivalents within the ligand framework in a manner akin to the previously discussed 1,4-hydroquinone diphosphine ligand scaffold.

Chapter 5 departs from the phosphine-based chemistry and instead focuses on the incorporation of hydrogen bonding networks into the secondary coordination sphere of [Fe₄(μ₄-O)]-type clusters supported by various pyrazolate ligands. The aim of this project is to stabilize reactive oxygenic species, such as oxos, to study their spectroscopy and reactivity in the context of complicated multimetallic clusters. Herein is reported this synthesis and electrochemical and Mössbauer characterization of a series of chloride clusters have been synthesized using parent pyrazolate and a 3-aminophenyl substituted pyrazolate ligand. Efforts to rationally access hydroxo and oxo clusters from these chloride precursors represents ongoing work that will continue in the group.

Appendix A discusses attempts to access [Fe₃Ni]-type clusters as models of the enzymatic active site of [NiFe] carbon monoxide dehydrogenase. Efforts to construct tetranuclear clusters with an interstitial sulfide proved unsuccessful, although a (μ₃-S) ligand could be installed through non-oxidative routes into triiron clusters. While [Fe₃Ni(μ₄-O)]-type clusters could be assembled, accessing an open heterobimetallic edge site proved challenging, thus prohibiting efforts to study chemical transformations, such as hydroxide attack onto carbon monoxide or carbon dioxide coordination, relevant to the native enzyme. Appendix B discusses the attempts to synthesize models of the full H-cluster of [FeFe]-hydrogenase using a bioinorganic approach. A synthetic peptide containing three cysteine donors was successfully synthesized and found to chelate a preformed synthetic [Fe₄S₄] cluster. However, efforts to incorporate the diiron subsite model complex proved challenging as the planned thioester exchange reaction was found to non-selectively acetylate the peptide backbone, thus preventing the construction of the full six-iron cluster.