TY - THES
T1 - Spreading on Networks
AU - Liu, Qiang
PY - 2019
Y1 - 2019
N2 - Spreading phenomena such as spreading of diseases, information and computer viruses are ubiquitous in nature and man-made systems, but the understanding of them is still insufficient. This dissertation focuses on the analysis of a basic mathematical model of spreading phenomena running on underlying network structures and aims to complete the basic theory of spreading processes. Specifically, we explore the Susceptible-Infected-Susceptible (SIS) model from several interesting perspectives to contribute to the state-of-the-art understanding of the model. Our first main contribution is related to temporal correlations. In most of the studies, the influence of time in the SIS spreading process is omitted because the specific value of the infection and curing rates does not influence the first-moment metastable properties, such as the infection probability of each node. Only the ratio between the two rates matters. In this dissertation, we show that the temporal correlation can be analyzed with the mean-field approaches, although mean-field methods are meant to only analyze first-moment properties. We derive the autocorrelation of the nodal infection state both in the steady and transient states under the mean-field approximation. By analyzing the autocorrelation, we indicate the influence of the underlying network and the value of the infection and curing rates on the temporal properties of the spreading process. We also show that the infection and curing rates can be calculated by measuring the infection state of each node. Second, we relax the Markovian assumption in the SIS process by extending the Poisson infection process to a Weibull renewal process. The Poisson infection process is just a special case of the Weibullian renewal process. Under this Weibullian framework, we can parameterize the non-Markovian infection behavior and show some new features raised by it. We specifically focus on an extreme (limiting) case of the Weibullian SIS process where the distribution of the infection time is a Dirac delta function. The analysis of the extreme case leads to the largest possible epidemic threshold for non-Poissonian infection processes. We further discuss the epidemic threshold for different infection processes with Weibull, lognormal and Gamma distributed infection time, which fit realistic spreading phenomena well, under a previous non-Markovian mean-field method based on renewal theory. We show consistency between our results and previous theory and that those different infection processes behave similarly.Third, we dive into the localization phenomena in networks from the viewpoint of SIS spreading processes. Localization of the spreading process appears just above the epidemic threshold in networks whose principal eigenvector of the adjacency matrix is localized. In the localized spreading, the prevalence (order parameter), which is the expected fraction of infected nodes, converges to zero with the increase of network size but the number of infected nodes is non-zero. Thus, the localized spreading forms an interesting phase different from the all-healthy phase (no infection) and the endemic phase (non-zero prevalence). We evaluate the above-mentioned extreme case of the Weibullian SIS process where the time-dependent prevalence is periodic in the long-run. Near the epidemic threshold, the ratio between the steady-state maximum and minimum prevalence, which equals to the largest eigenvalue of the adjacency matrix, diverges in some networks, but the spreading process is still localized. In other words, the divergent ratio of prevalence, determined by the largest eigenvalue of the network, cannot amplify a zero-prevalence to a non-zero one in the thermodynamic limit. The result indicates that the localization of spreading processes may be only determined by the network structure but not the specific infection process. Finally, we study the curing strategy for the control of the spreading process, specifically, the pulse curing strategy. Compared to the classical asynchronous curing strategy (for instance Poissonian), pulse strategy is an optimized method of suppressing the spreading and applied broadly in disease control. Here, we study the model which is composed of a susceptible-infected process and a periodical pulse curing process with a successful curing probability below one. We derive the mean-field epidemic threshold. Based on our analysis, the pulse strategy reduces the number of curing operations by $36.8\%$ compared to traditional asynchronous curing strategies in the Markovian SIS model.All the above-mentioned theoretical analyses are verified by directly simulating SIS processes.
AB - Spreading phenomena such as spreading of diseases, information and computer viruses are ubiquitous in nature and man-made systems, but the understanding of them is still insufficient. This dissertation focuses on the analysis of a basic mathematical model of spreading phenomena running on underlying network structures and aims to complete the basic theory of spreading processes. Specifically, we explore the Susceptible-Infected-Susceptible (SIS) model from several interesting perspectives to contribute to the state-of-the-art understanding of the model. Our first main contribution is related to temporal correlations. In most of the studies, the influence of time in the SIS spreading process is omitted because the specific value of the infection and curing rates does not influence the first-moment metastable properties, such as the infection probability of each node. Only the ratio between the two rates matters. In this dissertation, we show that the temporal correlation can be analyzed with the mean-field approaches, although mean-field methods are meant to only analyze first-moment properties. We derive the autocorrelation of the nodal infection state both in the steady and transient states under the mean-field approximation. By analyzing the autocorrelation, we indicate the influence of the underlying network and the value of the infection and curing rates on the temporal properties of the spreading process. We also show that the infection and curing rates can be calculated by measuring the infection state of each node. Second, we relax the Markovian assumption in the SIS process by extending the Poisson infection process to a Weibull renewal process. The Poisson infection process is just a special case of the Weibullian renewal process. Under this Weibullian framework, we can parameterize the non-Markovian infection behavior and show some new features raised by it. We specifically focus on an extreme (limiting) case of the Weibullian SIS process where the distribution of the infection time is a Dirac delta function. The analysis of the extreme case leads to the largest possible epidemic threshold for non-Poissonian infection processes. We further discuss the epidemic threshold for different infection processes with Weibull, lognormal and Gamma distributed infection time, which fit realistic spreading phenomena well, under a previous non-Markovian mean-field method based on renewal theory. We show consistency between our results and previous theory and that those different infection processes behave similarly.Third, we dive into the localization phenomena in networks from the viewpoint of SIS spreading processes. Localization of the spreading process appears just above the epidemic threshold in networks whose principal eigenvector of the adjacency matrix is localized. In the localized spreading, the prevalence (order parameter), which is the expected fraction of infected nodes, converges to zero with the increase of network size but the number of infected nodes is non-zero. Thus, the localized spreading forms an interesting phase different from the all-healthy phase (no infection) and the endemic phase (non-zero prevalence). We evaluate the above-mentioned extreme case of the Weibullian SIS process where the time-dependent prevalence is periodic in the long-run. Near the epidemic threshold, the ratio between the steady-state maximum and minimum prevalence, which equals to the largest eigenvalue of the adjacency matrix, diverges in some networks, but the spreading process is still localized. In other words, the divergent ratio of prevalence, determined by the largest eigenvalue of the network, cannot amplify a zero-prevalence to a non-zero one in the thermodynamic limit. The result indicates that the localization of spreading processes may be only determined by the network structure but not the specific infection process. Finally, we study the curing strategy for the control of the spreading process, specifically, the pulse curing strategy. Compared to the classical asynchronous curing strategy (for instance Poissonian), pulse strategy is an optimized method of suppressing the spreading and applied broadly in disease control. Here, we study the model which is composed of a susceptible-infected process and a periodical pulse curing process with a successful curing probability below one. We derive the mean-field epidemic threshold. Based on our analysis, the pulse strategy reduces the number of curing operations by $36.8\%$ compared to traditional asynchronous curing strategies in the Markovian SIS model.All the above-mentioned theoretical analyses are verified by directly simulating SIS processes.
KW - Spreading Process
KW - Complex Networks
KW - Stochastic Simulation
U2 - 10.4233/uuid:155cd8db-619f-49f6-a3db-1bdb6036420c
DO - 10.4233/uuid:155cd8db-619f-49f6-a3db-1bdb6036420c
M3 - Dissertation (TU Delft)
SN - 978-94-6384-074-3
CY - Delft
ER -