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.

On the thermal budget of Pahoehoe lava flows

In this thesis I investigate some aspects of the thermal budget of pahoehoe lava flows. This is done with a combination of general field observations, quantitative modeling, and specific field experiments. The results of this work apply to pahoehoe flows in general, even though the vast bulk of the work has been conducted on the lavas formed by the Pu'u 'O'o - Kupaianaha eruption of Kilauea Volcano on Hawai'i. The field observations rely heavily on discussions with the staff of the United States Geological Survey's Hawaiian Volcano Observatory (HVO), under whom I labored repeatedly in 1991-1993 for a period totaling about 10 months.

The quantitative models I have constructed are based on the physical processes observed by others and myself to be active on pahoehoe lava flows. By building up these models from the basic physical principles involved, this work avoids many of the pitfalls of earlier attempts to fit field observations with "intuitively appropriate" mathematical expressions. Unlike many earlier works, my model results can be analyzed in terms of the interactions between the different physical processes. I constructed models to: (1) describe the initial cooling of small pahoehoe flow lobes and (2) understand the thermal budget of lava tubes.

The field experiments were designed either to validate model results or to constrain key input parameters. In support of the cooling model for pahoehoe flow lobes, attempts were made to measure: (1) the cooling within the flow lobes, (2) the amount of heat transported away from the lava by wind, and (3) the growth of the crust on the lobes. Field data collected by Jones [1992], Hon et al. [1994b], and Denlinger [Keszthelyi and Denlinger, in prep.] were also particularly useful in constraining my cooling model for flow lobes. Most of the field observations I have used to constrain the thermal budget of lava tubes were collected by HVO (geological and geophysical monitoring) and the Jet Propulsion Laboratory (airborne infrared imagery [Realmuto et al., 1992]). I was able to assist HVO for part of their lava tube monitoring program and also to collect helicopterborne and ground-based IR video in collaboration with JPL [Keszthelyi et al., 1993].

The most significant results of this work are (1) the quantitative demonstration that the emplacement of pahoehoe and 'a'a flows are the fundamentally different, (2) confirmation that even the longest lava flows observed in our Solar System could have formed as low effusion rate, tube-fed pahoehoe flows, and (3) the recognition that the atmosphere plays a very important role throughout the cooling of history of pahoehoe lava flows. In addition to answering specific questions about the thermal budget of tube-fed pahoehoe lava flows, this thesis has led to some additional, more general, insights into the emplacement of these lava flows. This general understanding of the tube-fed pahoehoe lava flow as a system has suggested foci for future research in this part of physical volcanology.

Large-eddy simulations of fully developed turbulent channel and pipe flows with smooth and rough walls

Studies in turbulence often focus on two flow conditions, both of which occur frequently in real-world flows and are sought-after for their value in advancing turbulence theory. These are the high Reynolds number regime and the effect of wall surface roughness. In this dissertation, a Large-Eddy Simulation (LES) recreates both conditions over a wide range of Reynolds numbers Re_τ = O(10²)-O(10⁸) and accounts for roughness by locally modeling the statistical effects of near-wall anisotropic fine scales in a thin layer immediately above the rough surface. A subgrid, roughness-corrected wall model is introduced to dynamically transmit this modeled information from the wall to the outer LES, which uses a stretched-vortex subgrid-scale model operating in the bulk of the flow. Of primary interest is the Reynolds number and roughness dependence of these flows in terms of first and second order statistics. The LES is first applied to a fully turbulent uniformly-smooth/rough channel flow to capture the flow dynamics over smooth, transitionally rough and fully rough regimes. Results include a Moody-like diagram for the wall averaged friction factor, believed to be the first of its kind obtained from LES. Confirmation is found for experimentally observed logarithmic behavior in the normalized stream-wise turbulent intensities. Tight logarithmic collapse, scaled on the wall friction velocity, is found for smooth-wall flows when Re_τ ≥ O(10⁶) and in fully rough cases. Since the wall model operates locally and dynamically, the framework is used to investigate non-uniform roughness distribution cases in a channel, where the flow adjustments to sudden surface changes are investigated. Recovery of mean quantities and turbulent statistics after transitions are discussed qualitatively and quantitatively at various roughness and Reynolds number levels. The internal boundary layer, which is defined as the border between the flow affected by the new surface condition and the unaffected part, is computed, and a collapse of the profiles on a length scale containing the logarithm of friction Reynolds number is presented. Finally, we turn to the possibility of expanding the present framework to accommodate more general geometries. As a first step, the whole LES framework is modified for use in the curvilinear geometry of a fully-developed turbulent pipe flow, with implementation carried out in a spectral element solver capable of handling complex wall profiles. The friction factors have shown favorable agreement with the superpipe data, and the LES estimates of the Karman constant and additive constant of the log-law closely match values obtained from experiment.

Suspension mechanics: I. Inertial and non-Newtonian migration of neutrally buoyant rigid spheres in two-dimensional unidirectional flows; II. The effect of viscoelasticity on the creeping motion of a train of neutrally buoyant Newtonian drops through a circular tube

The lateral migration of neutrally buoyant rigid spheres in two-dimensional unidirectional flows was studied theoretically. The cases of both inertia-induced migration in a Newtonian fluid and normal stress-induced migration in a second-order fluid were considered. Analytical results for the lateral velocities were obtained, and the equilibrium positions and trajectories of the spheres compared favorably with the experimental data available in the literature. The effective viscosity was obtained for a dilute suspension of spheres which were simultaneously undergoing inertia-induced migration and translational Brownian motion in a plane Poiseuille flow. The migration of spheres suspended in a second-order fluid inside a screw extruder was also considered.

The creeping motion of neutrally buoyant concentrically located Newtonian drops through a circular tube was studied experimentally for drops which have an undeformed radius comparable to that of the tube. Both a Newtonian and a viscoelastic suspending fluid were used in order to determine the influence of viscoelasticity. The extra pressure drop due to the presence of the suspended drops, the shape and velocity of the drops, and the streamlines of the flow were obtained for various viscosity ratios, total flow rates, and drop sizes. The results were compared with existing theoretical and experimental data.

Effects of density differences on lateral mixing in open-channel flows

This study investigates lateral mixing of tracer fluids in turbulent open-channel flows when the tracer and ambient fluids have different densities. Longitudinal dispersion in flows with longitudinal density gradients is investigated also.

Lateral mixing was studied in a laboratory flume by introducing fluid tracers at the ambient flow velocity continuously and uniformly across a fraction of the flume width and over the entire depth of the ambient flow. Fluid samples were taken to obtain concentration distributions in cross-sections at various distances, x, downstream from the tracer source. The data were used to calculate variances of the lateral distributions of the depth-averaged concentration. When there was a difference in density between the tracer and the ambient fluids, lateral mixing close to the source was enhanced by density-induced secondary flows; however, far downstream where the density gradients were small, lateral mixing rates were independent of the initial density difference. A dimensional analysis of the problem and the data show that the normalized variance is a function of only three dimensionless numbers, which represent: (1) the x-coordinate, (2) the source width, and (3) the buoyancy flux from the source.

A simplified set of equations of motion for a fluid with a horizontal density gradient was integrated to give an expression for the density-induced velocity distribution. The dispersion coefficient due to this velocity distribution was also obtained. Using this dispersion coefficient in an analysis for predicting lateral mixing rates in the experiments of this investigation gave only qualitative agreement with the data. However, predicted longitudinal salinity distributions in an idealized laboratory estuary agree well with published data.

Entrainment of fine sediments by turbulent flows

A study was made of the means by which turbulent flows entrain sediment grains from alluvial stream beds. Entrainment was considered to include both the initiation of sediment motion and the suspension of grains by the flow. Observations of grain motion induced by turbulent flows led to the formulation of an entrainment hypothesis. It was based on the concept of turbulent eddies disrupting the viscous sublayer and impinging directly onto the grain surface. It is suggested that entrainment results from the interaction between fluid elements within an eddy and the sediment grains.

A pulsating jet was used to simulate the flow conditions in a turbulent boundary layer. Evidence is presented to establish the validity of this representation. Experiments were made to determine the dependence of jet strength, defined below, upon sediment and fluid properties. For a given sediment and fluid, and fixed jet geometry there were two critical values of jet strength: one at which grains started to roll across the bed, and one at which grains were projected up from the bed. The jet strength K, is a function of the pulse frequency, ω, and the pulse amplitude, A, defined by

K = Aω^-s

Where s is the slope of a plot of log A against log ω. Pulse amplitude is equal to the volume of fluid ejected at each pulse divided by the cross sectional area of the jet tube.

Dimensional analysis was used to determine the parameters by which the data from the experiments could be correlated. Based on this, a method was devised for computing the pulse amplitude and frequency necessary either to move or project grains from the bed for any specified fluid and sediment combination.

Experiments made in a laboratory flume with a turbulent flow over a sediment bed are described. Dye injection was used to show the presence, in a turbulent boundary layer, of two important aspects of the pulsating jet model and the impinging eddy hypothesis. These were the intermittent nature of the sublayer and the presence of velocities with vertical components adjacent to the sediment bed.

A discussion of flow conditions, and the resultant grain motion, that occurred over sediment beds of different form is given. The observed effects of the sediment and fluid interaction are explained, in each case, in terms of the entrainment hypothesis.

The study does not suggest that the proposed entrainment mechanism is the only one by which grains can be entrained. However, in the writer’s opinion, the evidence presented strongly suggests that the impingement of turbulent eddies onto a sediment bed plays a dominant role in the process.

I. Stokes flow past a thin screen. II. Viscous flows past porous bodies of finite size

Part I

The slow, viscous flow past a thin screen is analyzed based on Stokes equations. The problem is reduced to an associated electric potential problem as introduced by Roscoe. Alternatively, the problem is formulated in terms of a Stokeslet distribution, which turns out to be equivalent to the first approach.

Special interest is directed towards the solution of the Stokes flow past a circular annulus. A "Stokeslet" formulation is used in this analysis. The problem is finally reduced to solving a Fredholm integral equation of the second kind. Numerical data for the drag coefficient and the mean velocity through the hole of the annulus are obtained.

Stokes flow past a circular screen with numerous holes is also attempted by assuming a set of approximate boundary conditions. An "electric potential" formulation is used, and the problem is also reduced to solving a Fredholm integral equation of the second kind. Drag coefficient and mean velocity through the screen are computed.

Part II

The purpose of this investigation is to formulate correctly a set of boundary conditions to be prescribed at the interface between a viscous flow region and a porous medium so that the problem of a viscous flow past a porous body can be solved.

General macroscopic equations of motion for flow through porous media are first derived by averaging Stokes equations over a volume element of the medium. These equations, including viscous stresses for the description, are more general than Darcy's law. They reduce to Darcy's law when the Darcy number becomes extremely small.

The interface boundary conditions of the first kind are then formulated with respect to the general macroscopic equations applied within the porous region. An application of such equations and boundary conditions to a Poiseuille shear flow problem demonstrates that there usually exists a thin interface layer immediately inside the porous medium in which the tangential velocity varies exponentially and Darcy's law does not apply.

With Darcy's law assumed within the porous region, interface boundary conditions of the second kind are established which relate the flow variables across the interface layer. The primary feature is a jump condition on the tangential velocity, which is found to be directly proportional to the normal gradient of the tangential velocity immediately outside the porous medium. This is in agreement with the experimental results of Beavers, et al.

The derived boundary conditions are applied in the solutions of two other problems: (1) Viscous flow between a rotating solid cylinder and a stationary porous cylinder, and (2) Stokes flow past a porous sphere.

Mixing, Chemical Reactions, and Combustion in Supersonic Flows

Experiments were conducted at the GALCIT supersonic shear-layer facility to investigate aspects of reacting transverse jets in supersonic crossflow using chemiluminescence and schlieren image-correlation velocimetry. In particular, experiments were designed to examine mixing-delay length dependencies on jet-fluid molar mass, jet diameter, and jet inclination.

The experimental results show that mixing-delay length depends on jet Reynolds number, when appropriately normalized, up to a jet Reynolds number of 500,000. Jet inclination increases the mixing-delay length, but causes less disturbance to the crossflow when compared to normal jet injection. This can be explained, in part, in terms of a control-volume analysis that relates jet inclination to flow conditions downstream of injection.

In the second part of this thesis, a combustion-modeling framework is proposed and developed that is tailored to large-eddy simulations of turbulent combustion in high-speed flows. Scaling arguments place supersonic hydrocarbon combustion in a regime of autoignition-dominated distributed reaction zones (DRZ). The proposed evolution-variable manifold (EVM) framework incorporates an ignition-delay data-driven induction model with a post-ignition manifold that uses a Lagrangian convected 'balloon' reactor model for chemistry tabulation. A large-eddy simulation incorporating the EVM framework captures several important reacting-flow features of a transverse hydrogen jet in heated-air crossflow experiment.