  Diffusion of information in networks is at the core of many problems in AI.
Common examples include the spread of ideas and rumors as well as marketing
campaigns. Typically, information diffuses at a non-linear rate, for example,
if markets become saturated or if users of social networks reinforce each
other's opinions. Despite these characteristics, this area has seen little
research, compared to the vast amount of results for linear models, which
exhibit less complex dynamics. Especially, when considering the possibility of
re-infection, no fully rigorous guarantees exist so far.
  We address this shortcoming by studying a very general non-linear diffusion
model that captures saturation as well as reinforcement. More precisely, we
consider a variant of the SIS model in which vertices get infected at a rate
that scales polynomially in the number of their infected neighbors, weighted by
an infection coefficient $\lambda$. We give the first fully rigorous results
for thresholds of $\lambda$ at which the expected survival time becomes
super-polynomial. For cliques we show that when the infection rate scales
sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared
to the standard SIS model. In contrast, super-linear scaling changes the
process considerably and shifts the threshold by a polynomial term. For stars,
sub-linear and super-linear scaling behave similar and both shift the threshold
by a polynomial factor. Our bounds are almost tight, as they are only apart by
at most a poly-logarithmic factor from the lower thresholds, at which the
expected survival time is logarithmic.
