Infection number
The
infection number
quantifies the expected impact of a node \(i\) as the initial source of infection [2]. Under the assumption that all infection walks are independent, Bauer and Lizier [2] approximate the infection number using
self-avoiding walks
(SAWs) in a graph \(G\), which is also referred to as the walks-based method.
For the SIR (susceptible/infected/removed) model, where an infected node is removed from the network with probability \(λ = 1\) (representing either death or full recovery with immunity), the expected number of resulting infections from node \(i\) is
\[
I_i^{SIR} = \sum_{k=1}^{N-1} \sum_{j=1}^{N} \Bigl( 1 - (1 - β^k)^{s_{ij}^{k,0}} \Bigr)
\Bigl( 1 - \sum_{t=1}^{k-1} \bigl( 1 - (1 - β^t)^{(A^t)_{ij}} \bigr) \Bigr),
\]
where \((A^k)_{ij}\) is the total number of paths of length \(k\) from \(i\) to \(j\), \(s_{ij}^{k,0}\) is the number of self-avoiding walks of length \(k\) from \(i\) to \(j\) and \(β\) is the infection probability.
The infection number of node \(i\), considering only paths up to a maximum length \(K\), is denoted \(I_i^{SIR}(K)\). Bauer and Lizier [2] show that \(I_i^{SIR}(K)\) with \(K=4\) provides a good approximation of the true infection spread across a wide range of \(β\) values.