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.

Geometric discretization through primal-dual meshes

This thesis introduces new tools for geometric discretization in computer graphics and computational physics. Our work builds upon the duality between weighted triangulations and power diagrams to provide concise, yet expressive discretization of manifolds and differential operators. Our exposition begins with a review of the construction of power diagrams, followed by novel optimization procedures to fully control the local volume and spatial distribution of power cells. Based on this power diagram framework, we develop a new family of discrete differential operators, an effective stippling algorithm, as well as a new fluid solver for Lagrangian particles. We then turn our attention to applications in geometry processing. We show that orthogonal primal-dual meshes augment the notion of local metric in non-flat discrete surfaces. In particular, we introduce a reduced set of coordinates for the construction of orthogonal primal-dual structures of arbitrary topology, and provide alternative metric characterizations through convex optimizations. We finally leverage these novel theoretical contributions to generate well-centered primal-dual meshes, sphere packing on surfaces, and self-supporting triangulations.

Neural network design for switching network control

A neural network is a highly interconnected set of simple processors. The many connections allow information to travel rapidly through the network, and due to their simplicity, many processors in one network are feasible. Together these properties imply that we can build efficient massively parallel machines using neural networks. The primary problem is how do we specify the interconnections in a neural network. The various approaches developed so far such as outer product, learning algorithm, or energy function suffer from the following deficiencies: long training/ specification times; not guaranteed to work on all inputs; requires full connectivity.

Alternatively we discuss methods of using the topology and constraints of the problems themselves to design the topology and connections of the neural solution. We define several useful circuits-generalizations of the Winner-Take-All circuitthat allows us to incorporate constraints using feedback in a controlled manner. These circuits are proven to be stable, and to only converge on valid states. We use the Hopfield electronic model since this is close to an actual implementation. We also discuss methods for incorporating these circuits into larger systems, neural and nonneural. By exploiting regularities in our definition, we can construct efficient networks. To demonstrate the methods, we look to three problems from communications. We first discuss two applications to problems from circuit switching; finding routes in large multistage switches, and the call rearrangement problem. These show both, how we can use many neurons to build massively parallel machines, and how the Winner-Take-All circuits can simplify our designs.

Next we develop a solution to the contention arbitration problem of high-speed packet switches. We define a useful class of switching networks and then design a neural network to solve the contention arbitration problem for this class. Various aspects of the neural network/switch system are analyzed to measure the queueing performance of this method. Using the basic design, a feasible architecture for a large (1024-input) ATM packet switch is presented. Using the massive parallelism of neural networks, we can consider algorithms that were previously computationally unattainable. These now viable algorithms lead us to new perspectives on switch design.

Disorder driven transitions in non-equilibrium quantum systems

This thesis presents studies of the role of disorder in non-equilibrium quantum systems. The quantum states relevant to dynamics in these systems are very different from the ground state of the Hamiltonian. Two distinct systems are studied, (i) periodically driven Hamiltonians in two dimensions, and (ii) electrons in a one-dimensional lattice with power-law decaying hopping amplitudes. In the first system, the novel phases that are induced from the interplay of periodic driving, topology and disorder are studied. In the second system, the Anderson transition in all the eigenstates of the Hamiltonian are studied, as a function of the power-law exponent of the hopping amplitude.

In periodically driven systems the study focuses on the effect of disorder in the nature of the topology of the steady states. First, we investigate the robustness to disorder of Floquet topological insulators (FTIs) occurring in semiconductor quantum wells. Such FTIs are generated by resonantly driving a transition between the valence and conduction band. We show that when disorder is added, the topological nature of such FTIs persists as long as there is a gap at the resonant quasienergy. For strong enough disorder, this gap closes and all the states become localized as the system undergoes a transition to a trivial insulator.

Interestingly, the effects of disorder are not necessarily adverse, disorder can also induce a transition from a trivial to a topological system, thereby establishing a Floquet Topological Anderson Insulator (FTAI). Such a state would be a dynamical realization of the topological Anderson insulator. We identify the conditions on the driving field necessary for observing such a transition. We realize such a disorder induced topological Floquet spectrum in the driven honeycomb lattice and quantum well models.

Finally, we show that two-dimensional periodically driven quantum systems with spatial disorder admit a unique topological phase, which we call the anomalous Floquet-Anderson insulator (AFAI). The AFAI is characterized by a quasienergy spectrum featuring chiral edge modes coexisting with a fully localized bulk. Such a spectrum is impossible for a time-independent, local Hamiltonian. These unique characteristics of the AFAI give rise to a new topologically protected nonequilibrium transport phenomenon: quantized, yet nonadiabatic, charge pumping. We identify the topological invariants that distinguish the AFAI from a trivial, fully localized phase, and show that the two phases are separated by a phase transition.

The thesis also present the study of disordered systems using Wegner's Flow equations. The Flow Equation Method was proposed as a technique for studying excited states in an interacting system in one dimension. We apply this method to a one-dimensional tight binding problem with power-law decaying hoppings. This model presents a transition as a function of the exponent of the decay. It is shown that the the entire phase diagram, i.e. the delocalized, critical and localized phases in these systems can be studied using this technique. Based on this technique, we develop a strong-bond renormalization group that procedure where we solve the Flow Equations iteratively. This renormalization group approach provides a new framework to study the transition in this system.

A biochemical and structural characterization of Drosophila neuroglian

A number of cell-cell interactions in the nervous system are mediated by immunoglobulin gene superfamily members. For example, neuroglian, a homophilic neural cell adhesion molecule in Drosophila, has an extracellular portion comprising six C- 2 type immunoglobulin-like domains followed by five fibronectin type III (FnIII) repeats. Neuroglian shares this domain organization and significant sequence identity with Ll, a murine neural adhesion molecule that could be a functional homologue. Here I report the crystal structure of a proteolytic fragment containing the first two FnIII repeats of neuroglian (NgFn 1,2) at 2.0Å. The interpretation of photomicrographs of rotary shadowed Ng, the entire extracellular portion of neuroglian, and NgFnl-5, the five neuroglian Fn III domains, is also discussed.

The structure of NgFn 1,2 consists of two roughly cylindrical β-barrel structural motifs arranged in a head-to-tail fashion with the domains meeting at an angle of ~120, as defined by the cylinder axes. The folding topology of each domain is identical to that previously observed for single FnIII domains from tenascin and fibronectin. The domains of NgFn1,2 are related by an approximate two fold screw axis that is nearly parallel to the longest dimension of the fragment. Assuming this relative orientation is a general property of tandem FnIII repeats, the multiple tandem FnIII domains in neuroglian and other proteins are modeled as thin straight rods with two domain zig-zag repeats. When combined with the dimensions of pairs of tandem immunoglobulin-like domains from CD4 and CD2, this model suggests that neuroglian is a long narrow molecule (20 - 30 Å in diameter) that extends up to 370Å from the cell surface.

In photomicrographs, rotary shadowed Ng and NgFn1-5 appear to be highly flexible rod-like molecules. NgFn 1-5 is observed to bend in at least two positions and has a mean total length consistent with models generated from the NgFn1,2 structure. Ng molecules have up to four bends and a mean total length of 392 Å, consistent with a head-to-tail packing of neuroglian's C2-type domains.

Dirac spectra, summation formulae, and the spectral action

Noncommutative geometry is a source of particle physics models with matter Lagrangians coupled to gravity. One may associate to any noncommutative space (A, H, D) its spectral action, which is defined in terms of the Dirac spectrum of its Dirac operator D. When viewing a spin manifold as a noncommutative space, D is the usual Dirac operator. In this paper, we give nonperturbative computations of the spectral action for quotients of SU(2), Bieberbach manifolds, and SU(3) equipped with a variety of geometries. Along the way we will compute several Dirac spectra and refer to applications of this computation.

Geometric quantization and foliation reduction

A standard question in the study of geometric quantization is whether symplectic reduction interacts nicely with the quantized theory, and in particular whether “quantization commutes with reduction.” Guillemin and Sternberg first proposed this question, and answered it in the affirmative for the case of a free action of a compact Lie group on a compact Kähler manifold. Subsequent work has focused mainly on extending their proof to non-free actions and non-Kähler manifolds. For realistic physical examples, however, it is desirable to have a proof which also applies to non-compact symplectic manifolds.

In this thesis we give a proof of the quantization-reduction problem for general symplectic manifolds. This is accomplished by working in a particular wavefunction representation, associated with a polarization that is in some sense compatible with reduction. While the polarized sections described by Guillemin and Sternberg are nonzero on a dense subset of the Kähler manifold, the ones considered here are distributional, having support only on regions of the phase space associated with certain quantized, or “admissible”, values of momentum.

We first propose a reduction procedure for the prequantum geometric structures that “covers” symplectic reduction, and demonstrate how both symplectic and prequantum reduction can be viewed as examples of foliation reduction. Consistency of prequantum reduction imposes the above-mentioned admissibility conditions on the quantized momenta, which can be seen as analogues of the Bohr-Wilson-Sommerfeld conditions for completely integrable systems.

We then describe our reduction-compatible polarization, and demonstrate a one-to-one correspondence between polarized sections on the unreduced and reduced spaces.

Finally, we describe a factorization of the reduced prequantum bundle, suggested by the structure of the underlying reduced symplectic manifold. This in turn induces a factorization of the space of polarized sections that agrees with its usual decomposition by irreducible representations, and so proves that quantization and reduction do indeed commute in this context.

A significant omission from the proof is the construction of an inner product on the space of polarized sections, and a discussion of its behavior under reduction. In the concluding chapter of the thesis, we suggest some ideas for future work in this direction.

Computational design of self-assembling proteins and protein-DNA nanowires

Computational protein design (CPD) is a burgeoning field that uses a physical-chemical or knowledge-based scoring function to create protein variants with new or improved properties. This exciting approach has recently been used to generate proteins with entirely new functions, ones that are not observed in naturally occurring proteins. For example, several enzymes were designed to catalyze reactions that are not in the repertoire of any known natural enzyme. In these designs, novel catalytic activity was built de novo (from scratch) into a previously inert protein scaffold. In addition to de novo enzyme design, the computational design of protein-protein interactions can also be used to create novel functionality, such as neutralization of influenza. Our goal here was to design a protein that can self-assemble with DNA into nanowires. We used computational tools to homodimerize a transcription factor that binds a specific sequence of double-stranded DNA. We arranged the protein-protein and protein-DNA binding sites so that the self-assembly could occur in a linear fashion to generate nanowires. Upon mixing our designed protein homodimer with the double-stranded DNA, the molecules immediately self-assembled into nanowires. This nanowire topology was confirmed using atomic force microscopy. Co-crystal structure showed that the nanowire is assembled via the desired interactions. To the best of our knowledge, this is the first example of a protein-DNA self-assembly that does not rely on covalent interactions. We anticipate that this new material will stimulate further interest in the development of advanced biomaterials.

Characterization and modeling of premixed turbulent n-heptane flames in the thin reaction zone regime

n-heptane/air premixed turbulent flames in the high-Karlovitz portion of the thin reaction zone regime are characterized and modeled in this thesis using Direct Numerical Simulations (DNS) with detailed chemistry. In order to perform these simulations, a time-integration scheme that can efficiently handle the stiffness of the equations solved is developed first. A first simulation with unity Lewis number is considered in order to assess the effect of turbulence on the flame in the absence of differential diffusion. A second simulation with non-unity Lewis numbers is considered to study how turbulence affects differential diffusion. In the absence of differential diffusion, minimal departure from the 1D unstretched flame structure (species vs. temperature profiles) is observed. In the non-unity Lewis number case, the flame structure lies between that of 1D unstretched flames with "laminar" non-unity Lewis numbers and unity Lewis number. This is attributed to effective Lewis numbers resulting from intense turbulent mixing and a first model is proposed. The reaction zone is shown to be thin for both flames, yet large chemical source term fluctuations are observed. The fuel consumption rate is found to be only weakly correlated with stretch, although local extinctions in the non-unity Lewis number case are well correlated with high curvature. These results explain the apparent turbulent flame speeds. Other variables that better correlate with this fuel burning rate are identified through a coordinate transformation. It is shown that the unity Lewis number turbulent flames can be accurately described by a set of 1D (in progress variable space) flamelet equations parameterized by the dissipation rate of the progress variable. In the non-unity Lewis number flames, the flamelet equations suggest a dependence on a second parameter, the diffusion of the progress variable. A new tabulation approach is proposed for the simulation of such flames with these dimensionally-reduced manifolds.

The isolation and partial biochemical analysis of Sindbis virus proteins

Recently, the amino acid sequences have been reported for several proteins, including the envelope glycoproteins of Sindbis virus, which all probably span the plasma membrane with a common topology: a large N-terminal, extracellular portion, a short region buried in the bilayer, and a short C-terminal intracellular segment. The regions of these proteins buried in the bilayer correspond to portions of the protein sequences which contain a stretch of hydrophobic amino acids and which have other common characteristics, as discussed. Reasons are also described for uncertainty, in some proteins more than others, as to the precise location of some parts of the sequence relative to the membrane.

The signal hypothesis for the transmembrane translocation of proteins is briefly described and its general applicability is reviewed. There are many proteins whose translocation is accurately described by this hypothesis, but some proteins are translocated in a different manner.

The transmembraneous glycoproteins E1 and E2 of Sindbis virus, as well as the only other virion protein, the capsid protein, were purified in amounts sufficient for biochemical analysis using sensitive techniques. The amino acid composition of each protein was determined, and extensive N-terminal sequences were obtained for E1 and E2. By these techniques E1 and E2 are indistinguishable from most water soluble proteins, as they do not contain an obvious excess of hydrophobic amino acids in their N-terminal regions or in the intact molecule.

The capsid protein was found to be blocked, and so its N-terminus could not be sequenced by the usual methods. However, with the use of a special labeling technique, it was possible to incorporate tritiated acetate into the N-terminus of the protein with good specificity, which was useful in the purification of peptides from which the first amino acids in the N-terminal sequence could be identified.

Nanomole amounts of PE2, the intracellular precursor of E2, were purified by an immuno-affinity technique, and its N-terminus was analyzed. Together with other work, these results showed that PE2 is not synthesized with an N-terminal extension, and the signal sequence for translocation is probably the N-terminal amino acid sequence of the protein. This N-terminus was found to be 80-90% blocked, also by Nacetylation, and this acetylation did not affect its function as a signal sequence. The putative signal sequence was also found to contain a glycosylated asparagine residue, but the inhibition of this glycosylation did not lead to the cleavage of the sequence.

Locally convex Riesz spaces and Archimedean quotient spaces

A Riesz space with a Hausdorff, locally convex topology determined by Riesz seminorms is called a locally convex Riesz space. A sequence {x_n} in a locally convex Riesz space L is said to converge locally to x ϵ L if for some topologically bounded set B and every real r ˃ 0 there exists N (r) and n ≥ N (r) implies x – x_n ϵ r^b. Local Cauchy sequences are defined analogously, and L is said to be locally complete if every local Cauchy sequence converges locally. Then L is locally complete if and only if every monotone local Cauchy sequence has a least upper bound. This is a somewhat more general form of the completeness criterion for Riesz – normed Riesz spaces given by Luxemburg and Zaanen. Locally complete, bound, locally convex Riesz spaces are barrelled. If the space is metrizable, local completeness and topological completeness are equivalent.

Two measures of the non-archimedean character of a non-archimedean Riesz space L are the smallest ideal A_o (L) such that quotient space is Archimedean and the ideal I (L) = { x ϵ L: for some 0 ≤ v ϵ L, n |x| ≤ v for n = 1, 2, …}. In general A_o (L) ᴝ I (L). If L is itself a quotient space, a necessary and sufficient condition that A_o (L) = I (L) is given. There is an example where A_o (L) ≠ I (L).

A necessary and sufficient condition that a Riesz space L have every quotient space Archimedean is that for every 0 ≤ u, v ϵ L there exist u₁ = sup (inf (n v, u): n = 1, 2, …), and real numbers m₁ and m₂ such that m₁ u₁ ≥ v₁ and m₂ v₁ ≥ u₁. If, in addition, L is Dedekind σ – complete, then L may be represented as the space of all functions which vanish off finite subsets of some non-empty set.

Two and Three Finger Caging of Polygons and Polyhedra

Multi-finger caging offers a rigorous and robust approach to robot grasping. This thesis provides several novel algorithms for caging polygons and polyhedra in two and three dimensions. Caging refers to a robotic grasp that does not necessarily immobilize an object, but prevents it from escaping to infinity. The first algorithm considers caging a polygon in two dimensions using two point fingers. The second algorithm extends the first to three dimensions. The third algorithm considers caging a convex polygon in two dimensions using three point fingers, and considers robustness of this cage to variations in the relative positions of the fingers.

This thesis describes an algorithm for finding all two-finger cage formations of planar polygonal objects based on a contact-space formulation. It shows that two-finger cages have several useful properties in contact space. First, the critical points of the cage representation in the hand’s configuration space appear as critical points of the inter-finger distance function in contact space. Second, these critical points can be graphically characterized directly on the object’s boundary. Third, contact space admits a natural rectangular decomposition such that all critical points lie on the rectangle boundaries, and the sublevel sets of contact space and free space are topologically equivalent. These properties lead to a caging graph that can be readily constructed in contact space. Starting from a desired immobilizing grasp of a polygonal object, the caging graph is searched for the minimal, intermediate, and maximal caging regions surrounding the immobilizing grasp. An example constructed from real-world data illustrates and validates the method.

A second algorithm is developed for finding caging formations of a 3D polyhedron for two point fingers using a lower dimensional contact-space formulation. Results from the two-dimensional algorithm are extended to three dimension. Critical points of the inter-finger distance function are shown to be identical to the critical points of the cage. A decomposition of contact space into 4D regions having useful properties is demonstrated. A geometric analysis of the critical points of the inter-finger distance function results in a catalog of grasps in which the cages change topology, leading to a simple test to classify critical points. With these properties established, the search algorithm from the two-dimensional case may be applied to the three-dimensional problem. An implemented example demonstrates the method.

This thesis also presents a study of cages of convex polygonal objects using three point fingers. It considers a three-parameter model of the relative position of the fingers, which gives complete generality for three point fingers in the plane. It analyzes robustness of caging grasps to variations in the relative position of the fingers without breaking the cage. Using a simple decomposition of free space around the polygon, we present an algorithm which gives all caging placements of the fingers and a characterization of the robustness of these cages.

Topology optimization of silicon anode structures for lithium-ion battery applications

This thesis presents a topology optimization methodology for the systematic design of optimal multifunctional silicon anode structures in lithium-ion batteries. In order to develop next generation high performance lithium-ion batteries, key design challenges relating to the silicon anode structure must be addressed, namely the lithiation-induced mechanical degradation and the low intrinsic electrical conductivity of silicon. As such, this work considers two design objectives of minimum compliance under design dependent volume expansion, and maximum electrical conduction through the structure, both of which are subject to a constraint on material volume. Density-based topology optimization methods are employed in conjunction with regularization techniques, a continuation scheme, and mathematical programming methods. The objectives are first considered individually, during which the iteration history, mesh independence, and influence of prescribed volume fraction and minimum length scale are investigated. The methodology is subsequently extended to a bi-objective formulation to simultaneously address both the compliance and conduction design criteria. A weighting method is used to derive the Pareto fronts, which demonstrate a clear trade-off between the competing design objectives. Furthermore, a systematic parameter study is undertaken to determine the influence of the prescribed volume fraction and minimum length scale on the optimal combined topologies. The developments presented in this work provide a foundation for the informed design and development of silicon anode structures for high performance lithium-ion batteries.