The more I dive into modern graph theory, the more I think we are experiencing a phase transition and papers such as this one, can’t stop me from thinking we are at a turning point.

Let me just give you a short extract of that paper:

From the point of view of the origin of life problem the main conclusions are:

1. The model shows the emergence of an organization where none exists: a small ACS emerges spontaneously by random processes and then triggers the self-organization of the system.
2. A highly structured organization, whose timescale of forming by pure chance is exponentially large (as a function of the size of the system), forms in this model in a very short timescale that grows only logarithmically with the size of the system.

The above paper uses graph theory to model how life formed and shows how simple dynamic models of graph evolution can yield very complex non-linear behaviors (catastrophes, core-shifts, recoveries, etc…) but also, and probably most important, exhibit rapid auto-organization.

To me, the most important concept outlined in the paper is the idea that autocatalytic sets (ACS) bring self-organization. To give you an idea of what an ACS is take a look at this graph:

Figure 1: an autocatalytic set

Here, the blue nodes are the regular nodes and the red ones (the 5 ones in the center, for the colorblind among you) represent the ACS. Here, autocatalytic means, in software engineering terminology, that they are part of a “circular dependency”.

By simply adding and removing nodes and links over time using particular stochastic algorithms, the paper showed evolutions of the autocatalytic factor of the graph (basically, how much circular dependency there is involved) that exhibit highly non-linear behavior.

Figure 2: autocatalytic factor over time

This plot shows the evolution over time (x axis) of the autocatalytic factor of the network (red) and the number of populated nodes (black). The steep climbs represent auto-organization while the steep falls represent catastrophes, some of which lead to the return of an initial phase where the autocatalytic factor is zero and the network does not exhibit circular dependencies.

Now, the paper adopts a poissonian algorithm for the evolution of the network and it’s notorious how poissonian random graphs do not exhibit the same properties of real-life graphs. I wonder what would happen if we applied the same ACS-based analysis over random graphs that are power-law distributed. Hmmm…