Research

Synchronization, Transport, and Response in Information, Social, and Materials Networks

Supported in part by NSF DMR-0426488 under the Information Technology Research Initiative,
the Research Corporation, and Rensselaer.

Supported in part by NSF DMR-0426488 under the Information Technology Research Initiative,

the Research Corporation, and Rensselaer.

Many of our important technological, information, and infrastructure systems can be viewed as a complex network with a large number of components. The network consists of nodes (components of the system) and links connecting the nodes. The links facilitate some form of interaction dynamics between the nodes. Examples (with the processes inducing the interaction between the nodes) include high-performance scalable computing networks (synchronization protocols for massive parallelization), load-balancing schemes (relocating jobs among processors), the Internet (protocols for sending/receiving packets), or the electric power grid (generating/transmitting power between generators and buses). Many of theses systems are autonomous (by design or historical evolution), i.e., they lack a central regulator (including the electric power grid since the deregulation of the 1990's). Thus, fluctuations in the "load" in the respective network (data/state savings or task allocation in parallel simulations, traffic in the Internet, or voltage/phase in the electric grid) are determined by the collective result of the individual decisions of many interacting "agents" (nodes). As the number of processors on parallel architectures increases to hundreds of thousands, grid-computing networks proliferate over the Internet, or the electric power-grid covers, e.g., the North-American continent, fundamental questions on the corresponding dynamical processes on the respective underlying networks must be addressed.
Typically, large fluctuations in the above networks are to be avoided (e.g., for scalability or stability reasons). In the absence of global intervention or control, this is a difficult task. For example, for a distributed parallel simulation scheme to remain scalable, the spread between completion times of tasks performed on different processing nodes of a computer network must remain bounded over time. As another example, for an AC power grid to remain stable, the frequency and the phase of all power generation must remain synchronous within narrow limits; a 2Hz drop below 60Hz would build up sufficient heat in its bearings to destroy the generator.
In addition to the average load in the network, knowing the typical size and the distribution of the extreme fluctuations is of great importance from a system-design viewpoint, since delays or failures are often triggered by extreme events occurring on an individual node. Motivated by the above examples it becomes clear that understanding the stochastic and network effects on the extreme fluctuations in coupled multi-component systems is of great importance for the performance and stability of processing and infrastructure networks.

Snapshots of the fluctuating time horizon in the steady state for 10,000 processing elements (PEs) (a) for the regular one-dimensional lattice topology; (b) for a "small-world" network communication topology for synchronization.

Supported in part by NSF DEB-0342689 under the "Quantitative Environmental and Integrative Biology" focus area

Better understanding the processes that allow one species to invade the habitat of another will help answer fundamental questions in ecology. Just as importantly, understanding the processes of biological invasion to the point of prediction should enhance our capacity to respond effectively to invading species that impose economic problems on agriculture and threaten native biodiversity across North America.
    Ecologists recognize that biological invasion often depends on the way invaders are initially clustered, but current models and approaches poorly approximate consequences of this spatial clustering. In our recent efforts, we considered models where the invasive plant species is introduced into a habitat occupied by a common resident (i.e., native) plant. We assume that introduction of the invader is a rare stochastic process---it occurs randomly and with a low probability---but nonetheless can occur anywhere in the habitat. The introduced species competes with the resident for resources under pre-emptive competition. Our class of models captures essential features of competition between clonal plants. For example, the exotic Crested Wheatgrass, an invasive species found across the northern Great Plains, has substantially reduced diversity of native grasses.
    Our model's main result predicts the decline of the resident species resulting from clusters of invading species. The invasion process begins locally with a random seeding of invader clusters (starting as small "nuclei"), which subsequently can grow, and eventually will occupy the whole system. Invader clusters are initially well separated. As invasion proceeds, invader clusters grow and coalesce, and ultimately drive the resident species extinct. To characterize the process quantitatively, we borrow nucleation theory from the physics, the kind of theory that for example, explains how a crystal grows. In the limit of a low-invader introduction rate and a large habitat, the time-dependent decay of the resident species' density is given by Avrami's law (used elsewhere in the physical sciences to predict the growth of nonliving organisms), also confirmed by large-scale Monte Carlo simulations.
    Avrami's law was originally formulated in the late 1930's to describe how solids transform from one state of matter ("phase") to another as they crystallize, for example. Since then, nucleation theory and Avrami's law have also been applied successfully to predicting chemical reaction rates and formations of magnetic "domains" (zones of magnetism) in materials. To our knowledge, this is the first application of Avrami's law to ecological systems. Our results have general significance since the shape of the species' invading patterns, to a large extent, is independent of the details of how they are the introduced to a small local area. Essentially, only the small introduction rate, the pre-emptive nature of the competition, and a large habitat to be invaded are required to generate the spatially clustered invasion dynamics described by Avrami's law. We currently investigate models, where, analogously to introduction of the invasive species from "external" sources, introduction of an invasive allele is driven by rare mutation. This line of study provides a phenomenological picture for the invasive spread of an advantageous mutation.

Multi-cluster invasion mode (governed by nucleation and growth) in lattice Monte Carlo simulations. White represents empty sites, blue and red correspond to sites occupied by resident and invasive species, respectively. Introduction of the invasive species is a rare stochastic process, occuring where resource is available (empty sites). The resident and invader species compete preemptively and spread via local clonal propagation.