Epidemic threshold in directed networks

Abstract

Epidemics have so far been mostly studied in undirected networks. However, many real-world networks, such as the online social network Twitter and the world wide web, on which information, emotion, or malware spreads, are directed networks, composed of both unidirectional links and bidirectional links. We define the directionality $\ensuremath{\xi}$ as the percentage of unidirectional links. The epidemic threshold ${\ensuremath{\tau}}_{c}$ for the susceptible-infected-susceptible (SIS) epidemic is lower bounded by $1/{\ensuremath{\lambda}}_{1}$ in directed networks, where ${\ensuremath{\lambda}}_{1}$, also called the spectral radius, is the largest eigenvalue of the adjacency matrix. In this work, we propose two algorithms to generate directed networks with a given directionality $\ensuremath{\xi}$. The effect of $\ensuremath{\xi}$ on the spectral radius ${\ensuremath{\lambda}}_{1}$, principal eigenvector ${x}_{1}$, spectral gap $({\ensuremath{\lambda}}_{1}\ensuremath{-}\left|{\ensuremath{\lambda}}_{2}\right|),$ and algebraic connectivity ${\ensuremath{\mu}}_{N\ensuremath{-}1}$ is studied. Important findings are that the spectral radius ${\ensuremath{\lambda}}_{1}$ decreases with the directionality $\ensuremath{\xi}$, whereas the spectral gap and the algebraic connectivity increase with the directionality $\ensuremath{\xi}$. The extent of the decrease of the spectral radius depends on both the degree distribution and the degree-degree correlation ${\ensuremath{\rho}}_{D}$. Hence, in directed networks, the epidemic threshold is larger and a random walk converges to its steady state faster than that in undirected networks with the same degree distribution.

Locations

• Physical Review E - View
• arXiv (Cornell University) - View - PDF
• Research Repository (Delft University of Technology) - View - PDF
• PubMed - View
• DataCite API - View