Functional Ball Dropping

Uses the functional ball dropping technique to provide efficient generators for a variety of hypergraph (henceforth graph) models inlcuding

• Hyper preferential attachment (Do, Yoon, Hooi, & Shin)
• Degree corrected hyper stochastic block (Chodrow, Veldt, & Benson)
• Hyper Kronecker product (Eikmeier, Ramani, & Gleich)
• Hyper typing model (Chang & Chen)
• Uniform homogonous (Erdős & Rényi)

In all cases, maximum edge size (also known as hyperdegree) can vary from 1–30. In many cases it can range all the way up to 10⁵ or even 10¹⁰ depending on the model and host machine. This package is capable of producing ordinary graphs by setting maximum hpyerdegree to 2.

using FunctionalBallDropping
graph = example(Kronecker_sampler, 30)

10-element Vector{Tuple{Int64, Int64, Int64}}:
 (6, 0, 2)
 (3, 0, 0)
 (0, 5, 5)
 (1, 2, 2)
 (4, 2, 1)
 (0, 4, 0)
 (2, 6, 4)
 (1, 4, 5)
 (5, 7, 6)
 (0, 2, 0)

See src/examples.jl for examples!

Medium and large graphs are produced at a rate of 3 million to 150 million edges in the bipartite projection per second for all models on a single threaded 1.6 Ghz machine. The number of clock cycles per bipartite edge for each model at a variety of scales is approximately as follows:

A forthcoming paper utilizing results from FBDCompare.jl compares the performance of this package to the previous state of the art.