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.

Exploiting seismic waveforms of ambient noise and earthquakes

In this thesis, I apply detailed waveform modeling to study noise correlations in different environments, and earthquake waveforms for source parameters and velocity structure.

Green's functions from ambient noise correlations have primarily been used for travel-time measurement. In Part I of this thesis, by detailed waveform modeling of noise correlation functions, I retrieve both surface waves and crustal body waves from noise, and use them in improving earthquake centroid locations and regional crustal structures. I also present examples in which the noise correlations do not yield Green's functions, yet the results are still interesting and useful after case-by-case analyses, including non-uniform distribution of noise sources, spurious velocity changes, and noise correlations on the Amery Ice Shelf.

In Part II of this thesis, I study teleseismic body waves of earthquakes for source parameters or near-source structure. With the dense modern global network and improved methodologies, I obtain high-resolution earthquake locations, focal mechanisms and rupture processes, which provide critical insights to earthquake faulting processes in shallow and deep parts of subduction zones. Waveform modeling of relatively simple subduction zone events also displays new constraints on the structure of subducted slabs.

In summary, behind my approaches to the relatively independent problems, the philosophy is to bring observational insights from seismic waveforms in critical and simple ways.

Theoretical investigation of turbulent boundary layer over a wavy surface

The important features of the two-dimensional incompressible turbulent flow over a wavy surface of wavelength comparable with the boundary layer thickness are analyzed.

A turbulent field method using model equation for turbulent shear stress similar to the scheme of Bradshaw, Ferriss and Atwell (1967) is employed with suitable modification to cover the viscous sublayer. The governing differential equations are linearized based on the small but finite amplitude to wavelength ratio. An orthogonal wavy coordinate system, accurate to the second order in the amplitude ratio, is adopted to avoid the severe restriction to the validity of linearization due to the large mean velocity gradient near the wall. Analytic solution up to the second order is obtained by using the method of matched-asymptotic-expansion based on the large Reynolds number and hence the small skin friction coefficient.

In the outer part of the layer, the perturbed flow is practically "inviscid." Solutions for the velocity, Reynolds stress and also the wall pressure distributions agree well with the experimental measurement. In the wall region where the perturbed Reynolds stress plays an important role in the process of momentum transport, only a qualitative agreement is obtained. The results also show that the nonlinear second-order effect is negligible for amplitude ratio of 0.03. The discrepancies in the detailed structure of the velocity, shear stress, and skin friction distributions near the wall suggest modifications to the model are required to describe the present problem.

Measurement of the direct CP asymmetry in b-->s+gamma via sum of exclusive B Meson decays using the BABAR detector

We perform a measurement of direct CP violation in b to s+gamma Acp, and the measurement of a difference between Acp for neutral B and charged B mesons, Delta A_{X_s\gamma}, using 429 inverse femtobarn of data recorded at the Upsilon(4S) resonance with the BABAR detector. B mesons are reconstructed from 16 exclusive final states. Particle identification is done using an algorithm based on Error Correcting Output Code with an exhaustive matrix. Background rejection and best candidate selection are done using two decision tree-based classifiers. We found $\acp = 1.73%+-1.93%+-1.02% and Delta A_X_sgamma = 4.97%+-3.90%+-1.45% where the uncertainties are statistical and systematic respectively. Based on the measured value of Delta A_X_sgamma, we determine a 90% confidence interval for Im C_8g/C_7gamma, where C_7gamma and C_8g are Wilson coefficients for New Physics amplitudes, at -1.64 < Im C_8g/C_7gamma < 6.52.

A measurement of B0-B0 mixing in e+e- annihilation at 29 GeV

This thesis describes a measurement of B⁰- B⁰ mixing in events produced by electron-positron annihilation at a center of mass energy of 29 GeV. The data were taken by the Mark II detector in the PEP storage ring at the Stanford Linear Accelerator Center between 1981 and 1987, and correspond to a total integrated luminosity of 224pb^-1.

We used a new method, based on the kinematics of hadronic events containing two leptons, to provide a measurement of the probability, x, that a hadron, initially containing a b (b) quark decays to a positive (negative) lepton to be X = 0.17^+0.15_-0.08, with 90% confidence level upper and lower limits of 0.38 and 0.06, respectively, including all estimated systematic errors. Because of the good separation of signal and background, this result is relatively insensitive to various systematic effects which have complicated previous measurements.

We interpret this result as evidence for the mixing of neutral B mesons. Based on existing B⁰_d mixing rate measurements, and some assumptions about the fractions of B⁰_d and B⁰_s mesons present in the data, this result favors maximal mixing of B⁰_s mesons, although it cannot rule out zero B⁰_s mixing at the 90% confidence level.

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.

Current dependence of the energy gap in superconductors : a direct measurement

From the tunneling characteristics of a tin-tin oxide-lead junction, a direct measurement has been made of the energy-gap variation for a superconductor carrying a current in a compensated geometry. Throughout the region investigated – several temperatures near T_c and down to a reduced temperature t = 0.8 –the observed current dependence agrees quite well with predictions based on the Ginzburg-Landau-Gor’kov theory. Near T_c the predicted temperature dependence is also well verified, though deviations are observed at lower temperatures; even for the latter, the data are internally consistent with the temperature dependence of the experimental critical current. At the lowest temperature investigated, t = 0.8, a small “Josephson” tunneling current allowed further a direct measurement of the electron drift velocity at low current densities. From this, a preliminary experimental value of the critical velocity, believed to be the first reported, can be inferred in the basis of Ginzburg-Landau theory. For tin at t = 0.8, we find v_c = 87 m/sec. This value does not appear fully consistent with those predicted by recent theories for superconductors with short electronic mean-free-paths.