PaperlayerView exact revision on arXiv

Source-linked AI summary

Social contagion models on hypergraphs

Guilherme Ferraz de Arruda, Giovanni Petri, Yamir Moreno

arXiv:1909.11154v1physics.soc-phcond-mat.stat-mech

TL;DR

Hypergraph contagion dynamics require analysis beyond pairwise-network assumptions, particularly to determine the stability and behavior of competing solutions. The paper combines analytical stability analysis with quasi-stationary simulations and finds bistability, hysteresis, and transitions, while interpreting latent heat socially.

  • Problem

    The paper examines how to determine the stability and behavior of multiple contagion solutions on hypergraphs.

  • Method

    The authors analyze solution stability through Jacobians and use a quasi-stationary method to characterize active-state dynamics while avoiding absorption.

  • Results

    The model exhibits a bi-stable region with two possible solutions, including an upper solution that is analytically stable for λ∗ > 0.

  • Takeaways & Limitations

    Latent heat corresponds to the fraction of individuals needed to move between solutions, providing a social interpretation of transitions and possible oscillations.

  • Takeaways & Limitations

    In finite hypergraphs, fluctuations can move the dynamics between solutions and eventually drive the system to the absorbing state ρ = 0.

Abstract

from arXiv · show

Our understanding of the dynamics of complex networked systems has increased significantly in the last two decades. However, most of our knowledge is built upon assuming pairwise relations among the system's components. This is often an oversimplification, for instance, in social interactions that occur frequently within groups. To overcome this limitation, here we study the dynamics of social contagion on hypergraphs. We develop an analytical framework and provide numerical results for arbitrary hypergraphs, which we also support with Monte Carlo simulations. Our analyses show that the model has a vast parameter space, with first and second-order transitions, bi-stability, and hysteresis. Phenomenologically, we also extend the concept of latent heat to social contexts, which might help understanding oscillatory social behaviors. Our work unfolds the research line of higher-order models and the analytical treatment of hypergraphs, posing new questions and paving the way for modeling dynamical processes on these networks.

Appendix B: Analysis of hyperedge activity … 2. Poisson binomial distribution: the general case

The appendix analyzes hyperedge activity through Poisson binomial distributions, showing how structural symmetry yields binomial reductions while heterogeneous general cases resist useful approximations. It also connects these analyses to hypergraph constructions and dynamical group activation.

  • Appendix A: Hypergraph structure: A hypergraph consists of nodes and hyperedges of arbitrary cardinality; graphs and simplicial complexes arise as special structural cases.Graphs correspond to maximum hyperedge cardinality 2, while simplicial complexes include all subsets of hyperedges larger than 2.
  • Appendix A: Hypergraph structure: The analysis uses a hyperstar and a hyperblob as structurally symmetric regular hypergraphs.The hyperstar combines a central node, cardinality-two edges, and one hyperedge containing all nodes; the hyperblob is a random regular hypergraph.
  • Appendix A: Hypergraph structure: More general hypergraphs are generated by fixing the number of hyperedges and sampling their cardinalities from an arbitrary distribution P(|e|).This construction focuses on heterogeneity in hyperedge cardinalities.
  • Appendix A: Hypergraph structure: Exponential cardinality distributions keep group sizes near an average, whereas power-law distributions produce larger variance and can include hyperedges containing all nodes.The power-law heterogeneity may diverge when γ < 3; the study uses γ = 2.25.
  • Appendix B: Analysis of hyperedge activity: The appendix formulates the probability that a given hyperedge is active and distinguishes structurally symmetric Bernoulli cases from the general case.The general framework uses Pn from Eq. 4 or Eq. 5.
  • 1. Bernoulli distribution: induced by structural symmetries: Structural symmetries reduce the Poisson binomial distribution to a binomial distribution for star and homogeneous hypergraphs.In the star case, F(Θ) depends on leaf activity probability yl and N −1 leaves; in the homogeneous case, it depends on y and N.
  • 1. Bernoulli distribution: induced by structural symmetries: Dynamically, p equals yl(t) in star hypergraphs or y(t) in homogeneous hypergraphs, and reaching Θ∗ can activate group spreading.If group spreading is sufficiently fast, it increases p and competes with standard contact spreading.
  • 2. Poisson binomial distribution: the general case: In the general case, heterogeneous connection patterns and arbitrarily distributed hyperedge cardinalities yield unknown yi distributions, limiting Poisson binomial approximations.The approximation is not valid for sufficiently small hyperedges, including the triangles-only simplicial complex model in.

Appendix C: Analysis of a homogeneous hypergraph · 1. Definition

The homogeneous hypergraph’s strong symmetry reduces Eq. 2 to a single equation, which describes a family of structures rather than a quenched formalism. The framework may also capture qualitative behavior when cardinality-2 hyperedges form an Erdős–Rényi network.

  • 1. Definition: Strong symmetry in the homogeneous hypergraph reduces Eq. 2 to a single equation.The homogeneous structure is the one described in section A.
  • 1. Definition: The resulting equation describes a family of structures ranging from lattices to random regular networks.This is why the formalism is not quenched.
  • 1. Definition: The formalism is explicitly not a quenched formalism.Its equation applies across multiple structural realizations.
  • 1. Definition: The represented family includes lattices.Lattices are one endpoint of the structures described by the equation.
  • 1. Definition: The represented family also includes random regular networks.Random regular networks are the other explicitly mentioned structural class.
  • 1. Definition: Cardinality-2 hyperedges may be defined as an Erdős–Rényi network.Under that definition, the equation is expected to capture the network’s qualitative behavior.
  • 1. Definition: The equation would then be expected to capture the qualitative behavior of the Erdős–Rényi network.This expectation concerns qualitative behavior rather than an exact equivalence.

2. Steady-state analysis

The steady-state analysis derives the order parameter under large-system approximations and distinguishes regimes based on F(Θ, p). It recovers the QMF SIS solution on a random regular graph when F(Θ, p) = 0 or λ∗ = 0 and identifies feasible solutions when F(Θ∗, p) = 1.

  • Steady-state assumptions: The analysis imposes dy/dt = 0 and assumes N is sufficiently large but finite.These assumptions define the steady-state approximation.
  • QMF limit: For F(Θ, p) = 0 or λ∗ = 0, the equations recover the QMF SIS solution for a random regular graph.The corresponding expression is given in Eq. C4.
  • Regime F(Θ∗, p) = 1: When F(Θ∗, p) = 1, Eq. C3 is solved using the feasible solution y+, because y− may produce negative values.The order parameter is then expressed in this regime using y+.
  • Order parameter: Combining both solutions yields the order parameter for the analyzed steady-state regimes.The resulting expression is summarized after the two case-specific solutions.
  • Approximation limits: The approximation assumes that F(Θ∗, p) approximates F(Y_i=0) in sufficiently large systems and that individual states are independent.These are the two explicit ideas underlying the approximation.
  • Numerical illustration: Figure 6 displays solutions of equations C7 and C8 for different parameter values (λ, Θ∗).The figure examines how the solutions vary across the specified parameter pairs.

3. Local stability analysis · 4. Critical values

The analysis establishes stability of the relevant fixed-point solutions and identifies a bistable region, while critical points occur when the lower or upper solution crosses the threshold Θ∗. Treating λ as the control parameter yields critical-value relations under fixed δ, λ∗, N, and ⟨k⟩.

  • 3. Local stability analysis: The stability analysis evaluates derivatives near the fixed points ρLower and ρUpper to establish whether those ODE solutions are stable.The solutions ρLower and ρUpper are fixed points of the ODE system of Eq. C1.
  • 3. Local stability analysis: The lower fixed-point solution is stable for parameters above the critical point λ, with the transition condition δ ≥ 1 ⟨k⟩.The derivative is negative in this regime, and the second line of C9 indicates the classical graph-model second-order phase transition.
  • 3. Local stability analysis: The second solution is stable for all λ > 0, δ > 0, λ∗> 0 and ⟨k⟩> 0, whereas y− in Eq. C5 is unstable.The stability conclusion follows from a negative derivative in the regime F(Θ∗, p) = 1.
  • 3. Local stability analysis: Equations C7 and C8 are stable, producing a bi-stable region in which the realized solution depends on the initial condition.Finite-size fluctuations can switch between solutions, but this likelihood decreases with system size and vanishes in the thermodynamic limit.
  • 4. Critical values: Assuming λ is the control parameter, the critical point is calculated while δ, λ∗, N and ⟨k⟩ are kept fixed.More general expressions can be calculated using the same principle.
  • 4. Critical values: Critical points arise when the lower and upper solutions cross the threshold Θ∗, allowing the critical equation to be solved from the closed order-parameter expressions.The crossings are associated respectively with ρLower and ρUpper.
  • 4. Critical values: The critical-value relation could be obtained because the model has a simple form.The passage notes that this relation was obtainable only due to the simplicity of the model.

5. “Latent heat”

The paper defines a social analogue of latent heat as the difference between upper and lower solutions when the spreading rate changes with other parameters fixed. Socially, it represents the fraction of individuals that must be added or removed to shift dynamics between solutions and is tied to first-order transitions.

  • Phase diagram: For the RRN hypergraph with k = 5, δ = 1, and λ∗(|ej|) = log2(|ej|), the latent heat is shown as the difference between the upper and lower solutions, highlighting the hysteresis loop.The phase diagram varies λ and Θ∗ and plots latent heat as the difference between solutions.
  • Definition: Latent heat is defined as the difference between the upper and lower solutions while varying spreading rate λ and fixing δ, λ∗, ⟨k⟩, and Θ∗.This analogy treats the order parameter ρ as proportional to energy and spreading rate λ as analogous to temperature.
  • Phase transitions: The latent-heat concept is intrinsically connected with first-order phase transitions.Its physical interpretation applies at the discontinuity, which depends on Θ∗.
  • Social interpretation: In social terms, latent heat is the fraction of individuals that must be added or removed to move dynamics from one solution to the other.The interpretation concerns switching between the model’s upper and lower solutions.

Appendix D: Analysis of the Hyperstar · 1. Definition

The appendix analyzes social contagion on a hyperstar, consisting of a star graph plus a single hyperedge containing all nodes. Symmetry reduces the dynamics to central- and leaf-node activity probabilities and a corresponding steady-state order parameter.

  • 1. Definition: The hyperstar combines a star graph with a single hyperedge connecting all nodes.This configuration is introduced to obtain analytical insights from the approximation.
  • 1. Definition: Symmetries in this configuration reduce Eq. 2 to a simplified form.
  • 1. Definition: yc and yl denote the probabilities that the central node and a leaf, respectively, are active.
  • 1. Definition: The spreading probabilities are specified through the functions introduced after the reduced equation.
  • 1. Definition: The dependency in Θ is suppressed in Eq. D1, while the superscript Yl = 0 indicates that one leaf is treated as inactive.
  • 1. Definition: For the star hypergraph, the order parameter is reduced to a corresponding expression, followed by a steady-state equation for dyc.

2. Steady-state analysis

The steady-state analysis reduces the dynamics to QMF-like solutions in a sufficiently large finite system and shows that the thermodynamic limit has a vanishing critical point. It also yields two possible order-parameter solutions, with initial-condition dependence indicating bistability and possible hysteresis.

  • Finite-size steady state: For sufficiently large finite N, the steady-state approximation reduces the dynamics to F(Θ, p), whose zero or λ∗ = 0 recovers the QMF SIS solutions on a star graph.The approximation improves as N increases.
  • Finite-size steady state: The finite-star result is compatible with a second-order phase transition, and the approximations of the functions F do not affect it.This confirms the QMF theory for a finite star.
  • Thermodynamic limit: 0: In the thermodynamic limit, the critical point goes to zero, implying a vanishing critical point consistent with mean-field SIS predictions for a star graph.The passage states limN→∞ 1 √N−1 = 0.
  • Bistability and hysteresis: The thermodynamic-limit analysis identifies two possible order-parameter solutions selected by whether ρ(t = 0) is below or at least Θ∗.The first solution matches the star-graph SIS result, whereas the second arises from large hyperedge activation.
  • Bistability and hysteresis: Initial-condition dependence between ρ⋆ and ρ∗ indicates a bi-stable region that may produce a hysteresis loop.The analysis distinguishes finite-N and thermodynamic-limit solutions.

3. Local stability analysis … 6. Finite-size effects: analytical results vs ODE solutions

The paper analyzes local stability through Jacobian eigenvalues across three solution cases, then derives critical values and latent heat while comparing analytical predictions with finite-size ODE solutions. The analysis identifies stable upper solutions and finite-size mismatches near discontinuities.

  • 3. Local stability analysis: The local stability analysis approximates F(Θ∗, p) for large finite systems but restricts the Jacobian analysis because F is discontinuous at Θ∗=p.The derivative of F is undefined at the discontinuity.
  • 3. Local stability analysis: Stability is determined by evaluating the Jacobian eigenvalues for solutions of y_l and y_c obtained previously.The matrix structure depends on the assumed dependency of y_l, with J2 containing the discontinuous part.
  • 3. Local stability analysis: For the upper solution, both Jacobian eigenvalues are negative for any parameters with λ∗>0, proving its stability analytically.This upper solution is identified as a new characteristic of the model.
  • 4. Critical values: In the star case, the critical-value expression is obtained numerically rather than analytically, while δ, λ∗, and N are held fixed and λ is varied.More general critical expressions could be calculated using the same principle.
  • 5. “Latent heat”: The latent heat is analytically expressible but too long, motivating analysis of the quantity in the thermodynamic limit.The latent heat is defined from the difference between the relevant solutions.
  • 6. Finite-size effects: analytical results vs ODE solutions: ODE solutions match the analytical upper and lower solutions far from discontinuities, but a mismatch appears as the threshold increases.The comparison uses the hyperstar phase diagram with N = 103, δ = 1, and λ∗(|e_j|) = log2(|e_j|).

Appendix E: Upper solution: fluctuations and finite size effects … 4. Hysteresis and upper solution particularities

The appendices describe finite-size fluctuations, Monte Carlo and quasi-stationary simulation methods, latent-heat estimation, and computational treatment of hysteresis and upper-solution behavior. They show that stochastic transitions between solutions and the absorbing state complicate finite-system characterization, especially for sawtooth-like upper-solution dynamics.

  • Appendix E: Upper solution: fluctuations and finite size effects: In finite hypergraphs, fluctuations can move the upper solution to the lower solution, the lower solution to the absorbing state or upper solution, and eventually lead to ρ = 0.Because ρ = 0 is the only absorbing state, dynamics in a finite hypergraph ultimately reach it at infinite time.
  • Appendix E: Upper solution: fluctuations and finite size effects: Upper-solution persistence requires the spreading time to satisfy ts < tr, but fluctuations can still drive the dynamics to the absorbing state.The bound concerns the average time to reach ρ ≥ Θ∗ and neglects possible lower-order hyperedges.
  • Appendix E: Upper solution: fluctuations and finite size effects: For a single hyperedge, deactivation causes exponential decay while hyperedge spreading abruptly activates all nodes; sufficiently large λ∗ delays absorption, whereas smaller λ∗ produces oscillations before collapse below Θ∗.The oscillatory regime ends when ρ < Θ∗, after which only annihilation mechanisms remain.
  • 1. Continuous-time simulations: The continuous-time simulations use the Gillespie algorithm, representing active Poisson processes by exponentially sampled event times and executing the earliest scheduled deactivation or spreading event.Inactive processes are assigned infinite event times.
  • 2. Quasi-stationary method (QS): The quasi-stationary method maintains a list of M previously visited active states to avoid absorption and obtain statistically reliable process characterization.The method is used alongside an adaptive version intended to reduce computational cost while retaining reliable measurements.
  • 2. Quasi-stationary method (QS): Bi-stability is characterized by independently initializing the QS method at ρ(t = 0) = 1.00 and ρ(t = 0) = 0.01 to obtain statistics for both solutions.The passage identifies this as the simplest approach for the region with two solutions.
  • 3. Estimating the “latent heat”: Near discontinuities, susceptibility peaks may be finite-size artifacts because strong fluctuations can switch between upper and lower solutions or reach the absorbing state; these events become less likely with increasing system size.The QS method is used to characterize both solutions and estimate latent heat while avoiding this artifact.
  • 4. Hysteresis and upper solution particularities: The simpler phase-diagram algorithm runs Nruns = 50 simulations for tmax = 100 and records only ρ(tmax), reducing cost and making upper-to-lower stochastic switching less likely than with QS.Fixed-time sampling of regular upper-solution cases with a population-sized hyperedge can expose sawtooth-associated variance.

5. Regular hypergraphs: Hyperblob and Hyperstar

Regular hypergraphs exhibit second-order transitions, discontinuities, and fluctuation-driven jumps between lower and upper solutions. Finite-size simulations characterize ρ⋆ but suggest bistability is confined to the thermodynamic limit, while latent-heat estimates are notably accurate for hyperstars.

  • Finite-size behavior: Finite hypergraph simulations characterize only ρ⋆, suggesting that the bi-stable region exists only in the thermodynamic limit.Both homogeneous hypergraphs and hyperstars are expected to exhibit extreme fluctuations.
  • Hyperstar: In hyperstars, the second-order transition is indicated by rounded, increasingly divergent peaks that shift left as system size grows.The order-parameter and susceptibility curves also show a discontinuity whose two one-sided limits differ.
  • Homogeneous hypergraph: The regular homogeneous hypergraph shows susceptibility behavior resembling a random regular graph for larger Θ∗ and increasingly divergent peaks with system size.The order parameter exhibits predicted jumps from the lower to the upper solution.
  • Homogeneous hypergraph: For N = 103, fluctuations before the critical mass can drive the system to the upper solution, especially at Θ∗= 0.1 before the second-order transition.This provides a finite-size example of noise-induced switching between solution branches.
  • Latent heat: Latent-heat estimates and discontinuity points were evaluated for hyperstars and homogeneous hypergraphs across critical-mass thresholds, with remarkably good latent-heat approximation for hyperstars.The estimates used λ∗= log2(|ej|) and varied Θ∗.

6. Heterogeneous cases: Exponential and Power-law cardinality distribution

For exponential and power-law hypergraph cardinality distributions, simulations and numerical solutions reveal bistability and hysteresis, with the exponential structure yielding more accurate and less variable estimates. The lower and upper solutions correspond respectively to lower- and higher-cardinality hyperedge activation, while transient dynamics depend on initial conditions and stochastic factors.

  • Both exponential and power-law structures exhibit a clear bi-stability region, or hysteresis, in simulations and numerical solutions.
  • The critical quantity λU_c is correctly predicted but poorly estimated, whereas the more homogeneous exponential structure provides greater accuracy and slightly lower variance than the power-law structure.
  • The lower solution is associated with activating lower-cardinality hyperedges, while the upper solution is associated with activating higher-cardinality hyperedges.
  • The upper initial condition matches simulations better, while the lower initial condition has greater variance in the time required to reach the meta-state.The time to reach the meta-state depends on both the initial micro-state and stochastic factors.
  • The quasi-stationary method enables precise estimation of critical points and latent heat, and reveals hysteresis in the order parameter and susceptibility.

Appendix G: Implementation details

The appendix describes a C/C++ implementation using GNU Scientific Library routines for random-number generation and ODE integration, with adaptive Runge–Kutta–Fehlberg solving. It also specifies numerical error controls, convergence adjustments, and parallel execution of repeated runs.

  • Software and numerical methods: Simulations and ODE solutions were implemented in C/C++ using standard libraries and the GNU Scientific Library.The library was used for both random-number extraction and ODE integration.
  • Error control and parallelization: ϵabs = 10−4 and ϵrel = 10−3 were imposed relative to the solution yi(t).When convergence difficulties appeared in Fig. 8, the absolute and relative errors were reduced to obtain proper convergence.
  • Error control and parallelization: GNU Parallel was used to run many instances of the same code for both simulations and numerical solutions.This supported parallel execution across repeated computational instances.
Loading 1909.11154v1…