Algorithms for generating random graphs Applied to Dutch company networks
Summary
Uniformly generating weighted graphs that follow a degree sequences and of which the edge weights
follow a target distribution has been studied in [Kryven, 2022]. However, an efficient implementation
is missing. Here, we develop methods that implement their algorithm. On the one hand, we develop
a method that implement the general case, where no structure of the edge weights is known and
hence they have to be stored. This is also done for the binary case, where edges are either allowed
or disallowed. These methods are expensive due to them requiring at least O(n
2
) storage and
O(n
2
), simply, due to storing the edge weights. On the other hand, we focus on the case where
the edge weights are distances and instead implement a method where the edge weights do not
have to be stored. This implementation requires O(m) storage. Whereas the run time is unclear,
it is estimated to be O(m
9
8 dmax). In the process of developing these methods, the expected run
time of the case without edge weights is improved from O(mdmax) to O(m). Next, we explore
an alternative way of sampling the edges, namely such that all vertices have an equal chance of
being sampled. This gives more control over the edge weight distributions of individual vertices,
while still outputting a graph with the desired target distribution. Lastly, we develop a method for
reconstructing the Dutch company network as an internship at Statistics Netherlands.