Functional Ball Dropping: A superfast hypergraph generation scheme

We present a straightforward paradigm for designing simple, efficient generators for a wide variety of hypergraph models. This approach yields asymptotically optimal algorithms and concise implementations that outperform existing implementations by multiple orders of magnitude. Our generalization of ball dropping, called functional ball dropping, allows us to generate models that have not been previously treated by ball dropping. We identify natural building blocks of a given hypergraph model (e.g an edge) that can be concatenated to form a sensible representation of hypergraph (e.g. a list of edges). Next, we design a sampler subject to two constraints: the sampler’s resulting distribution of hypergraphs must match the model we generate, and the runtime of the sampler must be proportional to the size of the component it samples. Our algorithm incrementally generates the graph by repeated execution of the sampling function. In this paper, we present a general description of the functional ball dropping approach before applying it to several nontrivial graph models. We present arguments for correctness and complexity of each treatment. Following theoretical analysis, we perform empirical comparative runtime analysis that demonstrates the scalability of our implementations.