Abstract
The R-MAT graph generator introduced by Chakrabarti, Faloutsos, and
Zhan offers a simple, fast method for generating very large directed graphs.
These properties have made it a popular choice as a method of generating graphs for objects of study in a variety of disciplines, from social network analysis to high performance computing.
We analyze the graphs generated by R-MAT and model the generator in terms of occupancy problems in order to prove results about the degree distributions of these graphs. We prove that the limiting degree distributions can be expressed as a mixture of normal distributions, contradicting the widely held belief that R-MAT degree distributions exhibit the power law or scale free distribution observed in many real world graphs. Additionally, this paper offers an efficient computational technique for computing the exact degree distribution, as well as concise expressions for a number of properties of R-MAT graphs.