PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Evolution of Complex Networks: A Reinforcement Learning Approach Applying Evolutionary Games to Community Structure

Bin Pi, Liang-Jian Deng, Minyu Feng, Matjaž Perc, Jürgen Kurths

arXiv:2506.17925v1cs.SIcs.GT

TL;DR

Existing complex-network studies have not adequately explained community formation from individual game interactions while representing dynamic populations with birth and death. The paper develops a networked evolutionary model combining Q-learning, individual movement in two-dimensional space, and arbitrary individual lifespans, then validates its theory and practical fit through simulations and real data. The analyses identify parameter effects on cooperation, community formation, stability, and community size, while the authors note specific modeling assumptions and tie-formation constraints.

  • Problem

    Existing research falls short of deriving community formation and evolution from game interactions among individuals in dynamic systems.

  • Method

    The model combines networked evolutionary games, Q-learning-based individual movement in two-dimensional space, birth-death dynamics with arbitrary lifespans, and a mapping to high-dimensional network structure.

  • Results

    The theory agrees with simulations, while experiments show cooperative behavior and community evolution, and fits population data and real-network degree distributions.

  • Takeaways & Limitations

    The framework provides a perspective on real-world community development and a basis for studying dynamic population behaviors such as disease spread, cooperation, and synchronization.

  • Takeaways & Limitations

    The model assumes exponential birth timing as an effective representation for independent random events and restricts new ties when individuals had no edge at the previous time.

Abstract

from arXiv · show

Complex networks serve as abstract models for understanding real-world complex systems and provide frameworks for studying structured dynamical systems. This article addresses limitations in current studies on the exploration of individual birth-death and the development of community structures within dynamic systems. To bridge this gap, we propose a networked evolution model that includes the birth and death of individuals, incorporating reinforcement learning through games among individuals. Each individual has a lifespan following an arbitrary distribution, engages in games with network neighbors, selects actions using Q-learning in reinforcement learning, and moves within a two-dimensional space. The developed theories are validated through extensive experiments. Besides, we observe the evolution of cooperative behaviors and community structures in systems both with and without the birth-death process. The fitting of real-world populations and networks demonstrates the practicality of our model. Furthermore, comprehensive analyses of the model reveal that exploitation rates and payoff parameters determine the emergence of communities, learning rates affect the speed of community formation, discount factors influence stability, and two-dimensional space dimensions dictate community size. Our model offers a novel perspective on real-world community development and provides a valuable framework for studying population dynamics behaviors.

1 INTRODUCTION

Complex-network research has developed models for real-world structure and collective behavior, but existing work has not adequately derived community formation from individual game interactions. This paper proposes a reinforcement-learning, birth-death network model that connects individual movement and games to evolving community structures.

  • Background: Complex networks model diverse real-world systems and support analysis of structural dynamics and collective behaviors.Examples include communication, social, biological, and transportation networks, as well as synchronization, propagation, and evolutionary games.
  • Research gap: Existing research has not sufficiently explained how community structures form and evolve from game interactions among individuals.The gap matters because communities are a key feature of complex networks and occur across systems ranging from microorganisms to nations.
  • Proposed approach: The paper introduces a dynamic network model combining individual games, reinforcement learning, and a mapping from two-dimensional positions to high-dimensional network structure.Individuals move according to learned rewards from interactions with network neighbors.
  • Proposed approach: The model incorporates individual birth and death and analyzes steady-state system scale and distribution theoretically and experimentally.The study also compares systems with and without the birth-death process.
  • Validation: The authors validate practicality by fitting country populations and real-network degree distributions and comparing network properties with classical models.The comparisons include network structure, degree distribution, and clustering coefficient.
  • Implications: The study investigates how model parameters affect community emergence and development, offering a framework for structured-population dynamics.The stated applications include evolutionary games, propagation, and synchronization.

2 EVOLVING NETWORKS BASED ON A GAME BETWEEN INDIVIDUALS WITH REINFORCEMENT LEARNING

The model combines birth–death dynamics with reinforcement-learning movement and game-based network evolution. It derives steady-state system-size properties and maps individual locations and interactions into a dynamic network.

  • 2.1 Birth-Death Process of Individual: Individuals enter at exponential rate λ, have generally distributed lifetimes, and form an M/G/∞ queueing system with unbounded population size.The system size N(t) is modeled as a continuous-time Markov chain over {0, 1, 2, · · ·}.
  • 2.1 Birth-Death Process of Individual: The birth–death process yields a limiting system-size distribution and supports derivation of the system’s mean scale, variance, and average individual staying time.These quantities are determined when the input rate λ and death process {G(t), t ≥0} are known.
  • 2.2 Individual Movement Based on Reinforcement Learning: Individuals use ε-greedy Q-learning to choose locations, exploiting the highest-payoff action with probability δ and exploring randomly with probability ε, where ε + δ = 1.The six movement actions are left, right, up, down, stay, and random move.
  • 2.2 Individual Movement Based on Reinforcement Learning: Q-table updates combine immediate payoff with future utility through learning rate η and discount factor γ, allowing action preferences to evolve from experience.A larger γ makes individuals focus more on past experiences rather than immediate payoff.
  • 2.3 Payoff Calculation and Strategy Evolution of Individual: The model converts spatial movement into network ties using interaction history, weight decay, and a threshold σ that determines whether an edge is retained.Existing ties weaken through division by decay factor β and are removed when their updated weight does not exceed σ.

3 SIMULATIONS AND RESULTS

The simulations implement the birth–death and reinforcement-learning network model under multiple lifespan distributions and compare systems with and without population turnover. They use repeated simulations to examine population and network evolution.

  • 3. SIMULATIONS AND RESULTS: The experiments validate theoretical population-size results under different death processes and compare systems with and without birth–death dynamics.Final results are averaged over ten independent simulations.
  • 3.1 Methods: The simulations initialize individuals uniformly across a 10 × 10 grid, set utility tables to zero, and assign initial cooperation or defection with equal probability.The initial network is complete and then evolves as individuals move.
  • 3.1 Methods: Births are generated by a Poisson process, while lifespans are sampled from power-law, uniform, exponential, or lognormal distributions.Power-law lifespans are generated by inverse transformation, while uniform, exponential, and lognormal distributions use corresponding random-generation functions.
  • 3.1 Methods: At each discrete step, individuals move synchronously, play the snowdrift game on the updated network, and synchronously update their Q-tables and strategies.Once a lifespan ends, the individual and its network connections are removed.

Algorithm 1 Monte Carlo Simulation

The Monte Carlo simulation updates reinforcement-learning interactions, network structure, payoffs, and birth-death events over time. Theoretical and experimental individual-count distributions agree closely across death processes.

  • Simulation procedure: The algorithm initializes individual states, Q-tables, strategies, payoffs, birth times, death times, weights, and the network structure.Individuals select actions with an ϵ-greedy policy, observe new states, and update Q-values through game interactions.
  • Simulation procedure: After each update cycle, the simulation advances to whichever occurs first: the next birth or the earliest death.Births and deaths trigger updates to individual lifetimes, weights, and network structure.
  • Stationary population: Theoretical stationary distributions depend on the expected death-process value and input rate λ, with power-law, uniform, exponential, and lognormal cases analyzed.The number of individuals stabilizes around t = 1000 before fluctuating around theoretical values.
  • Validation: The maximum relative error between experimental and theoretical stationary results is 1.569%.Larger systems show greater variance, while distribution skewness differs across death processes and all distributions are thin-tailed.
  • Validation: KL divergence is below 0.045 and JS divergence below 0.012, while Pearson correlation and cosine similarity remain close to 1.These comparisons indicate strong agreement between theoretical and experimental distributions.

3.3 Evolution of Network Cooperation Behaviors

The study evaluates cooperation across payoff parameter r and exploitation rate δ with and without individual birth-death. Lower r favors cooperation in both systems, while δ has a stronger effect without birth-death.

  • Parameter effects: A smaller payoff parameter r favors the emergence and maintenance of cooperation in both systems.Higher r increases defector payoff and decreases cooperator payoff under the snowdrift-game payoff matrix.
  • Birth-death comparison: Without birth-death, a high exploitation rate can promote cooperation at a specific r, unlike the near-uniform δ effect with birth-death.The comparison uses identical parameter settings apart from the presence of the birth-death process.
  • Parameter effects: The heat maps compare cooperation fractions over r ∈ [0, 1] and δ ∈ [0, 1] in systems with and without birth-death.Both panels use learning rate 0.7, discount factor 0.3, and edge weight fading factor 2.

3.4 Emergence and Evolution of Communities

Community formation depends on the birth-death process and on payoff and exploitation parameters. Communities emerge more clearly without birth-death, especially with low r and sufficiently high but not maximal δ.

  • Community emergence: With birth-death, individuals remain evenly distributed and the corresponding network lacks distinguishing community features.Without birth-death, high δ and low r produce clustering and multiple communities over time.
  • Spatial evolution: The study compares individual movement and resulting network structure across four (δ, r) pairs and four time steps, with and without birth-death.The snapshots use (0.8, 0.6), (0.8, 0.2), (0.4, 0.4), and (0.9, 0.4), at times 500, 2000, 3500, and 5000.
  • Parameter effects: A smaller payoff parameter promotes community emergence and maintenance, while larger δ produces earlier and larger communities at fixed r.The comparison contrasts (δ, r) = (0.9, 0.4) with (0.4, 0.4).
  • Community measure: Nc measures the sum of individuals in the four most populated locations, with larger values indicating stronger community structure.The measure is evaluated over the evolutionary process for systems with and without birth-death.
  • Community measure: With birth-death, Nc remains between 30 and 42, whereas without birth-death it can exceed 250 when r < 0.45 and δ < 0.95.The latter corresponds to more than 83% of system individuals self-organizing into communities; δ = 1 performs worse than δ = 0.95.

3.6 Fit of the Proposed Model on Real Data

The model is evaluated against real populations and real network degree distributions. Simulated populations closely match four countries, and generated degree distributions show high similarity to six real networks.

  • Evaluation design: The study fits four country populations using birth-death models with different death distributions and fits six real-network degree distributions using SWBD and SWOBD.The population series span 1960–2022, while the network cases include biological, social, and other real-world networks.
  • Population fitting: The simulated populations closely match the real data and gradually increase before stabilizing.Greenland, Guam, the Slovak Republic, and Cuba are modeled with power-law, uniform, exponential, and lognormal death processes, respectively.
  • Population fitting: Relative errors are 0.96%, 0.48%, 0.71%, and 0.38% for Greenland, Guam, the Slovak Republic, and Cuba, respectively.All four correlation coefficients exceed 98.39%.
  • Network fitting: The network fits use SWOBD for HS-HT and TWITTER-COPEN and SWBD under four death distributions for the remaining real networks.The six cases include HS-HT, TWITTER-COPEN, AVES-WEAVER-SOCIAL, DWT-607, MAMMALIA-DOLPHIN, and NETSCIENCE.
  • Network fitting: Jensen-Shannon divergence does not exceed 0.0997, while cosine similarity is at least 0.7563 across simulated and real degree distributions.These values indicate relatively small differences between generated and real network degree distributions.
  • Overall assessment: The fitting results support consistency between the model and actual population dynamics and real network structures.The paper presents this consistency as evidence of the model’s practical value.

4 ANALYSIS OF THE COMMUNITY STRUCTURES

Community formation depends on learning rate, discount factor, and two-dimensional space dimensions. Higher learning rates accelerate stabilization, larger discount factors undermine sustained formation, and larger spaces produce larger but more numerous communities.

  • Discount factor: Lower discount factors produce sustained community growth, while γ = 0.7, 0.8, and 0.9 produce fluctuations and eventually reduce Nc to approximately 50.For γ = 0.1 and 0.2, Nc increases and plateaus; larger values do not sustain community formation.
  • Space dimensions: Nc increases as the numbers of rows and columns grow, indicating progressively larger communities across the two-dimensional space.The corresponding network snapshots show how community organization changes across spatial dimensions.
  • Space dimensions: Larger two-dimensional spaces enable more communities with fewer individuals in each community.Smaller configurations such as (4, 4) and (6, 6) produce only one community, whereas larger spaces allow more communities to form.

5 MODEL COMPARISONS

The model is compared with a heuristic alternative and classical WS and BA networks. Reinforcement learning supports dynamically changing community structures, while the proposed networks display flexible degree distributions and strong assortativity.

  • Heuristic-model comparison: Reinforcement learning maintains dynamic community evolution, whereas the heuristic model’s state transition ratio rapidly falls to 0 after stabilization.The SWOBD model’s final state transition ratio stabilizes around 0.25, indicating continuing structural evolution.
  • Heuristic-model comparison: The heuristic model lacks memory and learning, so individuals in the same state take identical actions focused on immediate benefits.The reinforcement-learning model instead allows behavioral differences through learning.
  • Classical-network comparison: SWOBD and SWBD with power-law distribution can exhibit irregular, power-law, or normal degree distributions depending on parameter settings.WS and BA networks respectively show normal and power-law degree distributions in the comparison.
  • Classical-network comparison: SWOBD and SWBD with power-law distribution are assortative, with assortativity coefficients of 0.807 and 0.877, compared with -0.082 for BA and -0.035 for WS.The proposed networks show relatively large joint-degree-distribution values near the diagonal.

6 CONCLUSIONS AND OUTLOOKS

The paper proposes a dynamic network model combining individual birth-death processes, evolutionary games, Q-learning, and movement in two-dimensional space. Its analyses address population size, cooperation, community formation, and structural properties, while the authors identify extensions to strategy updates and spatial dimensions.

  • Contributions: The proposed model combines games with Q-learning and individual lifetimes drawn from an arbitrary distribution.The model is designed to study formation mechanisms and structural dynamical behavior in complex networks.
  • Findings: Theoretical population-size results agree with simulations across different death-process distributions, as assessed using relative error and Kullback-Leibler divergence.The paper also examines cooperation, community structures, payoff parameters, and exploitation rates.
  • Implications: The framework is presented as applicable to other games by modifying the payoff matrix and as a basis for studying disease spread, cooperation, synchronization, and other prosocial behaviors.The paper positions the model as a framework for dynamic population behavior and community development.
  • Outlook: Future work includes testing alternative strategy-update rules and extending individual movement from two-dimensional to three-dimensional space.The authors specifically mention best-take-over and Moran-process updates.

(Supplementary Material)

The supplementary material provides theorem proofs, additional figures, and further simulation analyses for several death-process distributions.

  • Supplementary contents: The supplementary material contains proofs for Theorems 1 and 2 and additional figures supporting the main findings.It also includes further simulations and analyses of SWBD with uniform, exponential, and lognormal death distributions.

1 PROOF OF THEOREM 1

Theorem 1 considers a continuous-time Markov chain for system size under an existing expected death-process distribution and limiting probabilities. The proof models arrivals as exponential and lifetimes using a general distribution.

  • Theorem 1 concerns a continuous-time Markov chain N(t) with state space E and an assumed expected death process.
  • New individuals enter at exponentially distributed time intervals with parameter λ, while individual lifetimes follow a general distribution.
  • The limiting probability {π_i} is asserted to exist when the general death distribution has an expectation.
  • The proof describes the system-size process as a non-homogeneous Poisson process under the stated expectation condition.

2 PROOF OF THEOREM 2

Theorem 2 derives expressions for the system's average scale, scale variance, and average individual staying time. The accompanying proof identifies these quantities respectively as an expectation, variance, and average-time calculation based on Theorem 1.

  • Theorem 2 gives an expression for the average scale of the system.
  • It also gives an expression for the variance of the system scale.
  • A further expression gives the average staying time of each individual.
  • The proof identifies average scale as the expectation of Theorem 1's result.
  • The proof separately expresses the system-scale variance and calculates average individual staying time.

3 FURTHER SIMULATION RESULTS

Further simulations examine cooperation, community formation, game generality, and network structure under several birth-death processes. Cooperation is broadly similar across death distributions, while community formation depends strongly on the process and parameter setting, with larger communities reported without birth-death dynamics.

  • Simulation scope: The simulations compare cooperation and community evolution under uniform, exponential, and lognormal death distributions in systems with birth-death dynamics.The section also studies network structure and the effects of payoff and exploitation parameters.
  • Cooperative behavior: Across the three death distributions, cooperation decreases as payoff parameter r increases, while exploitation rate δ has almost no effect on cooperator survival.The reported cooperation-ratio pattern is similar across the distributions.
  • Community formation: The selected parameter snapshots show random individual distributions and no distinct community structure regardless of death-process distribution.The corresponding network structures are presented alongside the two-dimensional evolutionary snapshots.
  • Game comparison: In the stag hunt game, higher exploitation rates δ and lower payoff parameters r′ favor rapid community formation and sustained community evolution.The authors describe the snowdrift game as a special case of a framework extendable by substituting another payoff matrix.
  • Community formation: Uniform and exponential death processes yield relatively small Nc values and no clear parameter-driven community formation, whereas lognormal dynamics can produce communities.For δ = 1.0 and r = 0.1, one community begins forming around t = 2,000 and another around t = 3,500 before stabilization.
  • Birth-death comparison: Communities in systems without birth-death dynamics are larger in number and size than those in the lognormal birth-death system.
  • Network structure: The three generated networks have clustering coefficients of 0.701, 0.676, and 0.671 for uniform, exponential, and lognormal distributions, respectively.Most nodes have relatively small degrees, alongside a few nodes with larger degrees.
Loading 2506.17925v1…