One-dimensional small-world graphs (EPI-6, definitions) #
L. Becchetti, A. Clementi, R. Denni, F. Pasquale, L. Trevisan, I. Ziccardi, Percolation and epidemic processes in one-dimensional small-world networks, arXiv:2103.16398 [BCDPTZ22].
A one-dimensional small-world graph on n nodes is the cycle C_n (Mathlib's cycleGraph n
on Fin n) together with random bridges:
SWG(n, q)(Definition 1.1,n ≥ 3): the bridges are the edges of the Erdős–Rényi graphG(n, q). As in EPI-3,G(n, q)isperc ⊤ bwith i.i.d. Bernoulli(q) coinsb ~ coins q, soSWG(n, q)isswg n bwithb ~ coins q.3-SWG(n)(Definition 1.2,n ≥ 4even): the bridges are the edges of a uniformly random perfect matchingM ~ uniformMatching n(a perfect matching of the complete graph in the sense of Mathlib'sSubgraph.IsPerfectMatching), so3-SWG(n)isswg3 n M.
An edge that is both a cycle edge and a bridge is a single edge of the graph (the union of the
edge sets), as in the paper. Bond percolation with parameter p on a sampled graph G is
perc G ω with independent Bernoulli(p) coins ω ~ coins p (EPI-1). The probability of an
event over both the graph and the percolation is written as the iterated expectation
(coins q).expect fun b => (coins p).prob fun ω => … (resp. (uniformMatching n hn).expect),
the probability under the product of the two independent laws.
swgThreshold c = (√(c² + 6c + 1) − c − 1) / (2c) is the critical percolation probability of
SWG(n, c/n) (Theorems 2.1 and 2.4): the root in (0, 1) of c p (1 + p) / (1 - p) = 1, where
c p is the mean number of percolated bridges at a node and (1 + p) / (1 - p) the mean size of
the percolated cycle cluster around a node (the "local cluster", Fact A.4). For 3-SWG(n) the
critical value is 1/2, the root of p ((1 + p) / (1 - p) - 1) = 2 p² / (1 - p) = 1 (§3.2).
Proved here: the algebra of the thresholds (swgThreshold_spec, lt_swgThreshold_iff, …),
existence of perfect matchings for even n (PerfectMatching.nonempty) and the degree bound
swg3_degree_le (3-SWG(n) has maximum degree 3).
Adjacency in the percolated graph is decidable when adjacency in the host graph is.
Equations
- Epidemics.perc.decidableAdj G ω u v = Epidemics.perc.decidableAdj._aux_1 G ω u v
The threshold of SWG(n, c/n) #
The defining equation of p* = swgThreshold c: c p* (1 + p*) = 1 - p*, i.e. the mean
offspring c p (1 + p) / (1 - p) of the exploration of [BCDPTZ22] §3.1 equals 1 at p*.
For c = 1 (one bridge per node on average, as in 3-SWG(n)) the threshold is √2 - 1
([BCDPTZ22] §2.1).
SWG(n, q) #
SWG(n, q) ([BCDPTZ22] Definition 1.1): the one-dimensional small-world graph on
Fin n whose bridges are given by the coins b: the cycle C_n together with the pairs
{u, v} with b s(u, v) = true. With b ~ coins q the bridges form the Erdős–Rényi graph
G(n, q) (perc ⊤ b), and swg n b is distributed as SWG(n, q).
Equations
- Epidemics.swg n b = SimpleGraph.cycleGraph n ⊔ Epidemics.perc ⊤ b
Instances For
3-SWG(n) #
The perfect matchings on V: the perfect matchings of the complete graph on V, in the
sense of Mathlib (Subgraph.IsPerfectMatching; every vertex has exactly one neighbour,
Subgraph.isPerfectMatching_iff).
Equations
Instances For
There are finitely many perfect matchings on a finite type (classical: being a perfect matching is not decidable in general).
Equations
- Epidemics.PerfectMatching.instFintype = { elems := Epidemics.PerfectMatching.instFintype._aux_1, complete := ⋯ }
A perfect matching on V exists when |V| is even (Mathlib's
IsClique.even_iff_exists_isMatching for the clique V of the complete graph).
The uniformly random perfect matching on Fin n, n even ([BCDPTZ22]
Definition 1.2).
Equations
Instances For
3-SWG(n) ([BCDPTZ22] Definition 1.2): the cycle C_n on Fin n together with the
edges of the perfect matching M. With M ~ uniformMatching n hn, swg3 n M is distributed as
3-SWG(n).
Equations
- Epidemics.swg3 n M = SimpleGraph.cycleGraph n ⊔ (↑M).spanningCoe
Instances For
Adjacency in swg3 n M, classically decidable (the matching is a Mathlib subgraph, whose
adjacency is not decidable in general; the value of run does not depend on this choice).
Equations
Every node of the cycle C_n has at most two neighbours.
3-SWG(n) has maximum degree at most 3 ([BCDPTZ22] §1: two cycle neighbours and one
matching partner).