2004/08/22 by Benjamin B. Machta, Benjamin Machta, Jonathan Machta +1 · 21 citations
Mathematics · Physics and Astronomy · #Algorithm #Alpha (finance) #Binary logarithm #Combinatorics #Communication complexity #Complex Network Analysis Techniques #Complex network #Computational complexity theory #Computer science #Constant (computer programming) #Discrete mathematics #Logarithm #Mathematics #Node (physics) #Opinion Dynamics and Social Influence #Physics #Preferential attachment #Sublinear function #Theoretical and Computational Physics #Theoretical computer science #Time complexity #cond-mat.stat-mech
paper · pdf · doi:10.1103/physreve.71.026704
published in Physical Review E 71(2), 026704 (American Physical Society) · 10 pages, 2 figures
arxiv created 2004/08/22 · openalex publication_date 2005/02/28 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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</=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.