An Efficient and Scalable Algorithmic Method for Generating Large-Scale Random Graphs
SessionTensor and Graph Algorithms
Session ChairHari Sundar
Authors
Event Type
Paper
Algorithms
Intermediate
Introductory
TimeTuesday, November 15th4:30pm - 5pm
Location355-D
DescriptionMany real-world systems are modeled and analyzed using various random network models. For realistic analysis, models must incorporate relevant properties such as degree distribution and clustering coefficient. Many models, such as the Chung-Lu, stochastic Kronecker, stochastic blockmodels (SBM), and block two-level Erdos-Renyi (BTER) models have been devised to capture those properties. However, the generative algorithms for these models are mostly sequential and take a prohibitively long time. In this paper, we present a novel time and space efficient algorithm for the Chung-Lu model requiring O(m) time and O(Λ) space, where m and Λ are the number of edges and distinct degrees. We also present a distributed-memory parallel algorithm with P processors requiring O(m/P+Λ+P) time and O(Λ) space. Finally, we extend our algorithms for two other popular models: SBM and BTER. These algorithms are highly scalable. Generating a power-law network with 250 billion edges takes only 12 seconds using 1024 processors.
