Natural Algorithms and Influence Systems

Bernard Chazelle (acm) (google)

Eugene Higgins Professor of Computer Science
Princeton University

If you’re going to remember one(?) thing:

Think of influence systems as a brand of networks that perpetually rewire themselves emergently – a broad family of multiagent models arising in social dynamics. The idea is to reach beyond numerical simulation to analyze the structure and interactions of biological systems. This article focuses on how algorithmic ideas can enrich our understanding of nature. Examples of in uence systems include the Ising model, neural nets, Bayesian social learning, protein-protein interaction networks, population dynamics, etc.

Overview:

By “natural algorithms,” I mean the myriad of algorithmic processes evolved by nature over millions of years. Just as dierential equations have given us the tools to explain much of the physical world, so natural algorithms will help us model the living world and make sense of it.

Natural algorithms are quickly becoming the language of choice to model biological and social processes. And so algorithms, broadly construed, are both science and engineering.

Instead of identical particles subject to the same forces, the life sciences feature autonomous agents, each one with its own idea of what laws to obey. It is a long way, scientically speaking, from planets orbiting the sun in orderly fashion to unruly slime molds farming bacterial crops.

What is complexity? Such is the appeal of the word “complexity” that it comes in at least four distinct flavors.

• Semantic: What is hard to understand. For 99.99% of mankind, complex means complicated.
• Epistemological: What is hard to predict. An independent notion altogether: complex chaotic systems can be simple to understand while complicated mechanisms can be easy to predict.
• Instrumental: What is hard to compute, the province of theoretical computer science.
• Linguistic: What is hard to describe. Physics has low descriptive complexity|that’s part of its magic. By contrast, merely specifying a natural algorithm may require an arbitrarily large number of variables to model the diversity present in the system. To capture this type of complexity is a distinctive feature of natural algorithms.

A few words about our agent-based approach. Consider the diusion of pollen particles suspended in water. A Eulerian approach to this process seeks a dierential equation for the concentration c(x; t) of particles at any point x and time t. There are no agents, just density functions evolving over time [18]. An alternative approach, called Lagrangian, would track the movement of all the individual particles and water molecules by appealing to Newton’s laws. Given the sheer number of agents, this line of attack crashes against a wall of intractability. One way around it is to pick a single imaginary self-propelled agent and have it jiggle about randomly in a Brownian motion. This agent models a typical pollen particle – typical in the “ergodic” sense that its time evolution mimics the space distribution of countless particles caught on film in a snapshot. Scaling plays a key role: our pollen particles indeed can be observed only on a time scale far larger than the molecular bumps causing the jiggling. Luckily, Brownian motion is scale-free, meaning that it can be observed at any scale. As we shall see, the ability to express a dynamical process at different scales is an important feature of influence systems.
The strength of the Eulerian approach is its privileged access to an advanced theory of calculus. Its weakness lies in two commitments: global behavior is implied by innitesimal changes; and every point is subject to identical laws. While largely true in physics, these assumptions break down in the living world, where diversity, heterogeneity, and autonomy prevail. Alas, the Lagrangian answer, agent-based modeling, itself suffers from a serious handicap: the lack of a theory of natural  algorithms.