A Caltech Library Service

Network Structure Optimization with Applications to Minimizing Variance and Crosstalk


Barmpoutis, Dionysios (2012) Network Structure Optimization with Applications to Minimizing Variance and Crosstalk. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/ER8Y-ZK49.


This thesis provides a unified methodology for analyzing structural properties of graphs, along with their applications. In the last several years, the field of complex networks has been extensively studied, and it is now well understood that the way a large network is built is closely intertwined with its function. Structural properties have an impact on the function of the network, and the form of many systems has been evolved in order to optimize for given functions. Despite the great progress, particularly in how structural attributes affect the various network functions, there is a significant gap in the quantitative study of how much these properties can change in a network without a significant impact on the functionality of the system, or what the bounds of these structural attributes are. Here, we find and analytically prove tight bounds of global graph properties, as well as the form of the graphs that achieve these bounds. The attributes studied include the network efficiency, radius, diameter, average distance, betweenness centrality, resistance distance, and average clustering. All of these qualities have a direct impact on the function of the network, and finding the graph that optimizes one or more of them is of interest when designing a large system. In addition, we measure how sensitive these properties are with respect to random rewirings or addition of new edges, since designing a network with a given set of constraints may include a lot of trade-offs. This thesis also studies properties that are of interest in both natural and engineered networks, such as maximum immunity to crosstalk interactions and random noise. We are primarily focused on networks where information is transmitted through a means that is accessible by all the individual units of the network and the interactions among the different entities that comprise it do not necessarily have a dedicated mechanism that facilitates information transmission, or isolates them from other parts of the network. Two examples of this class are biological and chemical reaction networks. Such networks suffer from unwanted crosstalk interactions when two or more units spuriously interact with each other. In addition, they are subject to random fluctuations in their output, both due to noisy inputs and because of the random variance of their parameters. These two types of randomness affect the behavior of the system in ways that are intrinsically different. We examine the network topologies that accentuate or alleviate the effect of random variance in the network for both directed and undirected graphs, and find that increasing the crosstalk among different parts reduces the output variance but also contributes to a slower response.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Graph Theory, Extremal Properties, Crosstalk, Stochastic Calculus
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computation and Neural Systems
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Murray, Richard M.
Thesis Committee:
  • Murray, Richard M. (chair)
  • Abu-Mostafa, Yaser S.
  • Burdick, Joel Wakeman
  • Doyle, John Comstock
  • Perona, Pietro
Defense Date:2 December 2011
Record Number:CaltechTHESIS:12102011-161913831
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6749
Deposited By: Dionysios Barmpoutis
Deposited On:06 Jan 2012 22:43
Last Modified:03 Oct 2019 23:53

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page