How Complex Contagions Spread Quickly in Preferential Attachment Models and Other Time-Evolving Networks
The <italic><inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives> <inline-graphic xlink:href="ghasemiesfeh-ieq1-2718024.gif"/></alternatives></inline-formula>-complex contagion</italic> 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>1$</tex-math><alternatives> <inline-graphic xlink:href="ghasemiesfeh-ieq2-2718024.gif"/></alternatives></inline-formula> infected neighbors becomes infected. Previous work on <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives> <inline-graphic xlink:href="ghasemiesfeh-ieq3-2718024.gif"/></alternatives></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><alternatives><inline-graphic xlink:href="ghasemiesfeh-ieq4-2718024.gif"/> </alternatives></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><alternatives><inline-graphic xlink:href="ghasemiesfeh-ieq5-2718024.gif"/> </alternatives></inline-formula> earliest nodes in a network of this family, a <inline-formula> <tex-math notation="LaTeX">$k$</tex-math><alternatives><inline-graphic xlink:href="ghasemiesfeh-ieq6-2718024.gif"/> </alternatives></inline-formula>-complex contagion covers the entire network of <inline-formula> <tex-math notation="LaTeX">$n$</tex-math><alternatives><inline-graphic xlink:href="ghasemiesfeh-ieq7-2718024.gif"/> </alternatives></inline-formula> nodes in <inline-formula><tex-math notation="LaTeX">$O(\log n)$</tex-math> <alternatives><inline-graphic xlink:href="ghasemiesfeh-ieq8-2718024.gif"/></alternatives></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 <italic>uniformly randomly</italic>, 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><alternatives><inline-graphic xlink:href="ghasemiesfeh-ieq9-2718024.gif"/> </alternatives></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><alternatives> <inline-graphic xlink:href="ghasemiesfeh-ieq10-2718024.gif"/></alternatives></inline-formula>-complete. Thus, one cannot hope to categorize all the settings in which <inline-formula><tex-math notation="LaTeX">$k$</tex-math> <alternatives><inline-graphic xlink:href="ghasemiesfeh-ieq11-2718024.gif"/></alternatives></inline-formula>-complex contagions percolate in a graph.