  The parallel computational complexity or depth of growing network models is
investigated. The networks considered are generated by preferential attachment
rules where the probability of attaching a new node to an existing node is
given by a power, $\alpha$ of the connectivity of the existing node. Algorithms
for generating growing networks very quickly in parallel are described and
studied. The sublinear and superlinear cases require distinct algorithms. As a
result, there is a discontinuous transition in the parallel complexity of
sampling these networks corresponding to the discontinuous structural
transition at $\alpha=1$, where the networks become scale free. For $\alpha>1$
networks can be generated in constant time while for $0 \leq \alpha < 1$
logarithmic parallel time is required. The results show that these networks
have little depth and embody very little history dependence despite being
defined by sequential growth rules.
