Optimization-Based Approaches to Complex Network Topology

Overview:
We propose a novel approach to the study of complex network topology in which we use an optimization framework to model the mechanisms driving network design and growth. While previous methods of topology generation have focused on explicit replication of statistical properties, such as node hierarchies and node degree distributions, our approach provides a framework that reconciles the domain-specific details of vastly different systems with general principles underlying network evolution and growth. By investigating plausible objectives and constraints in the design of actual networks, observed network properties such as certain hierarchical structures and node degree distributions can be understood as the natural by-product of an approximately optimal solution to a network design problem. In short, we advocate here an approach to network topology design, modeling, and generation that is based on the concept of Highly Optimized Tolerance (HOT).

We use the router-level Internet as our principle case study in complex networks in order to illustrate how differences in the assumptions and methodologies of engineering and statistical physics have led to strikingly different conclusions about large-scale network properties, such as robustness to failure and attack. Perhaps most significantly, this work has shown that recently popular models of so-called "scale-free networks" are both inadequate and inaccurate representations of the Internet and that they provide results that are in many ways the opposite of the real network. In particular, the claim that power-law distibutions in node degree imply the existence of a fragile hub-like network core are simply not correct, and therefore the interpretation of the scale-free "Achilles' heel" as a fragile point under attack does not follow. Moreover, this work has demonstrated that the most essential "robust, yet fragile" features of the Internet and other highly evolved systems actually come from aspects that are only indirectly related to network connectivity. While scale-free networks are theoretically fascinating, our belief is that this framework has been misapplied to high-technology (and biological) systems where an iterative design process means that the resulting structure is inherently nonrandom. An unexpected consequence of this work has been the discovery of new graph theoretical insights for scale-free networks, much of which are as yet unexplored.

Publications: Presentations:
Last Updated: August 24, 2005.