Winter 2004

  CONTENTS:

 From the Director

 In this issue:

 Upcoming Programs

 Recent Programs

 Publications

 Subscribe/Unsubscribe

 Other issues

 IMA Home

From the Director

Networks

Douglas N. Arnold
Doug Arnold,
IMA Director

The concept of a network is among the most frequently recurring in recent IMA programming. Communication networks, power networks, transportation networks, sensor networks, social networks, gene regulatory networks, and protein interaction networks are but a few of the examples that have been explored in recent IMA programs. This should have become clear to me as soon as I arrived at the IMA in 2001. The first two workshops during my tenure here were Hot Topics workshops on Mathematical Opportunities in Large-Scale Network Dynamics and Wireless Networks. And the first technological problem I dealt with as director here was the establishment of the IMA wireless network, which is now a widely used part of the IMA information infrastructure. Just last week it was extended beyond the IMA facilities to the Radisson Hotel used by most of our visitors.

Mathematically a network is graph or digraph--a collection of nodes and connections between them by (possibly directed) edges--often endowed with additional information associated to the edges or nodes, such as a bandwidth capacity linking two routers on the Internet. This simple mathematical abstraction, which harks back at least to Euler, underlies all the examples above. Take for example their role in modeling the spread of disease, the topic of a workshop entitled Networks and the Population Dynamics of Disease Transmission, which took place from November 17-21, 2003 at the IMA. Mathematical epidemiology, a subject that began with Daniel Bernoulli's study of smallpox spread in 1760, was dominated in the 20th century by the SIR (susceptible/infected/recovered) model of Kermack and McKendrick, a system of ODEs that describes the population only in terms of a small number of discrete groups of individuals, assuming "perfect mixing" of the population. Actually the details of the contact networks of individuals play a massive role in disease transmission (perfect mixing is not a very attractive model for sexually transmitted diseases!). The relevant network has as nodes the individuals in the population and edges which describe relevant contacts between them, and understanding this network and incorporating its characteristics into the epidemiological model is crucial to predicting and controlling the spread of disease. There are many impediments to obtaining such understanding. These are big networks with the relevant number of nodes and edges in the thousands, millions, or billions (how large is the largest connected component of the sexual contact network?), and are frequently highly time-dependent. By contrast Euler's Konigsberg bridge graph was static and had four nodes and seven edges. The large dynamic networks in today's applications can rarely be exactly known and statistical and probabilistic methods are necessary. As was clear at the November workshop, which brought together statisticians, graph theorists, epidemiologist, sociologists, and many others, mathematics has many tools--random graph models, measures of degree and degree distribution, of locality, transitivity, correlation, centrality, and similar properties, simulation methods such as Markov Chain Monte Carlo, Bayesian inference methods, etc., etc.--which can help elucidate the different network properties that contribute to disease spread.

graphic for the 3003-2004 IMA Annual Program The wonderful thing about taking a mathematical point of view is the commonality it brings. The same ideas which can be used to model the spread of disease can be applied to the spread of rumors, or technology, or terroristic ideologies. But even more generally, many network modeling, analysis, and simulation ideas apply equally well to systems as diverse as the World Wide Web, which can be modeled as a digraph whose nodes represent web pages and whose directed edges represent hyperlinks, and the protein interaction network of a cell whose nodes represent proteins in the cell and whose directed edges describe various types of chemical interactions between them. The poster image for this years program on Probabilistic and Statistical Methods in Complex Systems, a detail of which appears here (click on it for more), is a reminder of this. While at first glance it seems to be organic and alive, it is actually a visualization of round-trip time measurements on the internet.

The power of mathematical abstraction and its ability to bridge disciplines is at the heart of the workshop Robustness of Complex Systems, which will take place at the IMA February 9-13, 2004. This workshop will bring together Internet researchers, scientists working on a range of different technological networks, biologists and biophysicists, mathematicians, and computer scientists and provide them with the opportunity to compare notes and share insights from engineering theory and practice that can shed new light on biological complexity or from biology that can illuminate existing mysteries associated with the complexity of large-scale engineered networks.

Networks are sure to be a central theme at the IMA for many years to come. Just as recent activity has focussed on merging network theory with mathematical epidemiology, many other mergers cry out for the attention of mathematical scientists. For example, consider the interplay of optimization and networks as in last years workshop on Network Management and Design, or control theory and networks as in the upcoming workshop on Control and Pricing in Communication and Power Networks, or game theory and networks (how does one manage the internet to maximize throughput or fairness or load balance if there are smart hackers willing to tweak their networking hardware and software to gain an advantage?).

And, of course, another kind of network which is at the heart of the IMA's mission: the collaboration network. Best known to mathematicians by the whimsical measure of centrality known as the Erdös number, networks that measure collaboration among scientists are the subject of serious study (e.g., by recent IMA visitor Mark Newman, who published "The structure of scientific collaboration networks" in PNAS a couple of years ago). Just as air transportation has led to connections of geographically distant populations in the networks of disease transmission and forever changed the ways diseases spread across the planet (think SARS), the IMA is fundamentally in the business of fostering the connections of scientifically distant researchers to bring about changes in the advancement of science.