Emergence and evolution of social networks through exploration of the Adjacent Possible space

The study investigates how social networks emerge and evolve from individual-level interaction mechanisms. The central research question is whether a minimal, microscopic exploration process—formalized via the adjacent possible framework—can simultaneously reproduce the key dynamical and topological properties of real social networks without assuming exogenous heterogeneity (e.g., fixed fitness distributions) or pre-imposed community structures. The context is the rich empirical evidence that human interaction networks display heavy-tailed activity and degree distributions, triadic closure, focal closure, and continuous creation/destruction of links, with time-varying topology affecting global dynamics. Existing models often treat network growth in a way that neglects interaction dynamics, or reproduce only subsets of observed phenomena. This work proposes a model where individuals expand their adjacent possible space of contacts through novel interactions, aiming to jointly capture microscopic decision rules and macroscopic network properties.

Prior research documented heterogeneous activity and degree distributions, homophily and closure mechanisms (triadic and focal), and the time-varying nature of social networks impacting both structure and dynamical processes. Many growth models add nodes stepwise and connect via mechanisms such as copying, rewiring, or preferential attachment (topological, information-based, hierarchical), often producing binary networks and neglecting weights. Some weighted approaches presuppose initial community structures or degree distributions. Dynamic models that allow repeated interactions frequently rely on fixed, data-driven heterogeneous parameters (e.g., node fitness or activity propensity) or focus on specific aspects like activation patterns or partner selection. The adjacent possible concept from evolutionary theory provides a framework where novelties expand the set of reachable possibilities; its recent mathematical formalization via Polya’s urns has explained Zipf’s, Heaps’, and Taylor’s laws in innovation processes. This study leverages that framework to address previous limitations, aiming to endogenously generate both dynamics and topology, including weights, clustering, community structure, and correlations, without imposing exogenous heterogeneity.

Model framework: A multi-agent extension of a modified Polya’s urn model representing exploration of adjacent possible in social interactions.

• Agents and urns: Each agent corresponds to an urn; each ball in an urn bears the ID of another urn (potential alter). A sequence of extractions produces interaction events (i, j) (i initiator, j contacted).
• Reinforcement (exploit): After an event (i, j), add p copies of j to i’s urn and p copies of i to j’s urn, increasing future likelihood of interacting again.
• Novelties and adjacent possible expansion (explore): If i and j interact for the first time, they exchange a memory buffer consisting of v+1 distinct IDs selected from their respective urns by a sharing strategy s. This enlarges each agent’s adjacent possible by introducing new potential alters.
• Entry of new agents: If a called node j has an empty urn (first appearance), it creates v+1 brand-new agents (empty urns) and places one ball for each in its urn; these IDs form j’s initial memory buffer. New agents can only become active after being called by others.
• Event dynamics: At each time step, select the calling urn i proportionally to its urn size (number of balls) and then draw a ball (alter j) from i.
• Parameters: p (reinforcement strength), v (number of novelty IDs shared minus one), and s (memory buffer sampling rule). The relative importance of exploit vs explore is R = p/v. The model generates a full time-ordered sequence of interactions (not only final topology), naturally producing weighted edges.

Exploration strategies s (three used here):

• WSW (Weighted Sample with Withdrawal): sample exactly v+1 distinct IDs from the urn proportionally to their current abundance, withdrawing all balls of an ID once drawn (favours most frequent past alters).
• SSW (Symmetric Sliding Window): each agent maintains a buffer of its last v+1 distinct alters; upon first-contact exchange, both agents share and then update their buffers by adding the new partner and removing the (v+1)th most recent (favours recent alters; symmetric updating).
• ASW (Asymmetric Sliding Window): as SSW but only the initiator updates its buffer after the event (asymmetric updating).

Datasets: Three empirical social systems used for validation and calibration.

• APS co-authorship network: undirected co-authorships across all APS journals (Jan 1970–Dec 2006): 301,236 papers, 184,583 authors, 995,904 edges.
• Twitter Mention Network (TMN): directed mentions among users (Jan–Sep 2008): 536,210 nodes, ~160M events, ~2.6M edges.
• Mobile Phone Network (MPN): call records from one operator in an EU country (Jan–Jul 2008): 6,779,063 operator users (~33M total peers) and 92,784,825 edges (limited observation window).

Calibration and evaluation:

• Simulations: T = 10^6 steps for R ≤ 1; T = 5×10^7–10^7 for R > 1; ten replicas per parameter set.
• Cost function S(p, R, s): sum of squared deviations across eight observables comparing empirical vs synthetic: (i) strengthening exponent β in p_e(k) ≈ (1 + k/c_e)^−β, (ii) exponent q for average degree growth ⟨k(t, t_e)⟩ ∝ (t/t_e)^q, (iii) exponent γ (y in figures) for edge growth E(t) ∝ t^γ, (iv) average clustering coefficient c, and (v–viii) asymptotic fractions of events by edge type: old-open (OO), old-closed (OC), new-open (NO), new-closed (NC).
• Additional comparisons (outside cost): activity and degree distributions, link weight distribution P(w), overlap–weight correlations (Granovetter’s weak/strong ties), modularity and community size distributions (Infomap), core–periphery structure, Taylor’s law of fluctuations in innovation (degree growth across intrinsic time).
• APS subsampling: because co-authorship generates cliques per paper, a 1-link subsampling per paper is used to remove clique-induced biases for certain topological measures.

Analytical insights (Supplementary): R and strategy s primarily govern global observables; absolute p and v affect local topology-related observables. The strengthening behaviour emerges endogenously from the urn dynamics.

• Broad distributions reproduced: The model matches heavy-tailed activity P(a) and degree P(k), and edge growth A(t) ∝ t^γ across APS, TMN, and MPN.
• Strengthening function: Empirically observed p_e(k) = (1 + k/c_e)^−β is recovered by the model across datasets after rescaling by c_e; β is dataset-level, c_e heterogeneous across agents/classes.
• Sublinear degree growth: Average degree grows sublinearly ⟨k(t, t_e)⟩ ∝ (t/t_e)^q with q < 1, consistent with data (e.g., TMN empirical q ≈ 0.56 vs model q ≈ 0.63; distributions of q per class agree well).
• Taylor’s law: Fluctuations in individual innovation rates (new link creation) exhibit α ∼ μ^δ with δ ≈ 1, indicating correlated dynamics; model reproduces this behaviour.
• Heterogeneous exploration rates: Distributions of local Heaps’ exponents α (degree vs intrinsic time) are reproduced, with dataset-specific peaks (APS ~0.9, TMN ~0.7, MPN ~0.4). The model also qualitatively matches P(c_i) for strengthening constants, though synthetic variance is smaller.
• Weighted and topological correlations: The model reproduces P(w), the positive correlation between edge weight and neighbourhood overlap (Granovetter pattern), and the rise-then-fall of clustering c(f_o) when removing low-overlap edges first (community bridges via weak ties). APS requires 1-link subsampling to align with model for these measures.
• Community structure and core–periphery: Community size distributions P(r) and modularity values are well reproduced for APS (including subsampled) and TMN; MPN synthetic modularity is lower, likely due to simulation scale limits. Core–periphery composition within communities is also captured.
• Link dynamics categories: Temporal fractions of events on OO, OC, NO, NC edges match empirical trends (excellent for APS after 1-link subsampling; good for TMN and MPN).
• Parameter insights (best fits):
  • TMN: p = 5, v = 5, R ≈ 1, s = WSW; exploration and reinforcement balanced; users share most frequent past alters (v+1 = 6 IDs).
  • MPN: p ≈ 21, v ≈ 7, R ≈ 3, s = ASW; reinforcement-dominated, sharing of most recent contacts asymmetrically (v+1 = 8 IDs).
  • APS: p ≈ 6, v ≈ 15, R ≈ 0.4, s = SSW; highly exploratory, sharing last contacts symmetrically (v+1 = 16 IDs). APS 1-link subsample: p ≈ 5, v ≈ 15, R ≈ 0.33, s = ASW.
• Novelty propagation: Correlated novelties—new connections expand adjacent possible—are essential to jointly reproduce microscopic strengthening and macroscopic structures without exogenous fitness or manually set modularity.

The findings support the hypothesis that social network growth and dynamics can be understood as an exploration of an evolving adjacent possible, where novelties expand future possibilities and reinforcement biases future interactions. By combining reinforcement (exploit) with novelty exchange (explore), the model endogenously generates the empirically observed strengthening probabilities, sublinear degree growth, heavy-tailed distributions, and topological correlations. It also reproduces community structures and core–periphery organization, linking microscopic rules to meso- and macro-scale features. Dataset-specific optimal parameters reveal differing exploration–exploitation balances: online mentions (TMN) are low-cost and balanced (R ≈ 1; share frequent alters), phone calls (MPN) are reinforcement-dominant with recent-contact sharing (ASW), while scientific co-authorship (APS) is highly exploratory with symmetric recent-contact sharing (SSW). The necessity of APS subsampling highlights the effect of event cliques on topological metrics rather than a model deficiency. Overall, the adjacent possible-driven mechanism offers a unified account of dynamics and structure without imposing heterogeneous node fitness or pre-specified modularity, suggesting broad applicability to social systems and innovation processes.

The study introduces a minimal, microscopic model of social exploration based on the adjacent possible framework that reproduces both the growth and dynamics of social networks. Without assuming exogenous heterogeneity or pre-defined communities, the model captures strengthening behaviour, sublinear degree growth, Taylor’s law, heavy-tailed activity/degree distributions, weighted-topological correlations, modularity, community size distributions, and core–periphery structure across diverse datasets (APS, TMN, MPN). It links individual exploration and reinforcement to emergent meso- and macro-scale organization, providing interpretable parameters that differentiate systems by their exploration–exploitation balance and sharing strategies. Future research directions include incorporating semantic/affinity factors (e.g., homophily), allowing memory exchange beyond first encounters, enhancing variability of strengthening constants, testing predictive capabilities (forecasting future contacts and tie strengths), and scaling simulations to larger systems.

• Semantic/affinity factors (e.g., homophily) are not modeled; ties form independent of shared interests beyond the adjacent possible mechanism.
• Memory buffer exchange occurs only on first encounters; alternative or repeated exchange schemes are not explored.
• Synthetic distributions of strengthening constants c_i show reduced variance compared to empirical data due to urn dynamics constraints.
• APS dataset’s clique structure (multi-author papers) biases clustering and overlap without subsampling; the model matches well after 1-link subsampling.
• For MPN, simulation scale (nodes, time steps) is much smaller than the real system, likely contributing to lower synthetic modularity.
• Entry mechanism restricts agents to appear only when called (no exogenous arrivals), which may limit realism in some contexts.