Generating Massive Scale-Free Networks under Resource Constraints
Generating Massive Scale-Free Networks under Resource Constraints
复制标题
DOI：
10.1137/1.9781611974317.4
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
U. Meyer;M. Penschuck
中科院分区：
文献类型：
--
作者：
U. Meyer;M. Penschuck
随机图作为大规模无标度网络的数学模型，近年来变得非常流行。虽然它们的一些有趣的性质已经被证明，但实际上需要生成这样的网络的巨大实例来进行实验评估并提供人工数据集。在这篇文章中，我们考虑了有限计算资源下基于线性优先依附的随机图模型的生成方法，并使用著名的Barabasi-Albert(BA)图模型研究了我们的技术。针对外部存储器模型，我们首先提出了两个I/O高效的BA生成器MP-BA和TFP-BA，然后基于但不限于GPGPU将MP-BA扩展到大规模并行。当图形大小仅超出可用RAM 2%时，我们简单且易于推广的顺序TFP-BA算法的性能比Batagelj和Brandes对顺序线性时间BB-BA算法的高度调整实现高出几个数量级。针对具有CPU和GPU的异类系统实施MP-BA，对于适合主内存的实例，其速度是BB-BA的17.6倍，并且在EM设置中可很好地扩展。这两种方案都支持更一般的优先连接模型中的许多特征，例如，超过主存的种子图、具有随机初始度的顶点、顶点的均匀采样、有向图和两个随机选择的顶点之间的边。与以前对计算机集群的研究相比，MP-BA产生了具有竞争力的结果，并且已经提出了一种仅使用一台机器的可行的替代方案。
Random graphs as mathematical models of massive scale-free networks have recently become very popular. While a number of interesting properties of them have been proven, huge instances of such networks actually need to be generated for experimental evaluation and to provide artificial data sets. In this paper, we consider generation methods for random graph models based on linear preferential attachment under limited computational resources and investigate our techniques using the well-known Barabasi-Albert (BA) graph model. We present the first two I/O-efficient BA generators, MP-BA and TFP-BA, for the external-memory (EM) model and then extend MP-BA to massive parallelism based on but not limited to GPGPU. Our simple and easily generalizable sequential TFP-BA outperforms a highly tuned implementation of the sequential lineartime BB-BA algorithm by Batagelj and Brandes by several orders of magnitude once the graph size exceeds the available RAM by only 2 %. An implementation of MP-BA targeting heterogeneous systems with CPUs and GPUs is 17.6 times faster than BB-BA for instances fitting in main memory and scales well in the EM setting. Both schemes support a number of features in more general preferential attachment models, e.g., seed graphs exceeding main memory, vertices with random initial degrees, the uniform sampling of vertices, directed graphs and edges between two randomly chosen vertices. Compared with previous studies on computer clusters, MP-BA yields competitive results and already poses a viable alternative using only a single machine.