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.

Real-World Social Cognition: Context Effects in Face and Threat Processing

As borne out by everyday social experience, social cognition is highly dependent on context, modulated by a host of factors that arise from the social environment in which we live. While streamlined laboratory research provides excellent experimental control, it can be limited to telling us about the capabilities of the brain under artificial conditions, rather than elucidating the processes that come into play in the real world. Consideration of the impact of ecologically valid contextual cues on social cognition will improve the generalizability of social neuroscience findings also to pathology, e.g., to psychiatric illnesses. To help bridge between laboratory research and social cognition as we experience it in the real world, this thesis investigates three themes: (1) increasing the naturalness of stimuli with richer contextual cues, (2) the potentially special contextual case of social cognition when two people interact directly, and (3) a third theme of experimental believability, which runs in parallel to the first two themes. Focusing on the first two themes, in work with two patient populations, we explore neural contributions to two topics in social cognition. First, we document a basic approach bias in rare patients with bilateral lesions of the amygdala. This finding is then related to the contextual factor of ambiguity, and further investigated together with other contextual cues in a sample of healthy individuals tested over the internet, finally yielding a hierarchical decision tree for social threat evaluation. Second, we demonstrate that neural processing of eye gaze in brain structures related to face, gaze, and social processing is differently modulated by the direct presence of another live person. This question is investigated using fMRI in people with autism and controls. Across a range of topics, we demonstrate that two themes of ecological validity — integration of naturalistic contextual cues, and social interaction — influence social cognition, that particular brain structures mediate this processing, and that it will be crucial to study interaction in order to understand disorders of social interaction such as autism.

Incidental Memory of Younger and Older Adults for Objects Encountered in a Real World Context

Effects of context on the perception of, and incidental memory for, real-world objects have predominantly been investigated in younger individuals, under conditions involving a single static viewpoint. We examined the effects of prior object context and object familiarity on both older and younger adults' incidental memory for real objects encountered while they traversed a conference room. Recognition memory for context-typical and context-atypical objects was compared with a third group of unfamiliar objects that were not readily named and that had no strongly associated context. Both older and younger adults demonstrated a typicality effect, showing significantly lower 2-alternative-forced-choice recognition of context-typical than context-atypical objects; for these objects, the recognition of older adults either significantly exceeded, or numerically surpassed, that of younger adults. Testing-awareness elevated recognition but did not interact with age or with object type. Older adults showed significantly higher recognition for context-atypical objects than for unfamiliar objects that had no prior strongly associated context. The observation of a typicality effect in both age groups is consistent with preserved semantic schemata processing in aging. The incidental recognition advantage of older over younger adults for the context-typical and context-atypical objects may reflect aging-related differences in goal-related processing, with older adults under comparatively more novel circumstances being more likely to direct their attention to the external environment, or age-related differences in top-down effortful distraction regulation, with older individuals' attention more readily captured by salient objects in the environment. Older adults' reduced recognition of unfamiliar objects compared to context-atypical objects may reflect possible age differences in contextually driven expectancy violations. The latter finding underscores the theoretical and methodological value of including a third type of objects-that are comparatively neutral with respect to their contextual associations-to help differentiate between contextual integration effects (for schema-consistent objects) and expectancy violations (for schema-inconsistent objects).

Superradiance: exploiting quantum phase transition in the real world

Superradiance (SR), or cooperative spontaneous emission, has been predicted by R. Dicke before the invention of the laser. During the last few years one can see a renaissance of both experimental and theoretical studies of the superradiant phase transition in a variety of media, ranging from quantum dots and Bose condensates through to black holes. Until recently, despite of many years of research, SR has been considered as a phenomenon of pure scientific interest without obvious potential applications. However, recent investigations of the femtosecond SR emission generation from semiconductors have opened up some practical opportunities for the exploitation of this quantum optics phenomenon. Here we present a brief review of some features, advantages and potential applications of the SR generation from semiconductor laser structures

Efficiency Dynamics on Two Coupled Small-World Networks

We investigate the effect of clusters in complex networks on efficiency dynamics by studying a simple efficiency model in two coupled small-world networks. It is shown that the critical network randomness corresponding to transition from a stagnant phase to a growing one decreases to zero as the connection strength of clusters increases. It is also shown for fixed randomness that the state of clusters transits from a stagnant phase to a growing one as the connection strength of clusters increases. This work can be useful for understanding the critical transition appearing in many dynamic processes on the cluster networks.

Recognition of Surface Reflectance Properties from a Single Image under Unknown Real-World Illumination

This paper describes a machine vision system that classifies reflectance properties of surfaces such as metal, plastic, or paper, under unknown real-world illumination. We demonstrate performance of our algorithm for surfaces of arbitrary geometry. Reflectance estimation under arbitrary omnidirectional illumination proves highly underconstrained. Our reflectance estimation algorithm succeeds by learning relationships between surface reflectance and certain statistics computed from an observed image, which depend on statistical regularities in the spatial structure of real-world illumination. Although the algorithm assumes known geometry, its statistical nature makes it robust to inaccurate geometry estimates.