Thesis Defense: Topologies of Complex Networks: Functions and Structures

Lun Li

Abstract:  During the last decade, significant efforts have been made towards improving our understanding of the topological structures underlying complex networks and illuminating some of the intriguing large-scale properties exhibited by these systems. The main focus of these efforts has been on studying the graph-theoretic properties of the corresponding connectivity structures and on developing universal theories and models that transcend system-specific details and describe the different systems well in a statistical sense.

However, in this thesis we argue that for highly engineered systems such as the Internet, these efforts have had very limited success and are in need for corrective actions.  Highly engineered networks are designed for a purpose, and ignoring that aspect or obscuring it with the help of some generic but random mechanism can result in models that are meaningless from an engineering perspective. By accounting in a minimal manner for both the functional requirements and structural features inherent in the design of an engineered system, we propose an alternative, optimization-based modeling approach that highlights the necessary tradeoffs between system performance and the technological and economic constraints that need to be satisfied when designing the system.  Using the router-level topology of an arbitrary Internet Service Provider (ISP) as a test case, we show that our proposed approach yields network models that not only match the large-scale graph-theoretic properties of measured ISP router-level topologies well but are also fully consistent with engineering intuition and networking reality, especially as far as their performance aspects and robustness properties are concerned. In fact, by introducing a performance-related graph metric, we show that our design-inspired network models can be easily distinguished from previously considered probabilistic network models and efficiently achieve the level of performance for which they were designed in the first place.

To better differentiate between different graphs that are identical as far as certain graph statistics (e.g., node degree distribution) are concerned, we introduce a structural metric, the $s$-metric, and demonstrate that it provides new insights into the diversity of graphs constrained by certain common properties and sheds new light on many previously studied graph properties such as the various notions of self-similarity, likelihood, and assortativity. Moreover, to examine the space of graphs that are constrained by certain common properties, we propose a new approach that is based on establishing a link between two graphs if and only if one can be obtained from the other via a local transformation.  We show that the resulting connected space of graphs has a rich and interesting structure and that some properties of the latter can be related to features of the individual graphs in this space (e.g., degree variabilities of a node $g$ in the space of graphs and the $s$-metric for $g$).