Source-linked AI summary
Network dynamics of innovation processes
Iacopo Iacopini, Staša Milojević, Vito Latora
TL;DR
The paper addresses how new ideas emerge and become correlated, modeling cognitive exploration as an edge-reinforced random walk on a network of concepts. The model reproduces novelty rates and correlations reported in empirical innovation sequences, including scientific knowledge growth.
Problem
The paper asks how novelties emerge and trigger further discoveries, a question the authors describe as fundamental to understanding creative processes and innovation.
Source: p. 1Method
The model represents ideas as nodes in a fixed network and uses an edge-reinforced random walk whose movement depends on edge weights that change with the walk.
Source: pp. 1–2Results
The model reproduces empirical novelty rates and correlations, and tuning reinforcement on small-world networks spans Heaps’ exponents from 0 to 1.
Source: pp. 2–4Takeaways & Limitations
The authors conclude that coevolving network weights and random walks reproduce observed innovation-process properties, with network topology key to the framework.
Source: p. 4The model assumes the graph has no self-loops, so the walker changes position at every time step.
Source: p. 2
Abstract
from arXiv · showhide
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.
NULL MODELS: RESHUFFLING THE SEQUENCES
The supplemental null models reshuffle exploration sequences in two ways: one destroys sequence correlations but changes novelty rates, while the other preserves the discovery schedule.
NULL MODELS: RESHUFFLING THE SEQUENCES
- Global reshuffling destroys sequence correlations but also changes the rate at which new concepts appear, ultimately changing the Heaps’ exponent.This makes it a null model that does not preserve the novelty rate.Source: NULL MODELS: RESHUFFLING THE SEQUENCES · p. 6
- Local reshuffling preserves the novelty rate by rearranging concepts only after their first appearance.A concept cannot be moved earlier than its actual discovery time.Source: NULL MODELS: RESHUFFLING THE SEQUENCES · p. 6
- The local null model therefore retains the discovery schedule while testing sequence correlations.It reshuffles sequence elements only after each concept has first appeared.Source: NULL MODELS: RESHUFFLING THE SEQUENCES · p. 6
CORRELATIONS PRODUCED BY ERRWS ON REAL NETWORKS
The authors test ERRWs on empirical concept networks from scientific disciplines, tuning reinforcement to match each field’s Heaps’ exponent and comparing sequence correlations with reshuffled null models.
CORRELATIONS PRODUCED BY ERRWS ON REAL NETWORKS
- For each scientific field, the reinforcement parameter was tuned so ERRW sequences matched the empirical Heaps’ exponent.The study examines correlations in sequences generated on real networks extracted from relevant concepts in scientific fields.Source: CORRELATIONS PRODUCED BY ERRWS ON REAL… · p. 6
- The real-network sequences were assessed using entropy, distinct subsequences of length l, and inter-event-time distributions.The same measures were used to study ERRWs on synthetic small-world networks.Source: CORRELATIONS PRODUCED BY ERRWS ON REAL… · p. 6
- Comparisons with two reshuffling null models confirm correlated sequences, while comparisons with ERRWs on small-world networks support small-world topology as a good model choice.The passage reports both comparisons as findings of the real-network analysis.Source: CORRELATIONS PRODUCED BY ERRWS ON REAL… · p. 6
CORRELATIONS PRODUCED BY ERRWS ON SYNTHETIC NETWORKS
The supplemental analysis examines ERRW sequence correlations across small-world network link probabilities and reinforcement settings, comparing results with reshuffled null models.
CORRELATIONS PRODUCED BY ERRWS ON SYNTHETIC NETWORKS
- The supplemental analysis varies reinforcement from δw = 0.001 to δw = 1 on small-world networks with N = 10^6 and p = 0.001, 0.01, or 0.1.It reports average sequence entropy and inter-event-time distributions for these settings.Source: CORRELATIONS PRODUCED BY ERRWS ON… · p. 6
- For each setting, the entropy and inter-event-time curves are compared with the corresponding global and local reshuffling null models.These are the same null-model procedures defined for the supplemental analysis.Source: CORRELATIONS PRODUCED BY ERRWS ON… · p. 6
- The analysis covers three small-world link probabilities: p = 0.001, p = 0.01, and p = 0.1.Each probability is considered across the stated reinforcement settings.Source: CORRELATIONS PRODUCED BY ERRWS ON… · p. 6
THE EFFECT OF THE AVERAGE DEGREE ON THE REINFORCEMENT
The analysis relates reinforcement to the Heaps’ exponent across networks with different average degrees, finding that greater degree requires stronger reinforcement to maintain the same exponent.
THE EFFECT OF THE AVERAGE DEGREE ON THE REINFORCEMENT
- The analysis relates β to δw using Erdős-Rényi graphs with N = 10^5 and average degree ⟨k⟩ from 6 to 80.Each curve in Figure S4 corresponds to a different average degree.Source: THE EFFECT OF THE AVERAGE DEGREE ON… · p. 6
- Supplementary small-world plots examine entropy and inter-event-time distributions across link probabilities and reinforcement settings.The curves are compared with globally and locally reshuffled sequences.Source: Figure S2 · p. 7, Figure S3 · p. 8
- Higher average degree requires stronger reinforcement δw to produce the same Heaps’ exponent.The authors explain that a reinforced edge is less likely to be selected among the more choices available at a high-degree node, favoring new links and higher β.Source: THE EFFECT OF THE AVERAGE DEGREE ON… · p. 8
COMPARING ERRWS TO THE NETWORK VERSION OF THE URN MODELS
The basic urn model’s next-draw probabilities depend on how often each color has appeared, not the order of draws. Unlike that model, ERRW probabilities depend on the trajectory’s order; semantic triggering adds correlations to urn models through labels and an extra parameter.
COMPARING ERRWS TO THE NETWORK VERSION OF THE URN MODELS
- ERRW’s next-node probability depends on the precise order of visited nodes, whereas the basic urn model’s color probability depends on color counts, not draw order.Two urn sequences with the same color counts yield identical urn contents and probabilities at t = 6, despite different draw orders.Source: COMPARING ERRWS TO THE NETWORK VERSION… · pp. 8–9
- The urn model with semantic triggering adds semantic labels and parameter η to produce correlated sequences; ERRW needs neither because correlations emerge from walker-network co-evolution.Source: COMPARING ERRWS TO THE NETWORK VERSION… · p. 10
- The urn-to-network mapping is exact only for η = 1, the uncorrelated basic urn model; for η ≤ 1 with semantic triggering, it is not one-to-one.The η = 1 case corresponds to a fully connected network, while network moves otherwise are restricted to a node’s neighbors.Source: COMPARING ERRWS TO THE NETWORK VERSION… · p. 10