PaperlayerView exact revision on arXiv

Source-linked AI summary

Decay towards the overall-healthy state in SIS epidemics on networks

Piet Van Mieghem

arXiv:1310.3980v5math.PRcond-mat.stat-mechcs.SIphysics.soc-ph

TL;DR

Accurately determining the second-largest eigenvalue, or decay parameter, remains an outstanding problem in birth–death processes and random walks. The paper develops an algebraic approach and applies it to SIS epidemics on K_N. It derives a decay-rate and lifetime bound above threshold, and concludes that almost all graphs have exponentially growing average absorption times, while the graph-dependent constant remains undetermined.

  • Problem

    Accurate determination of the second-largest eigenvalue, the decay parameter in birth–death processes and random walks, remains an outstanding problem.

    Source: §1 · p. 3

  • Method

    The paper computes the SIS decay rate on K_N through the second-largest eigenvalue of the process’s infinitesimal generator.

    Source: §1 · p. 3

  • Results

    Above threshold, the decay rate on K_N tends to zero at least as fast as e^(-N ln(τ/τc)), and the average lifetime in any network is at most about its reciprocal.

    Source: §3 · p. 10

  • Takeaways & Limitations

    Combining the upper bound with prior lower bounds, the paper concludes that for almost all graphs the average absorption time above threshold is O(e^(c_G N)).

    Source: §3 · p. 10

    The precise expression for c_G for a given graph remains future work.

    Source: §3 · p. 10

Abstract

from arXiv · show

The decay rate of SIS epidemics on the complete graph $K_{N}$ is computed analytically, based on a new, algebraic method to compute the second largest eigenvalue of a stochastic three-diagonal matrix up to arbitrary precision. The latter problem has been addressed around 1950, mainly via the theory of orthogonal polynomials and probability theory. The accurate determination of the second largest eigenvalue, also called the \emph{decay parameter}, has been an outstanding problem appearing in general birth-death processes and random walks. Application of our general framework to SIS epidemics shows that the maximum average lifetime of an SIS epidemics in any network with $N$ nodes is not larger (but tight for $K_{N}$) than \[ E\left[ T\right] \sim\frac{1}{\delta}\frac{\frac{\tau}{\tau_{c}}\sqrt{2\pi}% }{\left( \frac{\tau}{\tau_{c}}-1\right) ^{2}}\frac{\exp\left( N\left\{ \log\frac{\tau}{\tau_{c}}+\frac{\tau_{c}}{\tau}-1\right\} \right) }{\sqrt {N}}=O\left( e^{N\ln\frac{\tau}{\tau_{c}}}\right) \] for large $N$ and for an effective infection rate $\tau=\frac{\beta}{\delta}$ above the epidemic threshold $\tau_{c}$. Our order estimate of $E\left[ T\right] $ sharpens the order estimate $E\left[ T\right] =O\left( e^{bN^{a}}\right) $ of Draief and Massouli\'{e} \cite{Draief_Massoulie}. Combining the lower bound results of Mountford \emph{et al.} \cite{Mountford2013} and our upper bound, we conclude that for almost all graphs, the average time to absorption for $\tau>\tau_{c}$ is $E\left[ T\right] =O\left( e^{c_{G}N}\right) $, where $c_{G}>0$ depends on the topological structure of the graph $G$ and $\tau$.

1 Introduction

The introduction frames accurate determination of a birth–death process’s second-largest eigenvalue as an outstanding problem and applies it to SIS epidemics on the complete graph. It connects the resulting decay rate to epidemic lifetime and combines the complete-graph upper bound with prior lower bounds for a conclusion about almost all graphs.

1 Introduction

  • Below τc, SIS infection dies out exponentially fast, whereas above τc a nonzero fraction of nodes remains infected for a very long time.The introduction describes this contrast as a general characteristic of a phase transition.Source: §1 · p. 2
  • The second-largest eigenvalue determines decay toward the overall-healthy state and approximately gives the reciprocal average epidemic lifetime on K_N.For a discrete-time process, deviations from steady state decay at a rate governed by its second-largest eigenvalue.Source: §1 · p. 3
  • For τ > τc and large N, the paper’s main contribution is an accurate expression for the SIS decay rate on K_N.The decay rate is the second-largest eigenvalue of the complete-graph process’s infinitesimal generator.Source: §1 · p. 3
  • The accurate second-largest-eigenvalue problem has remained outstanding in birth–death processes and random walks, motivating the paper’s general framework.The paper computes the eigenvalue of a stochastic tridiagonal matrix through a Lagrange series.Source: §1 · p. 3
  • Earlier results give an exponential-in-N absorption-time bound above threshold, while the paper’s complete-graph estimate sharpens the order to parameters a = 1 and b = ln(τ/τc).The paper contrasts this with the earlier estimate O(e^(bN^a)).Source: §1 · pp. 2–3
  • Combining its upper bound with Mountford et al.’s lower bounds, the paper concludes that almost all graphs have average absorption time O(e^(c_G N)) above threshold.The constant c_G depends on graph topology; determining it accurately for graphs other than K_N is left open.Source: §1 · p. 4

2 Markovian ε−SIS epidemics

The section uses an irreducible ε-SIS process on the complete graph to analyze convergence through the second eigenvalue ζ, then takes ε → 0 to study classical SIS decay. It develops coefficient and large-N asymptotics to estimate ζ across epidemic regimes.

2 Markovian ε−SIS epidemics

  • For the complete graph, the ε-SIS process is a birth-death chain whose rates are λ_j = (βj + ε)(N − j) and μ_j = jδ.Positive ε makes all rates positive, so the chain is irreducible and has no absorbing state.Source: §2 · p. 4
  • As ε → 0, the ε-SIS process behaves as classical SIS; epidemics decay toward the overall healthy absorbing state at a rate never slower than 1/f0.Source: §2 · pp. 4–5

2.1 Coefficients f0, f1 and f2 in ε−SIS epidemics

  • The supported result is the limiting relation: as ε → 0, f1 tends to F(τ); the passage identifies this limit as the one specified in equation (3).Source: §2.1 · p. 5

2.2 Asymptotics of f0, f1 and f2 in ε−SIS epidemics for large N

  • For large N, the section derives asymptotic forms of the coefficients, including the ε → 0 limit of f_2, using x = Nτ to organize the regimes.The coefficient analysis distinguishes cases x < 1 and x > 1.Source: §2.2 · pp. 6–7

2.3 Scaling of ζ with N in SIS epidemics (when ε ↓0)

  • For x < 1, the first Lagrange-series term suffices for the main result, while at x = 1 the first two terms are of equal order and higher terms are needed for accuracy.The authors refrain from that more costly higher-order calculation and use numerical calculations for the latter regime.Source: §2.3 · p. 8
  • Numerical results support the order estimates at, below, and above threshold; both the second-order Lagrange estimate and Newton upper bound sharpen as τ rises above threshold.For 1 < x < 2.5, the asymptotic result is verified up to N = 100, while verification for x much larger than 1 is difficult for N > 10.Source: §2.3 · p. 8

3 Conclusion

For SIS on the complete graph above threshold, the decay rate implies an exponentially long mean lifetime, while an upper bound extends to any network. Combining that bound with prior lower bounds gives an exponential-order absorption time for almost all graphs.

3 Conclusion

  • Figure 1 compares the exact second-largest zero with second-order Lagrange-series and Newton-identity estimates across N and four effective infection rates.The caption specifies ε = 10^-5 and τ values {1/(2N), 1/N, 2/N, 3/N}.Source: Figure 1 · p. 9
  • Above threshold on K_N, the lifetime is approximately exponential with mean 1/|ζ|, and the decay rate tends to zero at least as fast as e^{-N ln(τ/τ_c)}.The passage describes τ/τ_c > 1 to first order in N.Source: §3 · p. 10
  • For any network, the survival probability is bounded by an exponential with exponent involving e^{-N ln(τ/τ_c)}, yielding an upper bound on mean lifetime.The supplied passages state this bound for τ > τ_c.Source: §3 · p. 10
  • Combining the upper bound with Mountford et al.’s lower-bound results gives E[T] = O(e^{c_G N}) for almost all graphs, with c_G > 0.The precise expression for c_G remains future work.Source: §3 · p. 10

A General tri-diagonal matrices

The paper studies stochastic tridiagonal matrices arising as transition matrices for generalized random walks, using an algebraic approach to their eigenstructure. A block decomposition also identifies how coupling between state ranges affects reducibility.

A General tri-diagonal matrices

  • The general stochastic tridiagonal matrix P is a transition matrix for a generalized random walk, and its eigenstructure is studied algebraically.The approach is contrasted with the more probabilistic and function-theoretic method of Karlin and McGregor.Source: A General tri-diagonal matrices · p. 11
  • When transition probabilities are constant, P has Toeplitz form, for which eigenvalues and eigenvectors can be written explicitly.The stated explicit result is attributed to.Source: A General tri-diagonal matrices · p. 11
  • In the block decomposition, the matrix CA^-1B changes only the first diagonal element of D, from r_k to r_k - p_{k-1}q_k.The blocks B and C each contain one nonzero element.Source: A General tri-diagonal matrices · p. 12
  • If p_{k-1} = 0 or q_k = 0, the determinant factors into the determinants of the two blocks and the Markov chain is reducible.The analysis thereafter assumes nonzero, time-independent matrix elements so the chain is irreducible.Source: A General tri-diagonal matrices · p. 12

A.1 A similarity transform

A diagonal similarity transform symmetrizes the tridiagonal transition matrix when its transition probabilities are positive. This makes the eigenvalues real while retaining the eigenvalues of the original matrix.

A.1 A similarity transform

  • The transform is chosen to satisfy the symmetry condition for adjacent off-diagonal entries of the tridiagonal matrix.The resulting matrix is H P H^-1.Source: §A.1 · pp. 12–13
  • If p_{i-1} = 0 or q_i = 0, states below i-1 are uncoupled from states i through N.This is the boundary case excluded by the positive-transition assumption.Source: §A.1 · p. 12
  • With all p_i and q_i positive, the diagonal similarity transform H produces a symmetric matrix, so all eigenvalues of P are real.The transform uses h_{i+1} = q_i h_i / p_i and may take h_1 = 1.Source: §A.1 · pp. 12–13

A.2 Eigenvectors of P

The appendix builds eigenvectors of P as polynomials in the shifted eigenvalue, then uses their recursions and orthogonality to characterize eigenvalues and derive a Christoffel-Darboux formula.

A.2 Eigenvectors of P

  • The eigenvector components satisfy a three-term recurrence, and the eigenvalues of P are zeros of the degree-(N+1) polynomial ρ_{N+1}(ξ), whose zeros interlace those of the other polynomials.The stochasticity condition supplies an additional coefficient relation.Source: §A.2 · pp. 13, 15, 16

A.3 Solving the recursion (15)

  • The recursion for the coefficients c_k(j) can be decomposed into two first-order recursions, determining all coefficients and showing they are non-negative.The coefficients are constructed from the transition probabilities p_j and q_j.Source: §A.3 · pp. 17–18

A.4 The second set of orthogonality conditions

  • The derivation gives an explicit weight function for the orthogonality relation of the polynomials associated with a tridiagonal stochastic matrix.The orthogonality conditions use the symmetric matrix obtained by similarity transformation.Source: §A.4 · pp. 18–19

A.5 The Christoffel-Darboux formula for eigenvectors of P

  • The Christoffel-Darboux formula for eigenvectors of P extends the orthogonality relation to all 0 ≤ m ≤ N.The extension uses p_N = 0.Source: §A.5 · p. 20

B Second largest zero of cP (ξ)

The section develops a Lagrange-series method and bounds for the second-largest zero of cP(ξ), then turns to properties of F(τ), including its Laplace-transform and asymptotic forms.

B Second largest zero of cP (ξ)

  • The Lagrange series can formally compute ζ to any order, and its first term equals the first Newton-Raphson iteration.The expansion around ξ = 0 converges fast because all Taylor coefficients are non-zero and zero is the largest zero of cP(ξ).Source: B Second largest zero of cP (ξ) · p. 21
  • The first Taylor coefficient f1 is an upper bound for ζ.The section also notes that orthogonal-polynomial interlacing gives lower bounds, but the best such bound is harder to compute because the largest zero of ρN(ξ) is negative and unknown.Source: B Second largest zero of cP (ξ) · p. 22
  • Using f0, f1, and f2, the second-largest zero ζ is approximated by a second-order Lagrange series and has upper bounds (36) and (39).The article demonstrates computation through second order; extending it with f3 is possible but entails huge computations.Source: B Second largest zero of cP (ξ) · pp. 21, 23
  • Newton identities can supply subsequent Lagrange-series terms and, combined with expansion around a complex number, offer insight into series convergence.Source: B Second largest zero of cP (ξ) · p. 23

C The function F (τ)

  • For τ = x/N with fixed x and large N, the section studies F(τ), including its Laplace-transform, exact-form, and asymptotic representations.It reconsiders F(τ) = limε→0 f1, which is linked to result (2).Source: C The function F (τ) · p. 23

C.1 F (τ) as a Laplace transform

For τ > τc, the section expresses F(τ) as a Laplace transform. It derives this representation by converting a recursion into a differential equation and solving with initial conditions.

C.1 F (τ) as a Laplace transform

  • For τ > τc, F(τ) = limε→0 f1 is expressed as a Laplace transform.Source: §C.1 · pp. 23, 25
  • Orthogonal-polynomial interlacing gives lower bounds for ζ, but the best lower bound requires the harder-to-compute second-largest zero of ρN(ξ).The largest zero of ρN(ξ) is negative and unknown, unlike the zero of ρN+1(ξ).Source: §C.1 · p. 23
  • The derivation converts a recursion for xk into a differential equation for its generating function g(z, N).The recursion uses x1 = 1 and xk = 0 for k < 1.Source: §C.1 · p. 24
  • The generating function is normalized by g(0, N) = 1, with the integration constant chosen to keep limz→0 g(z, N) finite.Source: §C.1 · pp. 24–25
  • The authors use variation of constants to solve the differential equation and obtain the Laplace-transform expression for F(τ).Source: §C.1 · p. 25

C.2 F (τ) in terms of exponential integrals

The section derives an expression for βF(τ) in terms of integer-order exponential integrals and presents an alternative integral form. It also identifies a restriction on using a large-N approximation.

C.2 F (τ) in terms of exponential integrals

  • F(τ) can be expressed in terms of integer-order exponential integrals En(x).Source: §C.2 · p. 26
  • The large-N approximation cannot be used in the relevant expression because the p-integral diverges.Source: §C.2 · p. 27
  • An alternative integral expression for βF(τ) avoids the summation.Source: §C.2 · p. 28
  • A triple-integral form suggests a change of variables s = p + u and r = pu, but that change did not yield useful results.Source: §C.2 · p. 28

C.2.1 Other exact series for βF (τ)

The section establishes alternative exact series representations for βF(τ) and relates their coefficients to exponential integrals. It then considers properties and a recursion for the Taylor coefficients Bj.

C.2.1 Other exact series for βF (τ)

  • The expression for βF(τ) is further explored using properties of the exponential integral.Source: §C.2.1 · p. 28
  • The proof establishes Bj = Cj, linking the coefficients in the two exact series representations.Source: §C.2.1 · p. 30
  • The series representation using coefficients Bj equals the Taylor series in (52), by uniqueness of Taylor series.Source: §C.2.1 · p. 31

C.2.2 The coefficients Bj

  • The section presents additional properties of Taylor coefficients Bj and introduces a recursion for them.Source: §C.2.2 · p. 31

C.3 Order estimate of F (τ) for large N

This section develops bounds and approximations used to estimate F(τ) for large N at fixed x = Nτ. It identifies a bound on the exponential integral as crucial to the order estimate.

C.3 Order estimate of F (τ) for large N

  • For k > 1, the inequality Ek(w) < Ek−1(w) is used to bound Lk(τ).The section states that the exponential-integral bound plays a crucial role in the proof of Theorem 6.Source: §C.3 · p. 32
  • The exponential-integral bound τ(γ − ln τ) < L1(τ) < τ(γ − ln τ) + τ is tight for τ < 1 but loose for τ > 1.The text says the upper bound suffices for small τ = x/N.Source: §C.3 · pp. 31, 33
  • For large N and fixed x > 1, the section estimates F(τ) using a dominant term and an asymptotically correct approximation.The bound on the exponential integral is used when treating the last term in the sum separately.Source: §C.3 · pp. 32, 34, 35
Loading 1310.3980v5…