Linear work generation of R-MAT graphs. (29th December 2020)

• Record Type: Journal Article
• Authors: Hübschle-Schneider, Lorenz; Sanders, Peter
• Is Part Of: Network science. Volume 8:Number 4(2020)
• Page Start: 543
• Page End: 550
• Publication Date: 2020-12-29
• Subjects: graph generator, -- parallel processing, -- large graphs, -- bit parallelism, -- sampling; Social networks -- Research -- Periodicals; System analysis -- Periodicals; System theory -- Periodicals; Computer science -- Periodicals; 003.72
• DOI: 10.1017/nws.2020.21
• Languages: English
• ISSNs: 2050-1242

Abstract

Abstract: R-MAT (for Recursive MATrix) is a simple, widely used model for generating graphs with a power law degree distribution, a small diameter, and communitys structure. It is particularly attractive for generating very large graphs because edges can be generated independently by an arbitrary number of processors. However, current R-MAT generators need time logarithmic in the number of nodes for generating an edge— constant time for generating one bit at a time for node IDs of the connected nodes. We achieve constant time per edge by precomputing pieces of node IDs of logarithmic length. Using an alias table data structure, these pieces can then be sampled in constant time. This simple technique leads to practical improvements by an order of magnitude. This further pushes the limits of attainable graph size and makes generation overhead negligible in most situations.