Network Dynamics of Innovation Processes

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. We show this by using synthetic networks and by studying real data sets on the growth of knowledge in different scientific disciplines. Edge-reinforced random walks on complex topologies offer a new modeling framework for the dynamics of correlated novelties and are another example of coevolution of processes and networks.

Figure 1

Edge-reinforced random walks (ERRWs) produce a coevolution of the network with the dynamics of the walkers. At time $t$, the walker is on the red node and has already visited the gray nodes, while the shaded nodes are still unexplored. The widths of edges are proportional to their weights. At time $t+1$, the walker has moved to a neighbor (red) with probability as in Eq. (1), and the weight of the used edge has been reinforced by $\delta w$. At this point, the walker will preferentially go back, although it can also access the set of “adjacent possible” (green).

Figure 2

ERRW on SW networks with $N={10}^5$ and $m=1$. (a) Heaps’s law and associated exponents $\beta$ obtained for different values of reinforcement $\delta w$ on a network with $p=0.02$. (b) Exponent $\beta$ as a function of the reinforcement $\delta w$ for networks with different rewiring probabilities $p$.

Figure 3

Growth of knowledge in science. (a) For each scientific field, an empirical sequence of scientific concepts $\mathcal{S}$ is extracted from the abstracts of the temporally ordered sequence of papers. (b) 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. (c) The model is tuned to the empirical data by choosing the value of the reinforcement $\delta w$ that reproduces the Heaps exponent $\beta$ associated to $\mathcal{S}$.

Figure 4

Correlations among concepts produced by an ERRW ($\delta w=0.01$) on a SW network ($p=0.02$). (a) Frequency distribution of interevent times $\mathrm{\Delta }t$ between consecutive occurrences of the same concept (node in our model). (b) Number $M_l$ of different subsequences of length $l$ as a function of $l$. (c) Normalized entropy of the sequence of visited nodes as a function of $n$, the number of times the nodes have been visited. In each panel, blue circles show average values over 20 different realizations, while triangles and crosses refer to those of (globally and locally) reshuffled sequences.