Graph Networks

A novel algorithm has been designed, developed, and implemented on modern GPU accelerators, and benchmarked on networks with billions of edges, including Facebook and Twitter networks. Rates of generation exceed 50 billion edges per second.

Our algorithm cuPPA generates scale-free networks using the preferential-attachment model, custom-designed to exploit multiple GPUs. We generate extremely large scale-free networks of 4 trillion edges in less than 8 minutes using 1,008 NVIDIA Volta GPUs of the Summit supercomputer. This represents the first ever graph network generation at this scale of parallel execution with over thousand GPUs. Moreover, our algorithm is uniquely suitable for generating networks in a streaming mode without the need for explicitly storing (writing to disk) the entire network, and is suitable for targeting even larger scales with quadrillions of edges.

We study the impact of edge additions on the community structure using Lancichinetti-Fortunato-Radicchi (LFR) benchmark networks. We show that, for a fixed network size, the impact of edge additions is greater on networks with initially weak community structure than on networks with strongly clustered structures. Also, we find that the perception of the impact is also dependent on the community detection algorithm used to uncover communities.

A novel parallel algorithm, cuPPA, is presented for generating random scale-free networks using the preferential attachment model. The algorithm is custom-designed for ‘single instruction multiple data (SIMD)’ for GPUs. Our algorithm is the first to exploit GPUs, and also the fastest implementation available today, for scale-free networks. On an NVidia GeForce 1080 GPU, cuPPA generates a scale-free network of two billion edges in less than 3 s. On multi-GPU platforms, cuPPA-Hash generates a scale-free network of 16 billion edges in less than 7 s using a machine consisting of 4 NVidia Tesla P100 GPUs.

A novel parallel algorithm, cuPPA, is presented for generating random scale-free networks using the preferential-attachment model. In one of the best cases, when executed on an NVidia GeForce 1080 GPU, cuPPA generates a scale-free network of two billion edges in less than 3 seconds.

A novel parallel algorithm is presented for generating random scale-free networks using the preferential-attachment model. In one of the best cases, when executed on an NVidia GeForce 1080 GPU, cuPPA generates a scale free network of a billion edges in less than 2 seconds.

A methodology and its associated algorithms are presented for mapping a novel, field-based vehicular…

A detailed introduction to the design, implementation, and use of network simulation tools is presen…

[Pub 44]