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.

Gas laser discharge noise and its effect on the laser output

A large portion of the noise in the light output of a laser oscillator is associated with the noise in the laser discharge. The effect of the discharge noise on the laser output has been studied. The discharge noise has been explained through an ac equivalent circuit of the laser discharge tube.

The discharge noise corresponds to time-varying spatial fluctuations in the electron density, the inverted population density and the dielectric permittivity of the laser medium from their equilibrium values. These fluctuations cause a shift in the resonant frequencies of the laser cavity. When the fluctuation in the dielectric permittivity of the laser medium is a longitudinally traveling wave (corresponding to the case in which moving striations exist in the positive column of the laser discharge), the laser output is frequency modulated.

The discharge noise has been analyzed by representing the laser discharge by an equivalent circuit. An appropriate ac equivalent circuit of a laser discharge tube has been obtained by considering the frequency spectrum of the current response of the discharge tube to an ac voltage modulation. It consist of a series ρLC circuit, which represents the discharge region, in parallel with a capacitance C', which comes mainly from the stray wiring. The equivalent inductance and capacitance of the discharge region have been calculated from the values of the resonant frequencies measured on discharge currents, gas pressures and lengths of the positive column. The experimental data provide for a set of typical values and dependencies on the discharge parameters for the equivalent inductance and capacitance of a discharge under laser operating conditions. It has been concluded from the experimental data that the equivalent inductance originates mainly from the positive column while the equivalent capacitance is due to the discharge region other than the positive column.

The ac equivalent circuit of the laser discharge has been shown analytically and experimentally to be applicable to analyzing the internal discharge noise. Experimental measurements have been made on the frequency of moving striations in a laser discharge. Its experimental dependence on the discharge current agrees very well with the expected dependence obtained from an analysis of the circuit and the experimental data on the equivalent circuit elements. The agreement confirms the validity of representing a laser discharge tube by its ac equivalent circuit in analyzing the striation phenomenon and other low frequency noises. Data have also been obtained for the variation of the striation frequency with an externally-applied longitudinal magnetic field and the increase in frequency has been attributed to a decrease in the equivalent inductance of the laser discharge.

The ionic basis of frequency selectivity in hair cells of the bullfrog's sacculus

Hair cells from the bull frog's sacculus, a vestibular organ responding to substrate-borne vibration, possess electrically resonant membrane properties which maximize the sensitivity of each cell to a particular frequency of mechanical input. The electrical resonance of these cells and its underlying ionic basis were studied by applying gigohm-seal recording techniques to solitary hair cells enzymatically dissociated from the sacculus. The contribution of electrical resonance to frequency selectivity was assessed from microelectrode recordings from hair cells in an excised preparation of the sacculus.

Electrical resonance in the hair cell is demonstrated by damped membrane-potential oscillations in response to extrinsic current pulses applied through the recording pipette. This response is analyzed as that of a damped harmonic oscillator. Oscillation frequency rises with membrane depolarization, from 80-160 Hz at resting potential to asymptotic values of 200-250 Hz. The sharpness of electrical tuning, denoted by the electrical quality factor, Q_e, is a bell-shaped function of membrane voltage, reaching a maximum value around eight at a membrane potential slightly positive to the resting potential.

In whole cells, three time-variant ionic currents are activated at voltages more positive than -60 to -50 mV; these are identified as a voltage-dependent, non-inactivating Ca current (I_ca), a voltage-dependent, transient K current (I_a), and a Ca-dependent K current (I_c). The C channel is identified in excised, inside-out membrane patches on the basis of its large conductance (130-200 pS), its selective permeability to Kover Na or Cl, and its activation by internal Ca ions and membrane depolarization. Analysis of open- and closed-lifetime distributions suggests that the C channel can assume at least two open and three closed kinetic states.

Exposing hair cells to external solutions that inhibit the Ca or C conductances degrades the electrical resonance properties measured under current-clamp conditions, while blocking the A conductance has no significant effect, providing evidence that only the Ca and C conductances participate in the resonance mechanism. To test the sufficiency of these two conductances to account for electrical resonance, a mathematical model is developed that describes I_ca, I_c, and intracellular Ca concentration during voltage-clamp steps. I_ca activation is approximated by a third-order Hodgkin-Huxley kinetic scheme. Ca entering the cell is assumed to be confined to a small submembrane compartment which contains an excess of Ca buffer; Ca leaves this space with first-order kinetics. The Ca- and voltage-dependent activation of C channels is described by a five-state kinetic scheme suggested by the results of single-channel observations. Parameter values in the model are adjusted to fit the waveforms of I_ca and I_c evoked by a series of voltage-clamp steps in a single cell. Having been thus constrained, the model correctly predicts the character of voltage oscillations produced by current-clamp steps, including the dependencies of oscillation frequency and Q_e on membrane voltage. The model shows quantitatively how the Ca and C conductances interact, via changes in intracellular Ca concentration, to produce electrical resonance in a vertebrate hair cell.