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.

Convex analysis for minimizing and learning submodular set functions

The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions.

First, we develop a novel method for minimizing a particular class of submodular functions, which can be expressed as a sum of concave functions composed with modular functions. The basic algorithm uses an accelerated first order method applied to a smoothed version of its convex extension. The smoothing algorithm is particularly novel as it allows us to treat general concave potentials without needing to construct a piecewise linear approximation as with graph-based techniques.

Second, we derive the general conditions under which it is possible to find a minimizer of a submodular function via a convex problem. This provides a framework for developing submodular minimization algorithms. The framework is then used to develop several algorithms that can be run in a distributed fashion. This is particularly useful for applications where the submodular objective function consists of a sum of many terms, each term dependent on a small part of a large data set.

Lastly, we approach the problem of learning set functions from an unorthodox perspective---sparse reconstruction. We demonstrate an explicit connection between the problem of learning set functions from random evaluations and that of sparse signals. Based on the observation that the Fourier transform for set functions satisfies exactly the conditions needed for sparse reconstruction algorithms to work, we examine some different function classes under which uniform reconstruction is possible.

Multiplexed DNA-mediated electrochemistry

The aromatic core of double helical DNA possesses the unique and remarkable ability to form a conduit for electrons to travel over exceptionally long molecular distances. This core of π-stacked nucleobases creates an efficient pathway for charge transfer to proceed that is exquisitely sensitive to even subtle perturbations. Ground state electrochemistry of DNA-modified electrodes has been one of the major techniques used both to investigate and to harness the property of DNA-mediated charge transfer. DNA-modified electrodes have been an essential tool for both gaining insights into the fundamental properties of DNA and, due to the exquisite specificity of DNA-mediated charge transfer for the integrity of the π-stack, for use in next generation diagnostic sensing. Here, multiplexed DNA-modified electrodes are used to (i) gain new insights on the electrochemical coupling of metalloproteins to the DNA π-stack with relevance to the fundaments of in vivo DNA-mediated charge transfer and (ii) enhance the overall sensitivity of DNA-mediated reduction for use in the detection of low abundance diagnostic targets.

First, Methylene Blue (MB′) was covalently attached to DNA through a flexible C12 alkyl linker to yield a new redox reporter for DNA electrochemistry measurements with enhanced sensitivity. Tethered, intercalated MB′ was reduced through DNA-mediated charge transport. The redox signal intensity for MB′-dT-C12-DNA was found to be at least 3 fold larger than that of previously used Nile Blue (NB)-dT-DNA, which is coupled to the base stack via direct conjugation. The signal attenuation, due to an intervening mismatch, and therefore the degree of DNA-mediated reduction, does, however, depend on the DNA film morphology and the backfilling agent used to passivate the surface. These results highlight two possible mechanisms for the reduction of MB′ on the DNA-modified electrode that are distinguishable by their kinetics: reduction mediated by the DNA base pair stack and direct surface reduction of MB′ at the electrode. The extent of direct reduction at the surface can be minimized by overall DNA assembly conditions.

Next, a series of intercalation-based DNA-mediated electrochemical reporters were developed, using a flexible alkane linkage to validate and explore their DNA-mediated reduction. The general mechanism for the reduction of distally bound redox active species, covalently tethered to DNA through flexible alkyl linkages, was established to be an intraduplex DNA-mediated pathway. MB, NB, and anthraquinone were covalently tethered to DNA with three different covalent linkages. The extent of electronic coupling of the reporter was shown to correlate with the DNA binding affinity of the redox active species, supporting an intercalative mechanism. These electrochemical signals were shown to be exceptionally sensitive to a single intervening π-stack perturbation, an AC mismatch, in a densely packed DNA monolayer, which further supports that the reduction is DNA-mediated. Finally, this DNA-mediated reduction of MB occurs primarily via intra- rather than inter duplex intercalation, as probed through varying the proximity and integrity of the neighboring duplex DNA. Further gains to electrochemical sensitivity of our DNA-modified devices were then achieved through the application of electrocatalytic signal amplification using these solvent accessible intercalative reporters, MB-dT-C8, and hemoglobin as a novel electron sink. Electrocatalysis offers an excellent means of electrochemical signal amplification, yet in DNA based sensors, its application has been limited due to strict assembly conditions. We describe the use of hemoglobin as a robust and effective electron sink for electrocatalysis in DNA sensing on low density DNA films. Protein shielding of the heme redox center minimizes direct reduction at the electrode surface and permits assays on low density DNA films. Electrocatalysis of MB that is covalently tethered to the DNA by a flexible alkyl linkage allows for efficient interactions with both the base stack and hemoglobin. Consistent suppression of the redox signal upon incorporation of single CA mismatch in the DNA oligomer demonstrates that both the unamplified and the electrocatalytically amplified redox signals are generated through DNA-mediated charge transport. Electrocatalysis with hemoglobin is robust: it is stable to pH and temperature variations. The utility and applicability of electrocatalysis with hemoglobin is demonstrated through restriction enzyme detection, and an enhancement in sensitivity permits femtomole DNA sampling.

Finally, we expanded the application of our multiplexed DNA-modified electrodes to the electrochemical characterization of DNA-bound proteins containing [4Fe-4S] clusters. DNA-modified electrodes have become an essential tool for the characterization of the redox chemistry of DNA repair proteins that contain redox cofactors. Multiplexed analysis of EndonucleaseIII (EndoIII), a DNA repair protein containing a [4Fe-4S] cluster known to be accessible via DNA-mediated charge transport, elucidated subtle differences in the electrochemical behavior as a function of DNA morphology. DNA-bound EndoIII is seen to have two different electron transfer pathways for reduction, either through the DNA base stack or through direct surface reduction. Closely packed DNA films, where the protein has limited surface accessibility, produce electrochemical signals reflecting electron transfer that is DNA-mediated. The electrochemical comparison of EndoIII mutants, including a new family of mutations altering the electrostatics surrounding the [4Fe-4S] cluster, was able to be quantitatively performed. While little change in the midpoint potential was found for this family of mutants, significant variations in the efficiency of DNA-mediated electron transfer were apparent. Based on the stability of these proteins, examined by circular dichroism, we propose that the electron transfer pathway can be perturbed not only by the removal of aromatic residues, but also through changes in solvation near the cluster.

Voting games with incomplete information

We examine voting situations in which individuals have incomplete information over each others' true preferences. In many respects, this work is motivated by a desire to provide a more complete understanding of so-called probabilistic voting.

Chapter 2 examines the similarities and differences between the incentives faced by politicians who seek to maximize expected vote share, expected plurality, or probability of victory in single member: single vote, simple plurality electoral systems. We find that, in general, the candidates' optimal policies in such an electoral system vary greatly depending on their objective function. We provide several examples, as well as a genericity result which states that almost all such electoral systems (with respect to the distributions of voter behavior) will exhibit different incentives for candidates who seek to maximize expected vote share and those who seek to maximize probability of victory.

In Chapter 3, we adopt a random utility maximizing framework in which individuals' preferences are subject to action-specific exogenous shocks. We show that Nash equilibria exist in voting games possessing such an information structure and in which voters and candidates are each aware that every voter's preferences are subject to such shocks. A special case of our framework is that in which voters are playing a Quantal Response Equilibrium (McKelvey and Palfrey (1995), (1998)). We then examine candidate competition in such games and show that, for sufficiently large electorates, regardless of the dimensionality of the policy space or the number of candidates, there exists a strict equilibrium at the social welfare optimum (i.e., the point which maximizes the sum of voters' utility functions). In two candidate contests we find that this equilibrium is unique.

Finally, in Chapter 4, we attempt the first steps towards a theory of equilibrium in games possessing both continuous action spaces and action-specific preference shocks. Our notion of equilibrium, Variational Response Equilibrium, is shown to exist in all games with continuous payoff functions. We discuss the similarities and differences between this notion of equilibrium and the notion of Quantal Response Equilibrium and offer possible extensions of our framework.

Baryon and lepton numbers in particle physics beyond the standard model

The works presented in this thesis explore a variety of extensions of the standard model of particle physics which are motivated by baryon number (B) and lepton number (L), or some combination thereof. In the standard model, both baryon number and lepton number are accidental global symmetries violated only by non-perturbative weak effects, though the combination B-L is exactly conserved. Although there is currently no evidence for considering these symmetries as fundamental, there are strong phenomenological bounds restricting the existence of new physics violating B or L. In particular, there are strict limits on the lifetime of the proton whose decay would violate baryon number by one unit and lepton number by an odd number of units.

The first paper included in this thesis explores some of the simplest possible extensions of the standard model in which baryon number is violated, but the proton does not decay as a result. The second paper extends this analysis to explore models in which baryon number is conserved, but lepton flavor violation is present. Special attention is given to the processes of μ to e conversion and μ → eγ which are bound by existing experimental limits and relevant to future experiments.

The final two papers explore extensions of the minimal supersymmetric standard model (MSSM) in which both baryon number and lepton number, or the combination B-L, are elevated to the status of being spontaneously broken local symmetries. These models have a rich phenomenology including new collider signatures, stable dark matter candidates, and alternatives to the discrete R-parity symmetry usually built into the MSSM in order to protect against baryon and lepton number violating processes.

Rational design of zinc phosphide heterojunction photovoltaics

The prospect of terawatt-scale electricity generation using a photovoltaic (PV) device places strict requirements on the active semiconductor optoelectronic properties and elemental abundance. After reviewing the constraints placed on an "earth-abundant" solar absorber, we find zinc phosphide (α-Zn₃P₂) to be an ideal candidate. In addition to its near-optimal direct band gap of 1.5 eV, high visible-light absorption coefficient (>10⁴ cm^-1), and long minority-carrier diffusion length (>5 μm), Zn₃P₂ is composed of abundant Zn and P elements and has excellent physical properties for scalable thin-film deposition. However, to date, a Zn₃P₂ device of sufficient efficiency for commercial applications has not been demonstrated. Record efficiencies of 6.0% for multicrystalline and 4.3% for thin-film cells have been reported, respectively. Performance has been limited by the intrinsic p-type conductivity of Zn₃P₂ which restricts us to Schottky and heterojunction device designs. Due to our poor understanding of Zn₃P₂ interfaces, an ideal heterojunction partner has not yet been found.

The goal of this thesis is to explore the upper limit of solar conversion efficiency achievable with a Zn₃P₂ absorber through the design of an optimal heterojunction PV device. To do so, we investigate three key aspects of material growth, interface energetics, and device design. First, the growth of Zn₃P₂ on GaAs(001) is studied using compound-source molecular-beam epitaxy (MBE). We successfully demonstrate the pseudomorphic growth of Zn₃P₂ epilayers of controlled orientation and optoelectronic properties. Next, the energy-band alignments of epitaxial Zn₃P₂ and II-VI and III-V semiconductor interfaces are measured via high-resolution x-ray photoelectron spectroscopy in order to determine the most appropriate heterojunction partner. From this work, we identify ZnSe as a nearly ideal n-type emitter for a Zn₃P₂ PV device. Finally, various II-VI/Zn₃P₂ heterojunction solar cells designs are fabricated, including substrate and superstrate architectures, and evaluated based on their solar conversion efficiency.

Optimization and Control of Power Flow in Distribution Networks

Climate change is arguably the most critical issue facing our generation and the next. As we move towards a sustainable future, the grid is rapidly evolving with the integration of more and more renewable energy resources and the emergence of electric vehicles. In particular, large scale adoption of residential and commercial solar photovoltaics (PV) plants is completely changing the traditional slowly-varying unidirectional power flow nature of distribution systems. High share of intermittent renewables pose several technical challenges, including voltage and frequency control. But along with these challenges, renewable generators also bring with them millions of new DC-AC inverter controllers each year. These fast power electronic devices can provide an unprecedented opportunity to increase energy efficiency and improve power quality, if combined with well-designed inverter control algorithms. The main goal of this dissertation is to develop scalable power flow optimization and control methods that achieve system-wide efficiency, reliability, and robustness for power distribution networks of future with high penetration of distributed inverter-based renewable generators.

Proposed solutions to power flow control problems in the literature range from fully centralized to fully local ones. In this thesis, we will focus on the two ends of this spectrum. In the first half of this thesis (chapters 2 and 3), we seek optimal solutions to voltage control problems provided a centralized architecture with complete information. These solutions are particularly important for better understanding the overall system behavior and can serve as a benchmark to compare the performance of other control methods against. To this end, we first propose a branch flow model (BFM) for the analysis and optimization of radial and meshed networks. This model leads to a new approach to solve optimal power flow (OPF) problems using a two step relaxation procedure, which has proven to be both reliable and computationally efficient in dealing with the non-convexity of power flow equations in radial and weakly-meshed distribution networks. We will then apply the results to fast time- scale inverter var control problem and evaluate the performance on real-world circuits in Southern California Edison’s service territory.

The second half (chapters 4 and 5), however, is dedicated to study local control approaches, as they are the only options available for immediate implementation on today’s distribution networks that lack sufficient monitoring and communication infrastructure. In particular, we will follow a reverse and forward engineering approach to study the recently proposed piecewise linear volt/var control curves. It is the aim of this dissertation to tackle some key problems in these two areas and contribute by providing rigorous theoretical basis for future work.