Source-linked AI summary
Heterogeneous Bond Percolation on Multitype Networks with an Application to Epidemic Dynamics
Antoine Allard, Pierre-André Noël, Louis J. Dubé, Babak Pourbohloul
TL;DR
The paper addresses how network structure and transmission probabilities vary across node types in percolation and epidemic models. It introduces a multitype PGF formalism with arbitrary joint degree distributions and heterogeneous occupation matrix T, deriving phase-transition and component statistics. The framework agrees well with simulations and provides type-specific epidemic outcomes while addressing correlations that iid percolation misses.
Problem
Existing percolation approaches using iid transmission probabilities cannot realistically represent diseases whose transmissibility correlates with direction, coinfection, age, or infectious-period heterogeneity.
Source: §I · p. 1, A. Failure of the iid hypothesis and… · p. 7Method
The paper develops a multitype bond-percolation formalism with arbitrary joint degree distributions and an occupation matrix T whose entries vary by edge direction and endpoint types.
Source: §I · p. 1, §II · p. 2Results
The formalism yields a general percolation threshold and type-resolved component and giant-component statistics, with epidemic predictions showing very good agreement with simulations.
Source: D. Percolation Threshold · p. 5, E. Giant Component · p. 5, C. Numerical Simulations · p. 8Takeaways & Limitations
Node types provide detailed epidemic composition, while heterogeneous occupation probabilities represent correlations that homogeneous iid approaches cannot capture.
Source: §I · p. 1, A. Failure of the iid hypothesis and… · p. 7, C. Numerical Simulations · p. 8
Abstract
from arXiv · showhide
Considerable attention has been paid, in recent years, to the use of networks in modeling complex real-world systems. Among the many dynamical processes involving networks, propagation processes -- in which final state can be obtained by studying the underlying network percolation properties -- have raised formidable interest. In this paper, we present a bond percolation model of multitype networks with an arbitrary joint degree distribution that allows heterogeneity in the edge occupation probability. As previously demonstrated, the multitype approach allows many non-trivial mixing patterns such as assortativity and clustering between nodes. We derive a number of useful statistical properties of multitype networks as well as a general phase transition criterion. We also demonstrate that a number of previous models based on probability generating functions are special cases of the proposed formalism. We further show that the multitype approach, by naturally allowing heterogeneity in the bond occupation probability, overcomes some of the correlation issues encountered by previous models. We illustrate this point in the context of contact network epidemiology.
I. INTRODUCTION
The paper models multitype networks with arbitrary joint degree distributions and heterogeneous, potentially asymmetric edge occupation probabilities. This framework represents mixing patterns and transmission correlations that single-type or homogeneous percolation models overlook.
I. INTRODUCTION
- Existing network models often use one node type, despite constituent differences affecting assortative mixing, communities, and disease propagation.Source: §I · p. 1
- The proposed formalism combines multitype networks with arbitrary joint degree distributions and explicit node properties.Source: §I · p. 1, §II · p. 2
II. MULTITYPE NETWORKS
- Multitype degree distributions encode mixing patterns such as assortativity, while consistency requires matching i →j and j →i edge counts in the large-network limit.Source: §II · p. 2
- The occupation matrix T assigns Tij to i →j edges, need not be symmetric, and can represent directionality implicit in spreading processes.Source: §II · pp. 2–3
III. FORMALISM
The paper develops a probability-generating-function formalism for heterogeneous bond percolation on multitype networks, extending Newman’s framework.
III. FORMALISM
- The formalism uses probability generating functions to describe heterogeneous bond percolation and generalizes Newman’s multitype approach.Source: §III · p. 3
A. Occupied Degree Distribution
The formalism derives occupied-degree and occupied-excess-degree distributions using edge occupation probabilities and multitype degree information. The excess-degree construction accounts for the type at both ends of a followed edge.
A. Occupied Degree Distribution
- The occupied degree distribution counts occupied edges leaving a randomly selected type-i node and is generated by Gi(x; T).Source: A. Occupied Degree Distribution · p. 3
- Average occupied degree by edge type is obtained by differentiating the generating function, yielding occupied edges from type i to type j.Source: A. Occupied Degree Distribution · p. 3
B. Occupied Excess Degree Distribution
- The occupied excess-degree distribution describes remaining occupied edges after reaching a type-j node through an i →j edge.Source: B. Occupied Excess Degree Distribution · p. 3
- Because high-degree nodes are more likely to be reached by an edge, excess-degree probabilities are weighted by the reached node’s degree distribution and depend on both endpoint types.Source: B. Occupied Excess Degree Distribution · p. 3
C. Small Components Size Distribution
Small occupied components are represented with multivariate generating functions that recursively combine branches reached through occupied edges. Unlike earlier one-variable formulations, the resulting expressions retain component composition by node type.
C. Small Components Size Distribution
- In the large-network limit, finite small components are typically treelike, allowing their size distributions to decompose recursively over occupied outgoing edges.Source: C. Small Components Size Distribution · p. 4
- The consistency relation generates the component reached by an i →j edge from the reached node and the distributions of its outgoing branches.Source: C. Small Components Size Distribution · p. 4
- A randomly chosen node’s component-size distribution is generated by combining the component distributions reached along each of its leaving edges.Source: C. Small Components Size Distribution · p. 4
- Unlike previous one-variable PGFs, the multivariate equations generate the composition of small components, including the number of nodes of each type.Source: C. Small Components Size Distribution · p. 4
D. Percolation Threshold
The average size of finite components diverges when det(I −A) approaches zero, establishing the percolation threshold and giant-component onset.
D. Percolation Threshold
- The threshold criterion follows from solving M sets of M^2 equations for the excess-degree quantities governing component growth.The excess-degree terms depend only on the degree distribution and are assembled into the block matrix A.Source: D. Percolation Threshold · pp. 4–5
- For M = 2, the matrix A is represented explicitly through M × M blocks that encode type-specific branching relationships.Source: D. Percolation Threshold · p. 5
- det(I −A) = 0 marks the phase transition where the giant component first appears.The divergence of average finite-component size occurs as det(I −A) → 0.Source: D. Percolation Threshold · p. 5
E. Giant Component
Above threshold, the formalism computes giant-component membership and size by combining forward finite-component probabilities with a transpose-based backward traversal.
E. Giant Component
- Backward traversal uses the transpose of T to determine whether nodes can be reached from the giant component.The backward probability is defined for a type-i node reached by a j →i edge.Source: E. Giant Component · p. 5
- The type-i fraction in the giant component is obtained from the probability that a randomly chosen type-i node does not belong to it.The overall giant-component size is then assembled from the type-specific fractions.Source: E. Giant Component · p. 5
- Asymmetric bond occupation makes the epidemic-occurrence probability P differ from the giant-component size S, whereas symmetric T gives P = S.The difference arises from unequal occupation of i →j and j →i edges.Source: E. Giant Component · p. 5
F. Average Small Components Size
Beyond threshold, the model continues to generate finite-component size distributions and provides a faster route to their moments and covariance structure.
F. Average Small Components Size
- The normalized generating function K(x; T) describes the finite component reached from a randomly chosen node above the percolation threshold.Source: F. Average Small Components Size · pp. 5–6
- Equations (25)–(27) compute finite-component information above threshold without solving the more time-consuming generating-function equations (10)–(12).They reduce to the below-threshold equations when P = 0 and the forward finite-component probability equals 1.Source: F. Average Small Components Size · p. 6
- Second moments yield the covariance matrix of small-component sizes, and analogous iterative equations can compute higher moments.Source: F. Average Small Components Size · p. 6
G. Special Cases
The formalism contains several established models as limiting cases and extends naturally to multipartite and clustered network constructions.
G. Special Cases
- Setting M = 1 recovers the equations of [19], while setting Tij = 1 for all type pairs recovers component results from.Source: G. Special Cases · p. 6
- Choosing Tij = 0 for selected ordered pairs while retaining Tji ≠ 0 recovers semi-directed results such as those in.Source: G. Special Cases · p. 6
- In bipartite networks, the imposed cross-type constraint leads to a phase-transition condition previously obtained in.The type-1 component size under the threshold is likewise recovered by differentiating the generating function and solving the associated equations.Source: G. Special Cases · p. 6
- The giant-component size result from is obtained by setting x2 = 1, while multipartite constraints and projected group networks allow clustering effects as proposed in.Source: G. Special Cases · p. 6
IV. APPLICATION TO EPIDEMIOLOGY
The epidemiological application addresses limits of iid transmission assumptions by representing heterogeneity in individuals and infectious periods through multitype networks and heterogeneous transmissibility.
A. Failure of the iid hypothesis and heterogeneity
- The iid hypothesis assigns the same mean transmission probability to all individual pairs and cannot represent correlations between transmission and individual traits.The limitation applies to heterogeneity in transmissibility, susceptibility, behavior, immunological traits, and infectious-period duration.Source: A. Failure of the iid hypothesis and… · pp. 6–7
- Transmission heterogeneity is empirically associated with direction, co-infection, age, and infectious-period variation across diseases.Examples include higher HIV transmission from male to female, enhanced transmission with STI co-infection, and greater influenza transmissibility among children.Source: A. Failure of the iid hypothesis and… · p. 7
- The formalism addresses these correlations by separating nodes into sufficiently detailed types so type-specific transmission probabilities can be applied.The paper proposes categories such as adults versus children or males versus females, with infectious-period ranges represented as additional node types.Source: A. Failure of the iid hypothesis and… · p. 7
- Finite infectious-period distributions can be represented by partitioning duration into subdomains, assigning each duration type its corresponding transmissibility and population fraction.The same construction is stated to apply to heterogeneous susceptibility.Source: A. Failure of the iid hypothesis and… · p. 7
B. Epidemiological quantities
The epidemiological quantities map multitype percolation outputs to outbreak probabilities, sizes, and composition, while simulations test the predictions across transmissibility values.
B. Epidemiological quantities
- Generating functions give outbreak-size distributions for patient zero of a specified type or any type, together with expected infections by population type.These quantities can evaluate interventions targeting groups such as health care workers or the elderly.Source: B. Epidemiological quantities · p. 7
- The percolation threshold det(I − A) = 0 defines transmissibility values above which outbreaks have a nonzero probability of becoming large-scale epidemics.P and Pi give epidemic probabilities, while S and Si give total and type-specific infected fractions.Source: B. Epidemiological quantities · p. 7
C. Numerical Simulations
- The simulations use N = 10^5-node, two-type networks with power-law total degree and mixing probabilities pij, while the formalism remains general.The chosen joint degree distribution illustrates the approach rather than restricting its applicability.Source: C. Numerical Simulations · p. 7
- Theoretical small-component distributions and average infected counts closely agree with simulations below and above the threshold.Figure 3 compares distributions, while Figure 4 compares type-specific and combined averages; finite-size effects explain disagreement near the threshold.Source: Figure 3 · p. 8, C. Numerical Simulations · p. 8
- γc ≃ 0.1834 marks the epidemic transition obtained by solving det(I − A) = 0 for the simulated transmissibility matrix.The matrix construction varies infectiousness through γ and includes asymmetric transmission between types.Source: C. Numerical Simulations · p. 8
- The model’s epidemic probabilities and relative sizes also agree with simulations, while asymmetric transmissibility can separate epidemic probability P from size S by up to approximately 10%.Type-specific results need not remain proportional as transmissibility changes.Source: C. Numerical Simulations · p. 8
- Type-resolved outcomes allow testing targeted policies by varying transmissibility entries for relevant groups, including age-specific influenza interventions.The paper identifies vaccination, face masks, and hand-washing as examples of strategies that can be compared.Source: C. Numerical Simulations · p. 8
V. CONCLUSION
The paper concludes with a general multitype bond-percolation formalism that captures heterogeneous occupation probabilities and recovers prior PGF-based approaches.
V. CONCLUSION
- The formalism derives exact large-network properties for small components, giant-component reachability and size, type composition, and a general percolation threshold.Iterative equations also provide average numbers of type-i nodes in small components.Source: §V · p. 8
- The framework generalizes existing PGF approaches and can recover multipartite-network results and asymmetric transmission through selected zero entries of Tij.An undirected network can represent one-way type-to-type infection when Tij = 0 but Tji ≠ 0.Source: §V · pp. 8–9
- The figures compare theoretical small-component and giant-component quantities with simulations across γ, using γc as the transition reference.Figure 4 concerns average small-component sizes, whereas Figure 5 concerns giant-component reachability and type-specific fractions.Source: Figure 4 · p. 9, Figure 5 · p. 9