Survival time of the susceptible-infected-susceptible infection process on a graph

The survival time T is the longest time that a virus, a meme, or a failure can propagate in a network. Using the hitting time of the absorbing state in an uniformized embedded Markov chain of the continuous-time susceptible-infected-susceptible (SIS) Markov process, we derive an exact expression for the average survival time E[T ] of a virus in...

Accuracy criterion for the mean-field approximation in susceptible-infected-susceptible epidemics on networks

Mean-field approximations (MFAs) are frequently used in physics. When a process (such as an epidemic or a synchronization) on a network is approximated by MFA, a major hurdle is the determination of those graphs for which MFA is reasonably accurate. Here, we present an accuracy criterion for Markovian susceptible-infected-susceptible (SIS)...

Domination-time dynamics in susceptible-infected-susceptible virus competition on networks

When two viruses compete for healthy nodes in a simple network and both spreading rates are above the epidemic threshold, only one virus will survive. However, if we prevent the viruses from dying out, rich dynamics emerge. When both viruses are identical, one virus always dominates the other, but the dominating and dominated virus alternate. We...

Epidemic threshold and topological structure of susceptible-infectious-susceptible epidemics in adaptive networks

The interplay between disease dynamics on a network and the dynamics of the structure of that network characterizes many real-world systems of contacts. A continuous-time adaptive susceptible-infectious-susceptible (ASIS) model is introduced in order to investigate this interaction, where a susceptible node avoids infections by breaking its...

Susceptible-infected-susceptible epidemics on networks with general infection and cure times

The classical, continuous-time susceptible-infected-susceptible (SIS) Markov epidemic model on an arbitrary network is extended to incorporate infection and curing or recovery times each characterized by a general distribution (rather than an exponential distribution as in Markov processes). This extension, called the generalized SIS (GSIS)...

Non-Markovian Infection Spread Dramatically Alters the Susceptible-Infected-Susceptible Epidemic Threshold in Networks

Most studies on susceptible-infected-susceptible epidemics in networks implicitly assume Markovian behavior: the time to infect a direct neighbor is exponentially distributed. Much effort so far has been devoted to characterize and precisely compute the epidemic threshold in susceptible-infected-susceptible Markovian epidemics on networks. Here,...

Susceptible-infected-susceptible model: A comparison of N-intertwined and heterogeneous mean-field approximations

We introduce the ?-susceptible-infected-susceptible (SIS) spreading model, which is taken as a benchmark for the comparison between the N-intertwined approximation and the Pastor-Satorras and Vespignani heterogeneous mean-field (HMF) approximation of the SIS model. The N-intertwined approximation, the HMF approximation, and the ?-SIS spreading...

Gossip-based counting in dynamic networks

We propose Gossipico, a gossip algorithm to average, sum or find minima and maxima over node values in a large, distributed, and dynamic network. Unlike previous work, Gossipico provides a continuous estimate of, for example, the number of nodes, even when the network becomes disconnected. Gossipico converges quickly due to the introduction of a...

Decreasing the spectral radius of a graph by link removals

The decrease of the spectral radius, an important characterizer of network dynamics, by removing links is investigated. The minimization of the spectral radius by removing m links is shown to be an NP-complete problem, which suggests considering heuristic strategies. Several greedy strategies are compared, and several bounds on the decrease of...