Evolutionary dynamics of higher-order interactions in social networks

Unai Alvarez-Rodriguez; Federico Battiston; Guilherme Ferraz de Arruda; Yamir Moreno; Matjaz Perc; Vito Latora

Source-linked AI summary

Evolutionary dynamics of higher-order interactions in social networks

Unai Alvarez-Rodriguez, Federico Battiston, Guilherme Ferraz de Arruda, Yamir Moreno, Matjaz Perc, Vito Latora

arXiv:2001.10313v5Jan 28, 2020physics.soc-phcs.SIq-bio.PE

TL;DR

Pairwise network models are poorly suited to cooperation in groups, where group membership and interactions are not uniquely represented. The paper models public goods games on hypergraphs, establishes their well-mixed correspondence, and examines heterogeneous structures and real collaboration data. It finds that group size can shape cooperation and that real scientific communities exhibit an intermediate group size maximizing the reduced synergy factor, while the data-based extraction relies on restrictive assumptions.

Problem
Existing network models primarily represent pairwise interactions and lack a common theoretical foundation for studying cooperation in groups such as public goods games.
Method
The paper studies public goods games on uniform and heterogeneous hypergraphs, including hyperdegree and group-order heterogeneity, and extracts group-size-dependent synergy factors from scientific collaboration data.
Results
The hypergraph public goods game agrees exactly with replicator dynamics in the well-mixed limit without hyperdegree-hyperdegree correlations, and real collaboration data show a maximum reduced synergy factor at intermediate group orders.
Takeaways & Limitations
Higher-order networks provide an explicit framework for studying cooperation in groups and for analyzing how group size and interaction heterogeneity relate to cooperation.
Takeaways & Limitations
Extracting synergy factors from real data assumes the interaction structure is an optimization outcome at a stationary state, and binary contributions do not unambiguously classify cooperators and defectors.

Abstract

from arXiv · show

We live and cooperate in networks. However, links in networks only allow for pairwise interactions, thus making the framework suitable for dyadic games, but not for games that are played in groups of more than two players. Here, we study the evolutionary dynamics of a public goods game in social systems with higher-order interactions. First, we show that the game on uniform hypergraphs corresponds to the replicator dynamics in the well-mixed limit, providing a formal theoretical foundation to study cooperation in networked groups. Secondly, we unveil how the presence of hubs and the coexistence of interactions in groups of different sizes affects the evolution of cooperation. Finally, we apply the proposed framework to extract the actual dependence of the synergy factor on the size of a group from real-world collaboration data in science and technology. Our work provides a way to implement informed actions to boost cooperation in social groups.

Introduction

Classical pairwise networks offer important insights into cooperation but lack a common way to represent and analyze cooperation in groups. The paper introduces higher-order interactions and uses hypergraphs to provide a structured framework for public goods games.

Motivation: Social dilemmas capture the conflict between individually optimal defection and cooperation that maximizes social welfare.Evolutionary game theory provides a mathematical framework for studying this conflict.
Motivation: Cooperation in groups remains difficult to model because classical networks do not uniquely define groups or represent all within-group interactions.This also limits the direct implementation of mechanisms such as reciprocity, image scoring, and reputation.
Higher-order framework: Higher-order interactions allow a single hyperlink to connect more than two individuals, making groups explicit in a hypergraph.A group consists of all players connected by the same hyperlink.
Contribution: The study examines how hubs and groups of different sizes affect cooperation, including how the synergy factor may depend on group size.This extends the analysis beyond networks containing only pairwise interactions.
Public goods game: The public goods game distributes a multiplied contribution among all group members, regardless of each member’s individual investment.Cooperators contribute while defectors do not, creating a social dilemma in groups.
Contribution: The framework generalizes evolutionary games to higher-order interactions in uniform and heterogeneous hypergraphs.It is presented as a theoretical foundation for studying cooperative games in networked groups.

Results

The hypergraph framework distinguishes genuine group interactions from pairwise projections and shows how group size, hyperdegree structure, and order heterogeneity shape cooperation. Applying the framework to APS co-authorship data reveals community-specific optimal collaboration sizes and benefit–cost trade-offs.

Uniform Hypergraphs: Hypergraphs represent group interactions through hyperlinks containing two or more nodes, unlike classical network links connecting pairs.The hyperlink order g is the number of nodes in the group.
Uniform Hypergraphs: The Hypergraph Implementation updates a selected node by comparing its payoff with the highest accumulated payoff in a selected hyperlink, rather than a single neighbour.For g = 2, this expression reduces to the standard graph implementation.
Uniform Hypergraphs: The critical reduced synergy factor rc decreases as hyperlink order g increases, so larger groups require a lower threshold for cooperation in the studied connected hypergraphs.For N = 1000, rc is defined as the lowest r producing a nonzero cooperator fraction.
Uniform Hypergraphs: At fixed reduced synergy factor r, larger groups are better at fostering cooperation in sparse hypergraphs, while increasing hyperlink density moves rc closer to 1.The density comparison follows because the critical number of hyperlinks represents a smaller fraction of possible hyperlinks for larger g.
Hyperdegree-Heterogeneous Hypergraphs: Uniform random hypergraphs agree quantitatively with the replicator approximation, but scale-free hypergraphs increasingly deviate as hyperdegree heterogeneity grows and their critical point approaches r = 1.For preferential random hypergraphs, the transition remains unchanged by heterogeneity and matches the uniform case.
Synergy factor of real games: APS co-authorship data show that the reduced synergy factor peaks at an intermediate group order, with the optimum varying across scientific communities.The maximum occurs at g = 3 for PhysRevLett and g = 5 for PhysRevApplied.
Synergy factor of real games: The APS costs–benefits representation factorizes synergy into benefits that dominate for small groups and costs associated with excessively large collaborations.The fitted parameters β and γ classify scientific communities by these benefit and cost contributions.

Discussion

The paper frames higher-order interactions as a group-based foundation for studying cooperation, while showing how heterogeneity, group size, and real-world structure affect outcomes. Its empirical application depends on assumptions that limit how collaboration data can be interpreted.

Discussion: Higher-order interactions define groups directly through hyperlinks, avoiding arbitrary group constructions in pairwise networks.The framework treats a hyperlink as connecting more than two individuals and uses it to represent a structured group.
Discussion: The public goods game on hypergraphs matches replicator dynamics in the well-mixed limit when hyperdegree-hyperdegree correlations are absent.The paper presents this hypergraph model as a null model for future extensions of cooperation dynamics.
Discussion: Hyperdegree and hyperlink-order heterogeneity expose effects of hubs and group size, including critical scaling and cases where hierarchical structure hinders cooperation.The framework also supports synergy factors that depend systematically on group size.
Discussion: Extracting synergy factors from scientific collaborations assumes that interaction structure results from optimization and reflects a stationary public goods game.The paper identifies this assumption as a limitation that could be tested by models including interaction-topology dynamics.
Discussion: Higher-order models motivate future study of community structure and multilayer networks as additional influences on cooperation.The paper identifies both properties as promising directions for extending the framework.

Methods

The methods construct random hypergraphs, analyze heterogeneous interaction structures, and infer group-size-dependent synergy factors from scientific publication data. The study also documents data, code, and connectivity conditions supporting these analyses.

Methods: Uniform random hypergraphs sample each possible g-tuple with a common probability, but this procedure scales poorly as g increases.The method therefore motivates a fixed-hyperlink-count construction based on combinatorial ordering.
Methods: Fixing the total number of hyperlinks and randomly selecting an integer provides an efficient way to choose hyperlinks from all possibilities.A combinatorial ordering maps integers to hyperlinks and supports unique enumeration.
Methods: The combinatorial construction uses normalized weights d_i and an empirically matched cumulative distribution 1 − (1 − x)^g.The paper reports numerical convergence between the empirical distribution and this expression.
Methods: Connectivity is studied using critical thresholds L_c and k_c; when L exceeds L_c, the hypergraph has a high probability of being connected.The reported threshold relation includes k_c = ln N.
Methods: Power random hypergraphs introduce degree heterogeneity by increasing the exponent used in hyperlink sampling, while scale-free random hypergraphs generate a power-law degree profile.The shared control parameter is μ ∈ [0, 1], with scale-free exponent λ = 1 + 1/μ.
Methods: The publication analysis uses 577886 papers to infer how the reduced synergy factor r(g) depends on scientific collaboration group size.The APS dataset is publicly available, while supporting code is available from the corresponding author upon request.
Methods: The collaboration synergy factor is modeled with benefits growing as a power law and costs decreasing exponentially with group size.The model’s maximum occurs at g = β/γ, and parameters are optimized separately for each journal.

Game Implementations

The graph and bipartite implementations differ in how groups and strategy updates are handled. Simulations show that the bipartite implementation preserves the critical point but relaxes more slowly than the hypergraph implementation.

Graph Implementation: In the graph implementation, randomly selected neighboring nodes play all groups they belong to, accumulate normalized payoffs, and update via a replicator rule.The update probability depends on the payoff difference and a noise-scale factor.
Bipartite Implementation: The bipartite implementation conducts each round within a hypergraph hyperlink but updates each node by comparing its payoff with one randomly selected neighbor.It therefore retains higher-order group structure without simultaneous multi-player updating.
Results: The critical point is the same for the bipartite and hypergraph implementations, but the bipartite implementation has a longer relaxation time and exceeds the replicator limit.This comparison is based on simulations of 1000-node hypergraphs across group sizes.
Figure 6: Figure 6 measures cooperator fraction against synergy factor and relaxation time against synergy factor under specified node, hyperlink, and simulation settings.Panel (a) uses N = 1000, L = L_C, and T = 10^4; panel (b) uses N = 1000 and L = 5L_C.

Creation Algorithm

The creation algorithm orders all possible hyperlinks through recursive star decomposition, allowing random integer selection to map uniquely onto hypergraph hyperlinks.

Creation Algorithm: For N = 5 and g = 3, the potential hyperlinks are partitioned using the identity C_5^3 = C_4^2 + C_3^2 + C_2^2.This creates successive g-star partitions such as {123, 124, 125, 134, 135, 145}, {234, 235, 245}, and {345}.
Creation Algorithm: A random natural number in [1, C_N^g] is assigned to a hyperlink through the star-decomposition ordering.The recursive partitioning is applied until all possible hyperlinks are ordered uniquely.
Creation Algorithm: Recursive star decomposition partitions the complete set of possible hyperlinks into disjoint g-star hypergraphs.The construction preserves equal probability for a specific node to appear in a hyperlink.

Replicator Dynamics for URH

The uniform-hypergraph public goods game is reduced to replicator dynamics through average payoff differences, whose form is independent of group order. The critical condition is r = 1, so cooperation emerges only when R > g.

Replicator Dynamics for URH: Average payoff differences are computed by summing all g −1-node strategy configurations and weighting each hyperlink configuration by strategy probabilities.The resulting dynamics uses normalized average payoffs for defectors and cooperators.
Replicator Dynamics for URH: The payoff difference πD −πC has no explicit dependence on g, making the same formula valid for every hyperlink order.The dynamics can still depend on g through Q.
Replicator Dynamics for URH: The replicator equations are ∂txD = QxDxC and ∂txC = −QxDxC, with their structure independent of g although Q depends on g.This describes the evolution of defector and cooperator fractions over time.
Replicator Dynamics for URH: The stationary states are xD = 0, xC = 0, or Q = 0, with Q = 0 marking the critical point r = 1.The first two states are the trivial phases of the system.
Replicator Dynamics for URH: For random uniform hypergraphs, cooperators emerge only when R > g.This condition follows from the critical reduced synergy factor r = 1.

PRH and SRH

The study compares hyperdegree distributions in Power Random Hypergraphs and Scale-Free Random Hypergraphs across hyperlink orders and heterogeneity levels. The resulting distributions distinguish sharp-decay and power-law regimes and reveal substantially larger hubs than in the uniform case.

PRH and SRH: PRH hyperdegree distributions show sharp decay followed by an intermediate flatter regime, enabling hubs up to 1.5 orders of magnitude larger than in the uniform case.The distributions are evaluated over ensembles of random hypergraphs.
PRH and SRH: SRH hyperdegree distributions follow a power law, appearing as straight lines on log-log plots.The scale-free construction produces the strongest hub heterogeneity among the compared cases.
PRH and SRH: SRH hubs have hyperdegrees 3 orders of magnitude larger than those in the uniform case.This comparison is reported for the heterogeneous distributions generated by the SRH algorithm.
PRH and SRH: Figure 8 plots p_k, the probability of hyperdegree k, against k on logarithmic axes for PRH and SRH across g = 2, 3, 4, 5.Columns represent hyperlink orders, while subplots vary μ from 0 to 1; simulations use N = 1000 and L = L_c.

Replicator Dynamics for Hyperdegree-Heterogeneous Hypergraphs

For hyperdegree-heterogeneous hypergraphs, the mean-field dynamics reduces to the uniform-case dynamics when neighboring hyperdegree distributions match the total distribution, yielding equivalent dynamics when nodes have equivalent neighborhoods.

Replicator Dynamics for Hyperdegree-Heterogeneous Hypergraphs: The analysis conditions the dynamics on node hyperdegree and tracks strategy fractions separately for defectors and cooperators of each hyperdegree.The evolution includes transitions between cooperator and defector states while preserving hyperdegree.
Replicator Dynamics for Hyperdegree-Heterogeneous Hypergraphs: Hyperdegree-hyperdegree correlations encode the probability that players with specified hyperdegrees participate in the same hyperlink.The conditional distributions determine the composition of the remaining group members in the payoff comparison.
Replicator Dynamics for Hyperdegree-Heterogeneous Hypergraphs: The normalization contribution is unchanged from the uniform case because the maximal and minimal payoffs are the same.The simplified expression can then be used in the main derivation.
Replicator Dynamics for Hyperdegree-Heterogeneous Hypergraphs: Under the assumption p(k′|k) = p(k′), the heterogeneous expression reduces to the uniform-case result.This assumption removes dependence on the focal node’s hyperdegree from the neighboring hyperdegree distribution.
Replicator Dynamics for Hyperdegree-Heterogeneous Hypergraphs: The resulting dynamics is equivalent to the uniform-case dynamics when nodes have equivalent neighborhoods.The conclusion applies even when the hypergraphs themselves are heterogeneous.

Order-Heterogeneous Random Hypergraphs

For interactions spanning multiple group sizes, the average payoff difference combines order-specific contributions weighted by their frequencies, while real collaboration data support extracting group-size-dependent synergy factors.

Order-Heterogeneous Random Hypergraphs: The average payoff difference is the sum of the payoff differences for each interaction order, weighted by p_g.The orders range from the minimum g− to the maximum g+ present in the hypergraph.
Order-Heterogeneous Random Hypergraphs: For r_g = αg^β−1, β < 1 places maximal payoffs at the lowest order and minimal payoffs at the highest order.The analysis separates this regime from β ≥ 1 according to the location of the extreme payoffs.
Order-Heterogeneous Random Hypergraphs: For β ≥ 1, maximal payoffs occur at the maximal orders and minimal payoffs at the minimal orders.This reverses the ordering of payoff extremes relative to the β < 1 regime.
Order-Heterogeneous Random Hypergraphs: The heterogeneous-order dynamics follows the same differential equation, relaxation time, and critical-point condition as the uniform case.The critical point is obtained by setting π_D − π_C = 0.
Hypergraphs describing real-world collaborations: For the IETF dataset, the extraction procedure infers hyperdegree distributions from publications by group size, assuming hyperlinks are evenly distributed among nodes.The critical-point condition is then imposed to extract the synergy factor.
Hypergraphs describing real-world collaborations: The IETF fits use power-law benefit and exponential cost terms, with generalized forms also fitted to reduced and unreduced synergy factors.The reported distances quantify agreement between analytical approximations and data-derived synergy factors.
Hypergraphs describing real-world collaborations: In APS collaboration data, reduced synergy factors are extracted from publication author counts across hyperlink orders and compared with analytical fits.Table 1 reports hyperlink counts, average orders, peak-synergy orders, fit parameters, and normalized empirical-fit distances.