  In this paper, we study the spreading speed of complex contagions in a social
network. A $k$-complex contagion starts from a set of initially infected seeds
such that any node with at least $k$ infected neighbors gets infected. Simple
contagions, i.e., $k=1$, quickly spread to the entire network in small world
graphs. However, fast spreading of complex contagions appears to be less likely
and more delicate; the successful cases depend crucially on the network
structure~\cite{G08,Ghasemiesfeh:2013:CCW}.
  Our main result shows that complex contagions can spread fast in a general
family of time-evolving networks that includes the preferential attachment
model~\cite{barabasi99emergence}. We prove that if the initial seeds are chosen
as the oldest nodes in a network of this family, a $k$-complex contagion covers
the entire network of $n$ nodes in $O(\log n)$ steps. We show that the choice
of the initial seeds is crucial. If the initial seeds are uniformly randomly
chosen in the PA model, even with a polynomial number of them, a complex
contagion would stop prematurely. The oldest nodes in a preferential attachment
model are likely to have high degrees. However, we remark that it is actually
not the power law degree distribution per se that facilitates fast spreading of
complex contagions, but rather the evolutionary graph structure of such models.
Some members of the said family do not even have a power-law distribution.
  We also prove that complex contagions are fast in the copy
model~\cite{KumarRaRa00}, a variant of the preferential attachment family.
  Finally, we prove that when a 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 $\mathbf{P}$-complete. Thus, one cannot
hope to categorize all the settings in which complex contagions percolate in a
graph.
