Parallel dynamics and computational complexity of network growth models.
Parallel dynamics and computational complexity of network growth models.
复制标题
网络增长模型的并行动力学和计算复杂性。
DOI：
10.1103/physreve.71.026704
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
J. Machta
中科院分区：
文献类型：
--
作者：
B. Machta;J. Machta
研究了增长网络模型的并行计算复杂度和深度。所考虑的网络是由优先附着规则生成的，其中将新节点附着到现有节点的概率由现有节点的连通性的幂α给出。快速并行生成增长网络的算法进行了描述和研究。次线性和超线性情况需要不同的算法。因此，在对这些网络进行采样的并行复杂性中存在不连续的过渡，对应于α =1时的不连续结构过渡，其中网络变得无标度。对于alpha>1，网络可以在恒定时间内生成，而对于0</=alpha<1，需要对数并行时间。结果表明，这些网络具有很小的深度和体现很少的历史依赖性，尽管被定义的顺序增长规则。
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.