Algorithms for generating random graphs Applied to Dutch company networks

Abstract

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.