Functional Ball Dropping
fast hypergraph generation
Implements 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 105 or even 1010 depending on the model and host machine. This package is capable of producing ordinary graphs by setting maximum hpyerdegree to 2.
Usage
]add https://github.com/LilithHafner/FunctionalBallDropping.jl
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!
Performance
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:
| Model \ Size | 10 | 102 | 103 | 104 | 105 | 106 | 107 |
|---|---|---|---|---|---|---|---|
| Preferential Attachment | 203 | 208 | 103 | 77 | 88 | 141 | 223 |
| Degree Corrected Stochastic Block | 25750 | 2137 | 281 | 85 | 52 | 39 | 29 |
| Kronecker | 196 | 54 | 58 | 85 | 71 | 54 | 45 |
| Typing | 305 | 187 | 188 | 187 | 187 | 252 | 448 |
| Uniform | 28 | 9 | 9 | 14 | 14 | 15 | 11 |
A forthcoming paper utilizing results from FBDCompare.jl compares the performance of this package to the previous state of the art.