Efficient generation of expected-degree graphs via edge-arrivals

The authors study how to quickly create random graphs where each vertex has a specific expected number of connections. They focus on models where vertices have weights, and the chance of an edge between two vertices depends on the product of their weights. Instead of generating each possible edge independently, which can be slow for large graphs, or using skipping techniques that require sorting vertices by weight, they use a different strategy. They imagine edges arriving one after another over time, up to a certain point. In this process, they allow the same edge to appear multiple times or even loops where a vertex connects to itself. After generating this multigraph, they simply remove the duplicate edges and self-loops to get the final simple graph without multiples. According to the paper, this final graph has exactly the same properties as the standard Norros-Reittu random graph model, which is known to have the desired expected degrees under certain conditions. Using this idea, they create a generator that runs in time linear with the number of vertices plus the number of edges in the output. This is faster than previous methods that take extra time for sorting. The new method is also easier to code and can be extended to directed graphs, graphs that change over time, or even more complex structures like hypergraphs. It can also benefit from running on multiple processors at once. This approach changes how we think about generating these graphs by focusing on the order edges appear rather than deciding for each pair.