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.

The Regulation of Sleep and Circadian Rhythms: The Role of Melatonin and Adenosine in Zebrafish

Sleep is a highly conserved behavioral state whose regulation is still unclear. In this thesis I initially briefly introduce the known sleep circuitry and regulation in vertebrates, and why zebrafish is seen as a good model to study sleep-regulation. I describe the existing two-process model of sleep regulation, which posits that the two processes C (circadian) and S (homeostatic) control timing of sleep-wake behavior. I then study the role melatonin plays in the circadian regulation of sleep using zebrafish. Firstly, we find that the absence of melatonin results in a reduction of sleep at night, establishing that endogenous melatonin is required for sleep at night. Secondly, melatonin mutants show a reduction in sleep in animals with no functional behavioral rhythms suggesting that melatonin does not require intact circadian rhythms for its effect on sleep. Thirdly, melatonin mutants do not exhibit any changes in circadian rhythms, suggesting that the circadian clock does not require melatonin for its function. Fourthly, we find that in the absence of melatonin, there is no rhythmic expression of sleep, suggesting that melatonin is the output molecule of process C. Lastly, we describe a connection between adenosine signaling (output molecules of process S), and melatonin. Following this we proceed to study the role adenosine signaling plays in sleep-wake behavior. We find that firstly, adenosine receptor A1 and A2 are involved in sleep- wake behavior in zebrafish, based on agonist/antagonist behavioral results. Secondly, we find that several brain regions such as PACAP cells in the rostral midbrain, GABAergic cells in the forebrain and hindbrain, Dopamine and serotonin cells in the caudal hypothalamus and sox2 cells lining the hindbrain ventricle are activated in response to the A1 antagonist and VMAT positive cells are activated in response to the A2A agonist, suggesting these areas are involved in adenosine signaling in zebrafish. Thirdly, we find that knocking out the zebrafish adenosine receptors has no effect on sleep architecture. Lastly, we find that while the A1 agonist phenotype requires the zfAdora1a receptor, the antagonist and the A2A agonist behavioral phenotypes are not mediated by the zfAdora1a, zfAdora1b and zfAdoraA2Aa, zfAdora2Ab receptors respectively.

Studies on the role of histones in the structure and function of chromatin

Studies on the dissociation of histones from chromatin by increasing concentrations of sodium deoxycholate (DOC) have shown that histrone II is removed at lowest concentrations of DOC, while slightly higher concentrations remove histones III and IV. Still higher concentrations remove histone I.

The complete separation of chromatin and ¹⁴C-DOC by sucrose sedimentation indicated that the binding of DOC to chromatin is readily and completely reversible.

The dissociation of histones from chromatin by increasing concentrations of related cholanic acids and some of their conjugated derivatives were studied. The results suggested that the driving force for the interaction between the cholanic acid anion and histones is the lowering of the activity coefficient of the cholanic acid anion which occurs when it is partially removed from solution by interaction with hydrophobic regions of the positively charged histones.

The role of histones in the structure of chromatin has been studied by comparing the effects of selective removal of histones from chromatin by increasing concentrations of DOC with those caused by NaCl (removes histone I at lowest concentrations, while higher concentrations remove histones II, III, and IV). Properties studied included thermal denaturation, sedimentation velocity, flow dichroism, relaxation times of molecules oriented in a flow field, and the irreversible disruption of a 130 S, cross-linked component of sheared chromatin. The data indicated that none of the structural or chemical parameters with which these properties are correlated show a dependence on the presence of one particular histone fraction.

The template activity (ability to prime a 0.2 M KC1 DNA-dependent RNA synthesis system catalyzed by E. coli RNA polymerase) increases from that of native chromatin (approximately 25 per cent of that pure DNA) to that of pure DNA in a fashion which shows a nearly linear relationship to the amount of histone coverage of the template. The precipitability of partially dehistonized chromatin samples in 0.15 M NaCl shows a large dependence on the presence of histone I.

Connectivity and Function of the Primate Insula

The insula is a mammalian cortical structure that has been implicated in a wide range of low- and high-level functions governing one’s sensory, emotional, and cognitive experiences. One particular role of this region is considered to be processing of olfactory stimuli. The ability to detect and evaluate odors has significant effects on an organism’s eating behavior and survival and, in case of humans, on complex decision making. Despite such importance of this function, the mechanism in which olfactory information is processed in the insula has not been thoroughly studied. Moreover, due to the structure’s close spatial relationship with the neighboring claustrum, it is not entirely clear whether the connectivity and olfactory functions attributed to the insula are truly those of the insula, rather than of the claustrum. My graduate work, consisting of two studies, seeks to help fill these gaps. In the first, the structural connectivity patterns of the insula and the claustrum in a non-human primate brain is assayed using an ultra-high-quality diffusion magnetic resonance image, and the results suggest dissociation of connectivity — and hence function — between the two structures. In the second study, a functional neuroimaging experiment investigates the insular activity during odor evaluation tasks in humans, and uncovers a potential spatial organization within the anterior portion of the insula for processing different aspects of odor characteristics.