Higher-Order Components Dictate Higher-Order Contagion Dynamics in Hypergraphs

Jung-Ho Kim and K.-I. Goh

Phys. Rev. Lett. 132, 087401 – Published 20 February 2024

Abstract

The presence of the giant component is a necessary condition for the emergence of collective behavior in complex networked systems. Unlike networks, hypergraphs have an important native feature that components of hypergraphs might be of higher order, which could be defined in terms of the number of common nodes shared between hyperedges. Although the extensive higher-order component (HOC) could be witnessed ubiquitously in real-world hypergraphs, the role of the giant HOC in collective behavior on hypergraphs has yet to be elucidated. In this Letter, we demonstrate that the presence of the giant HOC fundamentally alters the outbreak patterns of higher-order contagion dynamics on real-world hypergraphs. Most crucially, the giant HOC is required for the higher-order contagion to invade globally from a single seed. We confirm it by using synthetic random hypergraphs containing adjustable and analytically calculable giant HOC.

Received 15 August 2022
Revised 13 November 2023
Accepted 25 January 2024

DOI:https://doi.org/10.1103/PhysRevLett.132.087401

Physics Subject Headings (PhySH)

Collective behavior in networks

Graph theory Monte Carlo methods

Networks

Authors & Affiliations

Jung-Ho Kim ¹ and K.-I. Goh ^1,2,*

¹Department of Physics, Korea University, Seoul 02841, Korea
²Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095, USA

^*kgoh@korea.ac.kr

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 132, Iss. 8 — 23 February 2024

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Schematic illustration of the $m$ th-order connectivity and the $m$ th-order component.
Reuse & Permissions
Figure 2
(a) Schematic illustration of the higher-order contagion process in a hyperedge. (b),(c) The relative size of the largest $m$ th-order component ( $G_{m}$ ) on the empirical and randomized Coauth-DBLP hypergraph (the number of node $N = 1930 378$ , the number of hyperedge $H = 2467 396$ , mean degree $⟨ k ⟩ = 4.01$ , and mean size $⟨ s ⟩ = 3.14$ ) and contact-high-school hypergraph ( $N = 327$ , $H = 7$ , 818, $⟨ k ⟩ = 55.63$ , $⟨ s ⟩ = 2.33$ ). (d) The relative outbreak size ( $ρ$ ) of higher-order SIR dynamics on Coauth-DBLP hypergraph with the single-seed initial condition. (e) The relative outbreak size of higher-order SIS dynamics on contact-high-school hypergraph with the single-seed initial condition, and (f) with the fully infected initial condition. We ran over minimum $10^{2}$ to maximum $10^{7}$ realizations and averaged over samples only with a relative outbreak size $ρ > 10^{- 3}$ for SIR dynamics and only with active phase samples with minimum $10^{2}$ to maximum $10^{3}$ steps after the relaxation steps minimum $10^{3}$ to maximum $10^{4}$ for SIS dynamics. (g) A schematic illustration of the higher-order contagion process on the first- and second-order components.
Reuse & Permissions
Figure 3
Illustration of the higher-order-connected hypergraph model for $N = 9$ , $H = 3$ , and $S = 4$ . (a) Initially preassign $N = 9$ nodes to $S = 4$ subgroups. For clarity, the number of nodes preassigned to each subgroup is fixed to 2 in this Letter. (b) Each step, select a random node with probability ( $1 - p$ ) or a random subgroup with probability $p$ , and add it to a random hyperedge.
Reuse & Permissions
Figure 4
(a) The relative size of the $m$ th-order component $G_{m}$ in the original and randomized higher-order-connected hypergraph ( $N = 10^{5}$ , $H = 10^{5}$ , $S = 10^{5}$ , $⟨ k ⟩ = 5$ , $⟨ s ⟩ = 5$ , $p = 0.5$ ). (b)–(d) The relative outbreak size ( $ρ$ ) of (b) the higher-order SIR dynamics with the single-seed initial condition, (c) the higher-order SIS dynamics with the single-seed initial condition, (d) the higher-order SIS dynamics with the fully infected initial condition on the higher-order-connected hypergraph. (e)–(h) The phase diagram of the higher-order SIR and SIS dynamics on the original and randomized higher-order connected hypergraph with the single-seed and the fully infected initial conditions. White circles indicate tricritical points, and black circles indicate critical points $λ_{h}^{c}$ in the thermodynamic limit. We ran over minimum 90 to maximum $10^{7}$ realizations and averaged over samples only with a relative outbreak size $ρ > 1 / \sqrt{N}$ for the higher-order SIR dynamics and only with active phase samples with $0.1 \times N$ steps after the relaxation steps $N$ for the higher-order SIS dynamics.
Reuse & Permissions

Physical Review Letters