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.

Hierarchical synthesis of complex DSP functions on FPGAs

SoC systems are now being increasingly constructed using a hierarchy of subsystems or silicon Intellectual Property (IP) cores. The key challenge is to use these cores in a highly efficient manner which can be difficult as the internal core structure may not be known. A design methodology based on synthesizing hierarchical circuit descriptions is presented. The paper employs the MARS synthesis scheduling algorithm within the existing IRIS synthesis flow and details how it can be enhanced to allow for design exploration of IP cores. It is shown that by accessing parameterised expressions for the datapath latencies in the cores, highly efficient FPGA solutions can be achieved. Hardware sharing at both the hierarchical and flattened levels is explored for a normalized lattice filter and results are presented.

CELLULAR AND DEVELOPMENTAL FUNCTIONS OF THE XENOPUS ARVCF-CATENIN:KAZRIN COMPLEX

Xenopus ARVCF (xARVCF), a member of p120-catenin subfamily, binds cadherin cytoplasmic domains to enhance cadherin metabolic stability, or when dissociated, modulates Rho-family GTPases. We previously found that xARVCF binds directly to Xenopus KazrinA (xKazrinA), a widely expressed, conserved protein that bears little homology to established protein families. xKazrinA is also known to influence keratinocyte proliferation-differentiation and cytoskeletal activity. In my study, I first evaluated the expression pattern of endogenous Kazrin RNA and protein in Xenopus embryogenesis as well as in adult tissues. We then collaboratively predicted the helical structure of Kazrin’s coiled-coil domain, and I obtained evidence of Kazrin’s dimerization/oligomerization. In considering the intracellular localization of the xARVCF-catenin:xKazrin complex, I did not resolve xKazrinA in a larger ternary complex with cadherin, nor did I detect its co-precipitation with core desmosomal components. Instead, screening revealed that xKazrinA binds spectrin. This suggested a potential means by which xKazrinA localizes to cell-cell junctions, and indeed, biochemical assays confirmed a ternary xARVCF:xKazrinA:xβ2-spectrin complex. Functionally, I demonstrated that xKazrin stabilizes cadherins by negatively modulating the RhoA small-GTPase. I further revealed that xKazrinA binds to p190B RhoGAP (an inhibitor of RhoA), and enhances p190B’s association with xARVCF. Supporting their functional interaction in vivo, Xenopus embryos depleted of xKazrin exhibited ectodermal shedding, a phenotype that could be rescued with exogenous xARVCF. Cell shedding appeared to be caused by RhoA activation, which consequently altered actin organization and cadherin function. Indeed, I was capable of rescuing Kazrin depletion with ectopic expression of p190B RhoGAP. In addition, I obtained evidence that xARVCF and xKazrin participate in craniofacial development, with effects observed upon the neural crest. Finally, I found that xKazrinA associates further with delta-catenin and p0071-catenin, but not with p120-catenin, suggesting that Kazrin interacts selectively with additional members of the p120-catenin sub-family. Taken together, my study supports Kazrin’s essential role in development, and reveals KazrinA’s biochemical and functional association with ARVCF-catenin, spectrin and p190B RhoGAP.

A Genetic Analysis of Interactions with Spc110p Reveals Distinct Functions of Spc97p and Spc98p, Components of the Yeast γ-Tubulin Complex

The spindle pole body (SPB) in Saccharomyces cerevisiae functions as the microtubule-organizing center. Spc110p is an essential structural component of the SPB and spans between the central and inner plaques of this multilamellar organelle. The amino terminus of Spc110p faces the inner plaque, the substructure from which spindle microtubules radiate. We have undertaken a synthetic lethal screen to identify mutations that enhance the phenotype of the temperature-sensitive spc110–221 allele, which encodes mutations in the amino terminus. The screen identified mutations in SPC97 and SPC98, two genes encoding components of the Tub4p complex in yeast. The spc98–63 allele is synthetic lethal only with spc110 alleles that encode mutations in the N terminus of Spc110p. In contrast, the spc97 alleles are synthetic lethal with spc110 alleles that encode mutations in either the N terminus or the C terminus. Using the two-hybrid assay, we show that the interactions of Spc110p with Spc97p and Spc98p are not equivalent. The N terminus of Spc110p displays a robust interaction with Spc98p in two different two-hybrid assays, while the interaction between Spc97p and Spc110p is not detectable in one strain and gives a weak signal in the other. Extra copies of SPC98 enhance the interaction between Spc97p and Spc110p, while extra copies of SPC97 interfere with the interaction between Spc98p and Spc110p. By testing the interactions between mutant proteins, we show that the lethal phenotype in spc98–63 spc110–221 cells is caused by the failure of Spc98–63p to interact with Spc110–221p. In contrast, the lethal phenotype in spc97–62 spc110–221 cells can be attributed to a decreased interaction between Spc97–62p and Spc98p. Together, these studies provide evidence that Spc110p directly links the Tub4p complex to the SPB. Moreover, an interaction between Spc98p and the amino-terminal region of Spc110p is a critical component of the linkage, whereas the interaction between Spc97p and Spc110p is dependent on Spc98p.

Nonlinear indicial response of complex nonstationary oscillations as pulmonary hypertension responding to step hypoxia

This paper is devoted to the quantization of the degree of nonlinearity of the relationship between two biological variables when one of the variables is a complex nonstationary oscillatory signal. An example of the situation is the indicial responses of pulmonary blood pressure (P) to step changes of oxygen tension (ΔpO2) in the breathing gas. For a step change of ΔpO2 beginning at time t1, the pulmonary blood pressure is a nonlinear function of time and ΔpO2, which can be written as P(t-t1 | ΔpO2). An effective method does not exist to examine the nonlinear function P(t-t1 | ΔpO2). A systematic approach is proposed here. The definitions of mean trends and oscillations about the means are the keys. With these keys a practical method of calculation is devised. We fit the mean trends of blood pressure with analytic functions of time, whose nonlinearity with respect to the oxygen level is clarified here. The associated oscillations about the mean can be transformed into Hilbert spectrum. An integration of the square of the Hilbert spectrum over frequency yields a measure of oscillatory energy, which is also a function of time, whose mean trends can be expressed by analytic functions. The degree of nonlinearity of the oscillatory energy with respect to the oxygen level also is clarified here. Theoretical extension of the experimental nonlinear indicial functions to arbitrary history of hypoxia is proposed. Application of the results to tissue remodeling and tissue engineering of blood vessels is discussed.

Introduction to Coding Theory for Flow Equations of Complex Systems Models

The modeling of complex dynamic systems depends on the solution of a differential equations system. Some problems appear because we do not know the mathematical expressions of the said equations. Enough numerical data of the system variables are known. The authors, think that it is very important to establish a code between the different languages to let them codify and decodify information. Coding permits us to reduce the study of some objects to others. Mathematical expressions are used to model certain variables of the system are complex, so it is convenient to define an alphabet code determining the correspondence between these equations and words in the alphabet. In this paper the authors begin with the introduction to the coding and decoding of complex structural systems modeling.

Disipation Functions of Flow Equations in Models of Complex Systems

In an open system, each disequilibrium causes a force. Each force causes a flow process, these being represented by a flow variable formally written as an equation called flow equation, and if each flow tends to equilibrate the system, these equations mathematically represent the tendency to that equilibrium. In this paper, the authors, based on the concepts of forces and conjugated fluxes and dissipation function developed by Onsager and Prigogine, they expose the following hypothesis: Is replaced in Prigogine’s Theorem the flow by its equation or by a flow orbital considering conjugate force as a gradient. This allows to obtain a dissipation function for each flow equation and a function of orbital dissipation.

Syntactic and Semantic Relationships in Models of Complex Systems: An Ecological Case

In this paper, the authors extend and generalize the methodology based on the dynamics of systems with the use of differential equations as equations of state, allowing that first order transformed functions not only apply to the primitive or original variables, but also doing so to more complex expressions derived from them, and extending the rules that determine the generation of transformed superior to zero order (variable or primitive). Also, it is demonstrated that for all models of complex reality, there exists a complex model from the syntactic and semantic point of view. The theory is exemplified with a concrete model: MARIOLA model.

Tables of complex hyperbolic and circular functions,

Bibliography: p. 209-212.

Theory of functions of a complex variable /

Mode of access: Internet.

Monogenic polynomials of four variables with binomial expansion

In the recent past one of the main concern of research in the field of Hypercomplex Function Theory in Clifford Algebras was the development of a variety of new tools for a deeper understanding about its true elementary roots in the Function Theory of one Complex Variable. Therefore the study of the space of monogenic (Clifford holomorphic) functions by its stratification via homogeneous monogenic polynomials is a useful tool. In this paper we consider the structure of those polynomials of four real variables with binomial expansion. This allows a complete characterization of sequences of 4D generalized monogenic Appell polynomials by three different types of polynomials. A particularly important case is that of monogenic polynomials which are simply isomorphic to the integer powers of one complex variable and therefore also called pseudo-complex powers.

Chebanov law and Vakar formula in mathematical models of complex systems

Ecological models written in a mathematical language L(M) or model language, with a given style or methodology can be considered as a text. It is possible to apply statistical linguistic laws and the experimental results demonstrate that the behaviour of a mathematical model is the same of any literary text of any natural language. A text has the following characteristics: (a) the variables, its transformed functions and parameters are the lexic units or LUN of ecological models; (b) the syllables are constituted by a LUN, or a chain of them, separated by operating or ordering LUNs; (c) the flow equations are words; and (d) the distribution of words (LUM and CLUN) according to their lengths is based on a Poisson distribution, the Chebanov's law. It is founded on Vakar's formula, that is calculated likewise the linguistic entropy for L(M). We will apply these ideas over practical examples using MARIOLA model. In this paper it will be studied the problem of the lengths of the simple lexic units composed lexic units and words of text models, expressing these lengths in number of the primitive symbols, and syllables. The use of these linguistic laws renders it possible to indicate the degree of information given by an ecological model.

Krylov subspace methods for approximating functions of symmetric positive definite matrices with applications to applied statistics and anomalous diffusion

Matrix function approximation is a current focus of worldwide interest and finds application in a variety of areas of applied mathematics and statistics. In this thesis we focus on the approximation of A^(-α/2)b, where A ∈ ℝ^(n×n) is a large, sparse symmetric positive definite matrix and b ∈ ℝ^n is a vector. In particular, we will focus on matrix function techniques for sampling from Gaussian Markov random fields in applied statistics and the solution of fractional-in-space partial differential equations. Gaussian Markov random fields (GMRFs) are multivariate normal random variables characterised by a sparse precision (inverse covariance) matrix. GMRFs are popular models in computational spatial statistics as the sparse structure can be exploited, typically through the use of the sparse Cholesky decomposition, to construct fast sampling methods. It is well known, however, that for sufficiently large problems, iterative methods for solving linear systems outperform direct methods. Fractional-in-space partial differential equations arise in models of processes undergoing anomalous diffusion. Unfortunately, as the fractional Laplacian is a non-local operator, numerical methods based on the direct discretisation of these equations typically requires the solution of dense linear systems, which is impractical for fine discretisations. In this thesis, novel applications of Krylov subspace approximations to matrix functions for both of these problems are investigated. Matrix functions arise when sampling from a GMRF by noting that the Cholesky decomposition A = LL^T is, essentially, a `square root' of the precision matrix A. Therefore, we can replace the usual sampling method, which forms x = L^(-T)z, with x = A^(-1/2)z, where z is a vector of independent and identically distributed standard normal random variables. Similarly, the matrix transfer technique can be used to build solutions to the fractional Poisson equation of the form ϕn = A^(-α/2)b, where A is the finite difference approximation to the Laplacian. Hence both applications require the approximation of f(A)b, where f(t) = t^(-α/2) and A is sparse. In this thesis we will compare the Lanczos approximation, the shift-and-invert Lanczos approximation, the extended Krylov subspace method, rational approximations and the restarted Lanczos approximation for approximating matrix functions of this form. A number of new and novel results are presented in this thesis. Firstly, we prove the convergence of the matrix transfer technique for the solution of the fractional Poisson equation and we give conditions by which the finite difference discretisation can be replaced by other methods for discretising the Laplacian. We then investigate a number of methods for approximating matrix functions of the form A^(-α/2)b and investigate stopping criteria for these methods. In particular, we derive a new method for restarting the Lanczos approximation to f(A)b. We then apply these techniques to the problem of sampling from a GMRF and construct a full suite of methods for sampling conditioned on linear constraints and approximating the likelihood. Finally, we consider the problem of sampling from a generalised Matern random field, which combines our techniques for solving fractional-in-space partial differential equations with our method for sampling from GMRFs.

The effects of cognitive ageing on the use of complex interfaces

This paper discusses an experiment investigating the effects of cognitive ageing and prior-experience with technology on using complex interfaces intuitively. Overall 37 participants, between the ages of 18 to 83, participated in this study. All participants were assessed for their cognitive abilities and prior-experience with technology. It was anticipated that the Central Executive function (a component of Working Memory) would emerge as one of the important cognitive functions in using complex interfaces. This was found to be the case with the strongest negative correlation occurring between sustained attention (one of the functions of the Central Executive), the time to complete the task and number of errors made by the participants.