An “edge-reinforced” random walk down to innovation

Empirical studies show that the emergence of novelties follows similar patterns in a wide variety of contexts, including science, knowledge and information, goods and products, language, but also gastronomy and cinema. In particular, a power-law behaviour (the Heaps’ law), originally introduced to describe the number of distinct words in a text document, applies to different contexts with different values of β < 1.

The statistical regularities represent a starting point to get a deeper insight in the phenomenology of innovation. Different theoretical models have been used to reproduce the innovation dynamics in such domains(1). For example, random walks have been used to build exploration models for social annotation, music album popularity, knowledge acquisition, human language complexity and evolution in research interests.

In a study published in Physical Review Letters last week(2) last week, researchers from Queen Mary University of London put forward a mathematical model which uses an Edge-Reinforced Random Walk (ERRW) to mimic how different concepts are explored moving from a concept to an adjacent one in a network, with innovations being represented by the first discovery of nodes.

We introduce a model for the emergence of innovations, in which cognitive processes are described as random walks on the network of links among ideas or concepts, and an innovation corresponds to the first visit of a node. The transition matrix of the random walk depends on the network weights, while in turn the weight of an edge is reinforced by the passage of a walker. The presence of the network naturally accounts for the mechanism of the “adjacent possible,” and the model reproduces both the rate at which novelties emerge and the correlations among them observed empirically,

The adjacent possible is an inspiring metaphor, originally introduced in the framework of biology by Stuart Kauffman. It refers to all those things, ideas, linguistic structures, concepts, molecules, genomes, technological artefacts, etc., that are one step away from what actually exists, and hence can arise from incremental modifications and/or recombination of existing material(1), and more poetically described by Steven Johnson:

a kind of shadow future, hovering on the edges of the present state of things, a map of all the ways in which the present can reinvent itself.

Mathematical illustration of the adjacent possible in terms of a graph that conditionally expands from the situation depicted in (a) to that depicted in (b). Fig 1 in Reference (1)

For each scientific field, an empirical sequence of scientific concepts (S) is extracted from the abstracts of the temporally ordered sequence of papers. The network of relations among concepts is constructed by linking two concepts if they appear in the same abstract. The network is then used as the underlying structure for the ERRW model. The model is tuned to the empirical data by choosing the value of the reinforcement parameter that reproduces the Heaps’ exponent associated to S(2).

Growth of knowledge in science. Fig 3 in Reference (2)

As supported by empirical observations, “walkers” are expected to move more frequently among already known concepts and, from time to time, to discover new “adjacent” nodes. Edge-reinforced random walks produce a co-evolution of the network with the dynamics of the walkers.

In our model, (i) random walkers move over a network with assigned topology and whose edge weights represent the strength of concept associations, and (ii) the network evolves in time through a reinforcement mechanism in which the weight of an edge is increased every time the edge is traversed by a walker, making traversed edges more likely to be traversed again.

According to their authors, the model is able to reproduce the statistical properties observed in real data of innovation processes (i.e. the heaps law), including the correlated nature of exploration trajectories. With the topology of the network being a key ingredient of the model, they hope their framework will be found useful in all cases where the network can be directly reconstructed from data, as in the study of scientific innovations reported in the paper.


(1) Loreto, Vittorio, Vito D. P. Servedio, Steven H. Strogatz, and Francesca Tria. 2017. ‘Dynamics on Expanding Spaces: Modeling the Emergence of Novelties’, January.

(2) Iacopini, Iacopo, Staša Milojević, and Vito Latora. 2018. ‘Network Dynamics of Innovation Processes’. Physical Review Letters 120 (4): 048301.


One comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.