Documentation

Epidemics.SmallWorldDefs

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:

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).

@[implicit_reducible]
instance Epidemics.perc.decidableAdj {V : Type u_1} (G : SimpleGraph V) [DecidableRel G.Adj] (ω : Sym2 V → Bool) :

Adjacency in the percolated graph is decidable when adjacency in the host graph is.

Equations

The threshold of SWG(n, c/n) #

noncomputable def Epidemics.swgThreshold (c : ℝ) :

The critical percolation probability of SWG(n, c/n) ([BCDPTZ22] Theorems 2.1 and 2.4): p* = (√(c² + 6c + 1) − c − 1) / (2c).

Equations
Instances For
    theorem Epidemics.swgThreshold_spec {c : ℝ} (hc : 0 < c) :

    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*.

    theorem Epidemics.swgThreshold_pos {c : ℝ} (hc : 0 < c) :

    p* > 0.

    theorem Epidemics.swgThreshold_lt_one {c : ℝ} (hc : 0 < c) :

    p* < 1.

    theorem Epidemics.lt_swgThreshold_iff {c : ℝ} (hc : 0 < c) {p : ℝ} (hp : 0 ≤ p) :
    p < swgThreshold c ↔ c * p * (1 + p) < 1 - p

    Below the threshold the mean offspring is < 1: for p ≥ 0, p < p* ↔ c p (1 + p) < 1 - p.

    theorem Epidemics.swgThreshold_lt_iff {c : ℝ} (hc : 0 < c) {p : ℝ} (hp : 0 ≤ p) :
    swgThreshold c < p ↔ 1 - p < c * p * (1 + p)

    Above the threshold the mean offspring is > 1: for p ≥ 0, p* < p ↔ 1 - p < c p (1 + p).

    For c = 1 (one bridge per node on average, as in 3-SWG(n)) the threshold is √2 - 1 ([BCDPTZ22] §2.1).

    theorem Epidemics.lt_half_iff {p : ℝ} (hp : 0 ≤ p) :
    p < 1 / 2 ↔ 2 * p ^ 2 < 1 - p

    The threshold 1/2 of 3-SWG(n): for p ≥ 0, p < 1/2 ↔ 2 p² < 1 - p, i.e. the mean offspring 2 p² / (1 - p) of the exploration of [BCDPTZ22] §3.2 is < 1.

    SWG(n, q) #

    def Epidemics.swg (n : ℕ) (b : Sym2 (Fin n) → Bool) :

    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
    Instances For
      @[implicit_reducible]
      instance Epidemics.swg.decidableAdj (n : ℕ) (b : Sym2 (Fin n) → Bool) :

      Adjacency in swg n b is decidable (cycle or open bridge).

      Equations

      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
        @[implicit_reducible]

        There are finitely many perfect matchings on a finite type (classical: being a perfect matching is not decidable in general).

        Equations

        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
          Instances For
            @[implicit_reducible]
            noncomputable instance Epidemics.swg3.decidableAdj (n : ℕ) (M : PerfectMatching (Fin n)) :

            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.

            theorem Epidemics.swg3_degree_le (n : ℕ) (M : PerfectMatching (Fin n)) (v : Fin n) :
            (swg3 n M).degree v ≤ 3

            3-SWG(n) has maximum degree at most 3 ([BCDPTZ22] §1: two cycle neighbours and one matching partner).