Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix
arXiv:1906.04269 · doi:10.1093/imamat/hxaa003
Abstract
We study the stochastic susceptible-infected-susceptible model of epidemic processes on finite directed and weighted networks with arbitrary structure. We present a new lower bound on the exponential rate at which the probabilities of nodes being infected decay over time. This bound is directly related to the leading eigenvalue of a matrix that depends on the non-backtracking and incidence matrices of the network. The dimension of this matrix is N+M, where N and M are the number of nodes and edges, respectively. We show that this new lower bound improves on an existing bound corresponding to the so-called quenched mean-field theory. Although the bound obtained from a recently developed second-order moment-closure technique requires the computation of the leading eigenvalue of an N^2 x N^2 matrix, we illustrate in our numerical simulations that the new bound is tighter, while being computationally less expensive for sparse networks. We also present the expression for the corresponding epidemic threshold in terms of the adjacency matrix of the line graph and the non-backtracking matrix of the given network.
arXiv comment1 figure
References in corpus (20)
- Emergence of scaling in random networks
- Epidemic spreading in scale-free networks
- Finding community structure in networks using the eigenvectors of matrices
- Epidemic processes in complex networks
- Self-similar community structure in organisations
- Influence maximization in complex networks through optimal percolation
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- Thresholds for epidemic spreading in networks
- Random walks and diffusion on networks
- A message passing approach for general epidemic models
- Unification of theoretical approaches for epidemic spreading on complex networks
- Percolation on sparse networks
- Optimal Resource Allocation for Network Protection Against Spreading Processes
- Non-backtracking random walks mix faster
- A message-passing approach for recurrent-state epidemic models on networks
- Leveraging percolation theory to single out influential spreaders in networks
- Dynamic message-passing equations for models with unidirectional dynamics
- Tight lower bound for percolation threshold on a quasi-regular graph
- Relevance of backtracking paths in epidemic spreading on networks
- Second-Order Moment-Closure for Tighter Epidemic Thresholds