and Influence Systems
Algorithms offer a rich, expressive language for modelers
of biological and social systems. They lay the grounds for
numerical simulations and, crucially, provide a powerful
framework for their analysis. The new area of natural algorithms may reprise in the life sciences the role differential
equations have long played in the physical sciences. For this
to happen, however, an “algorithmic calculus” is needed.
We discuss what this program entails in the context of
influence systems, a broad family of multiagent models arising
in social dynamics.
The gradual elevation of “computational thinking” within
the sciences is enough to warm the heart of any computer scientist. Yet the long-awaited dawning of a new age may need
to wait a little longer if we cannot move beyond the world of
simulation and build a theory of natural algorithms with real
analytical heft. By “natural algorithms,” I mean the myriad
of algorithmic processes evolved by nature over millions of
years. Just as differential equations have given us the tools
to explain much of the physical world, so will natural algorithms help us model the living world and make sense of it.
At least this is the hope and, for now, I believe, one of the
most pressing challenges facing computer science.
1. 1. science or engineering?
To dra w a fine line bet ween science and engineering is a fool’s
errand. Unrepentant promiscuity makes a clean separation
neither wise nor easy. Yet a few differences bear mentioning.
If science is the study of the nature we have, then engineering
is the study of the nature we want: the scientist will ask how
the valley was formed; the engineer will ask how to cross it.
Science is driven by curiosity and engineering by need: one
is the stuff of discovery, the other of invention. The path of
science therefore seems more narrow. We want our physical
laws to be right and our mousetraps to be useful. But there
are more ways to be useful than to be right. Engineering can
“negotiate” with nature in ways science cannot. This freedom
comes at a price, however. Any mousetrap is at the mercy of a
better one. PageRank one day will go; the Second Law of thermodynamics never will. And so algorithms, like mousetraps,
are human-designed tools: they are engineering artifacts.
Or are they? Perhaps search engines do not grow on trees,
but leaves do, and a sophisticated algorithmic formalism,
L-systems, is there to tell us how20. It is so spectacularly accurate, in fact, that the untrained eye will struggle to pick out
computer-generated trees from the real thing. The algorithmic modeling of bird flocking has been no less successful.
Some will grouch that evolution did not select the human eye
for its capacity to spot fake trees and catch avian impostors.
Ask a bird to assess your computer-animated flock, they will
snicker, and watch it cackle with derision. Perhaps, but the
oohs and ahhs from fans of CGI films everywhere suggest that
these models are on to something. These are hardly isolated
cases. 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.
1. 2. it is all about language
The triumph of 20th-century physics has been, by and large,
the triumph of mathematics. A few equations scattered on
a single page of paper explain most of what goes on in the
physical world. This miracle speaks of the organizing principles of the universe: symmetry, invariance, and regularity—
precisely the stuff on which mathematics feasts. Alas, not all
of science is this tidy. Biology = physics + history; but history
is the great, unforgiving symmetry breaker. 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, scientifically speaking,
from planets orbiting the sun in orderly fashion to unruly
slime molds farming bacterial crops. Gone are the symmetry, invariance, and clockwork regularity of astronomy: what
we have is, well, sludge. But the sludge follows a logic that
has its own language, the language of natural algorithms.
The point of departure with classical mathematics is
indeed linguistic. While differential equations are the native
idiom of electromagnetism, no one believes that cancer has
its own “Maxwell’s equations.” Yet it may well have its own
natural algorithm. The chain of causal links, some deterministic, others stochastic, cannot be expressed solely in the
language of differential equations. It is not just the diversity
of factors at play (genetic, infectious, environmental, etc.);
nor is it only their heterogeneous modes of interaction. It is
also the need for a narrative of collective behavior that can
be expressed at different levels of abstraction: first-princi-ples; phenomenological; systems-level; and so on. The issue
is not size alone: the 3-body problem may be intractable but,
through the magic of universality, intricate phase transitions
among 1030 particles can be predicted with high accuracy.
The promise of agent-based natural algorithms is to deliver
tractable abstractions for descriptively complex systems.
This paper is based on “Natural Algorithms,” which
was published in the Proceedings of the 20th Annual
ACM-SIAM Symposium on Discrete Algorithms, 2009, and