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.

Dilution refrigeration and a calorimetric measurement of the quadruple coupling constant in rhenium metal

A dilution refrigerator has been constructed capable of producing steady state temperatures less than .075°K. The first part of this work is concerned with the design and construction of this machine. Enough theory is presented to allow one to understand the operation and critical design factors of a dilution refrigerator. The performance of our refrigerator is compared with the operating characteristics of three other dilution refrigerators appearing in the present literature.

The dilution refrigerator constructed was used to measure the nuclear contribution to the low temperature specific heat of a pure, single-crystalline sample of rhenium metal. Measurements were made in magnetic fields from 0 to 12.5 kOe for the temperature range .13°K - .52°K. The second part of this work discusses the results of these experiments. The expected nuclear contribution is not found when the sample is in the superconducting state. This is believed to be due to the long spin-lattice relaxation times in superconductors. In the normal state, for the temperature range studied, the nuclear contribution is given by A/T² where A = .061 ± .002 millijoules-K/mole. The value of A is found to increase to A = .077 ± .004 millijoules-K/mole when the sample is located in a magnetic field of 12.5 kOe.

From the measured value of A the splitting of the energy levels of the nuclear spin system due to the interaction of the internal crystalline electric field gradients with the nuclear quadrupole moments is calculated. A comparison is made between the predicted and measured magnetic dependence of the specific heat. Finally, predictions are made of future nuclear magnetic resonance experiments which may be performed to check the results obtained by calorimetery here and further, to investigate existing theories concerning the sources of electric field gradients in metals.

Part I. Electric birefringence studies of deoxyribonucleic acids. Part II. Selective dissociation of nucleohistone complexes

Part I

The electric birefringence of dilute DNA solutions has been studied in considerable detail and on a large number of samples, but no new and reliable information was discovered concerning the tertiary structure of DNA. The large number of variables which effect the birefringence results is discussed and suggestions are made for further work on the subject.

The DNA molecules have been aligned in a rapidly alternating (10 to 20 kc/sec) square wave field confirming that the orientation mechanism is that of counterion polarization. A simple empirical relation between the steady state birefringence, Δn_st, and the square of the electric field, E, has been found: Δn_st = E²/(a E² + b), where a = 1/Δn_s and b = (E²/Δn_st)_E→o. Δn_s is the birefringence extrapolated to infinite field strength.

The molecules show a distribution of relaxation times from 10^-4 to 0.2 sec, which is consistent with expectations for flexible coil molecules. The birefringence and the relaxation times decrease with increasing salt concentrations. They also depend on the field strength and pulse duration in a rather non-reproducible manner, which may be due in part to changes in the composition of the solution or in the molecular structure of the DNA (other than denaturation). Further progress depends on the development of some control over these effects.

Part II

The specificity of the dissociation of reconstituted and native deoxyribonucleohistones (DNH) by monovalent salt solutions has been investigated. A novel zone ultracentrifugation method is used in which the DNH is sedimented as a zone through a preformed salt gradient, superimposed on a stabilizing D₂O (sucrose) density gradient. The results, obtained by scanning the quartz sedimentation tubes in a spectrophotometer, were verified by the conventional, preparative sedimentation technique. Procedures are discussed for the detection of microgram quantities of histones, since low concentrations must be used to prevent excessive aggregation of the DNH.

The data show that major histone fractions are selectively dissociated from DNH by increasing salt concentrations: Lysine rich histone (H I) dissociates gradually between 0.1 and 0.3 F, slightly lysine rich histone (H II) dissociates as a narrow band between 0.35 and 0.5 F, and arginine rich histone (H III, H IV) dissociates gradually above 0.5 F NaClO₄.

The activity of the partially dissociated, native DNH in sustaining RNA synthesis, their mobility and their unusual heat denaturation and renaturation behavior are described. The two-step melting behavior of the material indicates that the histones are non-randomly distributed along the DNA, but the implications are that the uncovered regions are not of gene-size length.

1. Ultrasonic studies of binary liquid structure in the critical region. Theory and experiment for the 2,6-lutidine/water system. 2. Hartree-Fock calculations of electric polarizabilities of some simple atoms and molecules, and their practicality. 3. Calculation of vibrational transition probabilities in collinear atom-diatom and diatom-diatom collisions with Lennard-Jones interaction

Part 1. Many interesting visual and mechanical phenomena occur in the critical region of fluids, both for the gas-liquid and liquid-liquid transitions. The precise thermodynamic and transport behavior here has some broad consequences for the molecular theory of liquids. Previous studies in this laboratory on a liquid-liquid critical mixture via ultrasonics supported a basically classical analysis of fluid behavior by M. Fixman (e. g., the free energy is assumed analytic in intensive variables in the thermodynamics)--at least when the fluid is not too close to critical. A breakdown in classical concepts is evidenced close to critical, in some well-defined ways. We have studied herein a liquid-liquid critical system of complementary nature (possessing a lower critical mixing or consolute temperature) to all previous mixtures, to look for new qualitative critical behavior. We did not find such new behavior in the ultrasonic absorption ascribable to the critical fluctuations, but we did find extra absorption due to chemical processes (yet these are related to the mixing behavior generating the lower consolute point). We rederived, corrected, and extended Fixman's analysis to interpret our experimental results in these more complex circumstances. The entire account of theory and experiment is prefaced by an extensive introduction recounting the general status of liquid state theory. The introduction provides a context for our present work, and also points out problems deserving attention. Interest in these problems was stimulated by this work but also by work in Part 3.

Part 2. Among variational theories of electronic structure, the Hartree-Fock theory has proved particularly valuable for a practical understanding of such properties as chemical binding, electric multipole moments, and X-ray scattering intensity. It also provides the most tractable method of calculating first-order properties under external or internal one-electron perturbations, either developed explicitly in orders of perturbation theory or in the fully self-consistent method. The accuracy and consistency of first-order properties are poorer than those of zero-order properties, but this is most often due to the use of explicit approximations in solving the perturbed equations, or to inadequacy of the variational basis in size or composition. We have calculated the electric polarizabilities of H₂, He, Li, Be, LiH, and N₂ by Hartree-Fock theory, using exact perturbation theory or the fully self-consistent method, as dictated by convenience. By careful studies on total basis set composition, we obtained good approximations to limiting Hartree-Fock values of polarizabilities with bases of reasonable size. The values for all species, and for each direction in the molecular cases, are within 8% of experiment, or of best theoretical values in the absence of the former. Our results support the use of unadorned Hartree-Pock theory for static polarizabilities needed in interpreting electron-molecule scattering data, collision-induced light scattering experiments, and other phenomena involving experimentally inaccessible polarizabilities.

Part 3. Numerical integration of the close-coupled scattering equations has been carried out to obtain vibrational transition probabilities for some models of the electronically adiabatic H₂-H₂ collision. All the models use a Lennard-Jones interaction potential between nearest atoms in the collision partners. We have analyzed the results for some insight into the vibrational excitation process in its dependence on the energy of collision, the nature of the vibrational binding potential, and other factors. We conclude also that replacement of earlier, simpler models of the interaction potential by the Lennard-Jones form adds very little realism for all the complication it introduces. A brief introduction precedes the presentation of our work and places it in the context of attempts to understand the collisional activation process in chemical reactions as well as some other chemical dynamics.

New search for the Neutron Electric Dipole Moment using ultracold neutrons at the Spallation Neutron Source

This document introduces the planned new search for the neutron Electric Dipole Moment at the Spallation Neutron Source at the Oak Ridge National Laboratory. A spin precession measurement is to be carried out using Ultracold neutrons diluted in a superfluid Helium bath at T = 0.5 K, where spin polarized 3He atoms act as detector of the neutron spin polarization. This manuscript describes some of the key aspects of the planned experiment with the contributions from Caltech to the development of the project.

Techniques used in the design of magnet coils for Nuclear Magnetic Resonance were adapted to the geometry of the experiment. Described is an initial design approach using a pair of coils tuned to shield outer conductive elements from resistive heat loads, while inducing an oscillating field in the measurement volume. A small prototype was constructed to test the model of the field at room temperature.

A large scale test of the high voltage system was carried out in a collaborative effort at the Los Alamos National Laboratory. The application and amplification of high voltage to polished steel electrodes immersed in a superfluid Helium bath was studied, as well as the electrical breakdown properties of the electrodes at low temperatures. A suite of Monte Carlo simulation software tools to model the interaction of neutrons, 3He atoms, and their spins with the experimental magnetic and electric fields was developed and implemented to further the study of expected systematic effects of the measurement, with particular focus on the false Electric Dipole Moment induced by a Geometric Phase akin to Berry’s phase.

An analysis framework was developed and implemented using unbinned likelihood to fit the time modulated signal expected from the measurement data. A collaborative Monte Carlo data set was used to test the analysis methods.