Emergence of Cooperation and Interdependence.
Fig. 1
shows a sample run. The same qualitative behavior is seen in each of
several hundred runs performed for p values ranging from 0.00002
to 0.01 and for s = 100, 150, 200. That the ratio of number of
cooperative to destructive links at first remains constant at unity
(statistically) and then increases by more than an order of magnitude is
evidence of the emergence of cooperation. Fig. 1
also shows how a measure of the mutual interdependence of the species
changes with time. This measure, “interdependency,” denoted
, is defined as
≡ (1/s)∑i=1s
di, where di is the
“dependency” of the ith node. di ≡
∑kj|ckj|hki,
where hki is 1 if there
exists a directed path from k to i and 0 otherwise.
di is the sum of (the absolute value of) the strengths
of all links that eventually feed into i along some directed
path. di describes not just the character of the
“neighborhood” of the ith species but also the long-range
connections that affect its dynamics. The increase in
by an order of magnitude is a quantitative measure of the
increase of interdependence of species in the network. The increase in the
total density of links (l+ +
l−)/s is another aspect of the increase of
complexity of the system. Note that in the model selection rewards only
“performance” as measured in terms of relative population; the rules do
not select for higher cooperativity per se. Because a new species
is equally likely to have positive or negative links with other species,
the introduction of novelty is also not biased in favor of cooperativity.
That this behavior is not a consequence of any intrinsic bias in the model
that favors the increase of cooperation and interdependence is evidenced
by the flat initial region of all of the curves.
Autocatalytic Sets. The explanation for the
above behavior lies in the formation and growth of certain structures,
autocatalytic sets (ACSs), in the graph. An ACS is defined as a set of
nodes such that each node has at least one incoming positive link from a
node in the set. Thus an ACS has the property of catalytic closure, i.e.,
it contains a catalyst for each of its members (24–26).
The simplest example of an ACS is a cycle of positive links. Every ACS is
not such a cycle but it can be shown that an ACS must contain a cycle of
positive links (9).
In Fig. 1,
there is no ACS in the graph until n = 1,903. A small ACS (which
happens to be a cycle of positive links between two nodes) appears at
n ≡ n1 = 1,904, exactly where the behavior of
the s1 curve changes. As time proceeds, this ACS
becomes more complex and enlarges until at n ≡
n2 = 3,643, the entire graph becomes an ACS.
l+ and
exhibit an increase and l− a decrease as the
ACS comes to occupy a significant part of the graph. After the ACS first
appears (at n = n1), the set of populated
nodes in the attractor configuration (s1 in number) is
always an ACS (except for certain catastrophic events to be discussed
later), which we call the “dominant ACS.” The spontaneous appearance of a
small ACS at some n = n1, its persistence
(except for catastrophes), and its growth until it spans the graph at
n = n2, are seen in each of the several
hundred runs mentioned earlier. The growth of the ACS across the graph
between n1 and n2 occurs
exponentially (with stochastic fluctuations),
This
expression (derived below) agrees with simulations as shown in Fig.
2.
The average timescale τ
a ≡
n1
for the first appearance of the ACS is given, for sufficiently
small
p, by τ
a ≈
4/(
p2s) (=1,600 for
p = 0.005 and
s = 100). This follows from the fact that the probability that a
graph not containing an ACS will acquire a 2 cycle of positive links at
the next update is
p2s/4, with larger cycles
being much less likely to appear when
ps ≪ 1.
Up to n = n1, the graph has no ACS. It has
chains and trees of positive and negative links and possibly loops
containing negative links. These latter structures are not robust. For
example, consider a chain of two positive links 1→2→3. Because catalytic
links are pointing to node 3, it will do well populationally compared with
nodes 1 and 2. However, because 1 has no incoming catalytic links, its
relative population will decline to zero under Eq. 1,
and it can be picked for replacement in the next graph update. This can
disrupt the chain and hence erode the “well being” of node 3 until
eventually, after some graph updates, the latter can also join the ranks
of the least fit. Species 3 gets eliminated eventually because it does not
feed back into and “protect” species 1 and 2, on whom its “well being”
depends. In a graph without an ACS, no structure is protected from
disruption. Because every node is liable to be replaced sooner or later,
the graph remains as random as the initial graph (we have checked that the
probability distribution of the number of incoming and outgoing links at a
node remains the appropriate binomial for n <
n1). This explains why s1,
l±, and
hover around their initial values.
The picture changes the moment a small ACS appears in the graph. The
key point is that by virtue of catalytic closure, members of the ACS do
well collectively in the population dynamics governed by Eq. 1.
An ACS is a collective self replicator and beats chains, trees, and other
non-ACS structures in the population game, reducing their
Xi to zero when it appears. Thus, because graph update
proceeds by replacing one of the nodes with Xi= 0 (if
present) with a new one, such a replacement being outside the dominant ACS
can cause no damage to the links that constitute the ACS. That is why the
ACS structure, once it appears, is much more robust than the non-ACS
structures discussed earlier. If the new node happens to get an incoming
positive link from the dominant ACS, it becomes part of it. Thus the
dominant ACS tends to expand in the graph as new nodes get attached to it
(8,
9,
15),
and s1 increases. In Δn graph updates, the
average increase in s1, which is the number of added
nodes that will get a positive link from one of the s1
nodes of the dominant ACS, is Δs1 ≈
(p/2)s1Δn, for small p.
This proves Eq. 2.
(Note that the exponential growth described by Eq. 2
is not to be confused with the exponential growth of populations
yi of species that are part of the ACS. Eq. 2
reflects the growth of the ACS across the graph or the increase in the
number of species that constitute the ACS.)
Because the dominant ACS grows by adding positive links from the
existing dominant ACS, the number of positive links increases as the ACS
grows. On the other hand, nodes receiving negative links usually end up
being least fit, hence negative links get removed when these nodes are
eliminated. Which novelty is captured thus depends on the existing
“context”; the network evolves by preferentially capturing links and nodes
that “latch on” cooperatively to the existing ACS and by disregarding
those that do not. The “context” itself arises when the ACS structure
first appears; this event transforms the nature of network evolution from
random to “purposeful” (in this case directed toward increasing
cooperation). Before the ACS appears, nothing interesting happens even
though selection is operative (the least populated species are being
eliminated). It is only after the ACS topological structure appears that
selection for cooperation and complexity begins. Initially the ACS is
small, and its impact on links and interdependency is not visible. As it
grows and comes to occupy a significant part of the graph, the latter
quantities depart significantly from their initial random graph
values.
Inevitability of Autocatalytic Sets. Note that
the appearance of an ACS, although a chance event, is inevitable. For
sp ≪ 1, the probability that a graph not containing a 2 cycle
will acquire one at the next time step is
p2s/4 ≡ q. Because the probability
of occurrence of 3 cycles, etc., is much smaller, the probability
distribution of arrival times n1 is approximated by
P(n1) =
, whose mean
τa is 1/q. Because this probability declines
exponentially after a timescale 1/q, the appearance of an ACS is
inevitable, even for arbitrarily small (but finite) p.
Occasionally in a graph update, s1 can decrease for
various reasons. If the new node forms an ACS of its own with nodes
outside the dominant ACS, and the new ACS has a higher population growth
rate (as determined by Eq. 1)
than the old ACS, it drives the species of the latter to extinction and
becomes the new dominant ACS. Alternatively, the new node could be a
“destructive parasite:” it receives one or more positive links from and
gives one or more negative links to the dominant ACS. Then part or whole
of the ACS may join the set of least-fit nodes. Structures that diminish
the size of the dominant ACS or destroy it appear rarely. For example, in
Fig. 1,
destructive parasites appeared 6 times at n = 3,388, 3,478,
3,576, 3,579, 3,592, and 3,613. In each case, s1
decreased by 1.
Emergence of Structure. At n =
n2, the whole graph becomes an ACS; the entire system
can collectively self replicate despite the explicit absence of individual
self replicators. Such a fully autocatalytic set is a very nonrandom
structure. Consider a graph of s nodes and let the probability of
a positive link existing between any pair of nodes be p*. Such a
graph has on average m* = p*(s − 1) incoming or
outgoing positive links per node. For the entire graph to be an ACS, each
node must have at least one incoming positive link, i.e., each row of the
matrix C must contain at least one positive element. Hence the
probability, P, for the entire random graph to be an ACS is
P
=
probability that every row has at least one positive entry =
[probability that a row has at least one positive
entry]s =
[1 − (probability that every entry of a row is ≤
0)]s =
[1 − (1 −
p*)s−1]s =
[1 − (1 − m*/(s −
1))s−1]s.
For large s and m* ~ O(1),
where
α is positive and
O(1). At
n =
n2,
we find in all our runs that
l+(
n2) ≡
l* is greater
than
s but of order
s, i.e.,
m* ≈
O(1). Thus dynamical evolution in the model via the ACS mechanism
converts a random organization into a highly structured one that is
exponentially unlikely to appear by chance. In the displayed run at
n =
n2, the graph had 117 positive links. The
probability that a random graph with
s = 100 nodes and
m* = 1.17 would be an ACS is given by Eq.
3
to be ≈10
−16.
Such a structure would take an exponentially long time to arise by pure
chance. The reason it arises inevitably in a short timescale in the
present model is the following: a small ACS can appear by chance
quite readily and, once appeared, it grows exponentially fast across the
graph by the mechanism outlined earlier. The dynamical appearance of such
a structure may be regarded as the emergence of “organizational order.”
The appearance of “exponentially unlikely” structures in the prebiotic
context has been a puzzle. That in the present model such structures
inevitably form in a short time may be relevant for the origin of life
problem.
The Self-Organization Timescale in a Prebiotic
Scenario. We now speculate on a possible application to prebiotic
chemical evolution. Imagine the molecular species to be small peptide
chains with weak catalytic activity in a prebiotic pond alluded to
earlier. The pond periodically receives an influx of new molecular species
being randomly generated elsewhere in the environment through tides,
storms, or floods. Between these influxes of novelty, the pond behaves as
a well stirred reactor where the populations of existent molecular species
evolve according to (a realistic version of) Eq. 1
and reach their attractor configuration. Under the assumption that the
present model captures what happens in such a pond, the growth timescale
(Eq. 2)
for a highly structured almost fully autocatalytic chemical organization
in the pond is τg = 2/p in units of the graph
update time step. In this scenario, the latter time unit corresponds to
the periodicity of the influx of new molecular species, hence it ranges
from 1 day (for tides) to 1 year (for floods). Further, in the present
model p/2 is the probability that a random small peptide will
catalyze the production of another (26),
and this has been estimated in ref. 12
as being in the range
10−5–10−10. With p/2
≈ 10−8, for example, the timescale for a highly
structured chemical organization to grow in the pond would be estimated to
be of the order of 106–108 years. It is believed
that life originated on Earth in a few hundred million years after the
oceans condensed. These considerations suggest that it might be worthwhile
to empirically pin down the “catalytic probability” p (introduced
in ref. 26)
for peptides, catalytic RNA, lipids, etc., on the one hand, and explore
chemically more realistic models on the other.
Catastrophes and Recoveries in Network Dynamics.
After n = n2, the character of the
network evolution changes again. For the first time, the least-fit node
will be one of the ACS members. Most of the time elimination of the node
does not affect the ACS significantly, and s1
fluctuates between s and s − 1. Sometimes the least-fit
node could be a “keystone” species, which plays an important
organizational role in the network despite its low population. When such a
node is eliminated, many other nodes can get disconnected from the ACS,
resulting in large dips in s1 and
and subsequently large fluctuations in l+
and l−. These large “extinction events” can be seen in
Fig. 3.
Occasionally, the ACS can even be destroyed completely. The system
recovers on the timescale τg after large extinctions
if the ACS is not completely destroyed; if it is, and the next few updates
obliterate the memory of previous structures in the graph, then again a
time on average τa elapses before an ACS arises, and
the self-organization process begins anew. It may be of interest
(especially in ecology, economics, and finance) that network dynamics
based on a fitness selection and the “incremental” introduction of
novelty, as discussed here, can by itself cause catastrophic events
without the presence of large external perturbations.