How Complex Contagions Spread Quickly in Preferential Attachment Models and Other Time-Evolving Networks

Abstract

The <i><inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives> <inline-graphic xlink:href="ghasemiesfeh-ieq1-2718024.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula>-complex contagion</i> model is a social contagion model which describes the diffusion of behaviors in networks where the successful adoption of a behavior requires influence from multiple contacts. It has been argued that complex contagions better model behavioral changes such as adoption of new beliefs, fashion trends or expensive technology innovations. A contagion in this model starts from a set of initially infected seeds and progresses in rounds. In any round any node with at least <inline-formula><tex-math notation="LaTeX">$k&gt;1$</tex-math></inline-formula> infected neighbors becomes infected. Previous work on <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -complex contagions was focused on networks with uniform degree distributions. However, many real-world network topologies have non-uniform degree distribution and evolve over time. We analyze the spreading rate of a <inline-formula> <tex-math notation="LaTeX">$k$</tex-math></inline-formula> -complex contagion in a general family of time-evolving networks which includes the preferential attachment (PA) model. We prove that if the initial seeds are chosen as the <inline-formula> <tex-math notation="LaTeX">$k$</tex-math></inline-formula> earliest nodes in a network of this family, a <inline-formula> <tex-math notation="LaTeX">$k$</tex-math></inline-formula> -complex contagion covers the entire network of <inline-formula> <tex-math notation="LaTeX">$n$</tex-math></inline-formula> nodes in <inline-formula><tex-math notation="LaTeX">$O(\log n)$</tex-math> </inline-formula> rounds with high probability (w.h.p). We prove that the choice of the seeds is crucial: in the PA model, even if a much larger number of seeds are chosen <i>uniformly randomly</i> , the contagion stops prematurely w.h.p. Although the earliest nodes in a PA model are likely to have high degrees, it is actually the evolutionary graph structure of such models that facilitates fast spreading of complex contagions. The general family of time-evolving graphs with this property even contains networks without a power law degree distribution. Finally, we prove that when a <inline-formula> <tex-math notation="LaTeX">$k$</tex-math></inline-formula> -complex contagion starts from an arbitrary set of initial seeds on a general graph, determining if the number of infected vertices is above a given threshold is <inline-formula> <tex-math notation="LaTeX">${\mathbf {P}}$</tex-math></inline-formula> -complete. Thus, one cannot hope to categorize all the settings in which <inline-formula><tex-math notation="LaTeX">$k$</tex-math> </inline-formula> -complex contagions percolate in a graph.