Algorithms for graph generation given parameters

Question

I guess there may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g. clustering coefficient, average path length, degree distribution, etc). I am new to this field, and some google search didn't find me a thorough review of the literature.

My question concerns a specific case: I want to generate a few undirected regular graphs (i.e. each node of each graph has the same number of edges) with different clustering coefficients and average path lengths. More generally, while fixing a degree distribution, generate graphs by varying clustering coefficient and average path length.

I wonder what are the well-known algorithms for doing this (or links to relevant literature reviews would be great too!), and what are the recommended software for generating such graphs?

Answer 1

This question was posted more than 8 years ago, and much progress was done since then. However, many questions remain open, even very natural ones like sampling a random graph with prescribed clustering coefficient. Also, sampling simple graphs (no loop, no multi-edge) with prescribed degree sequence made much progress but remains difficult.

I would like to give a pointer to a quite comprehensive and recent survey on many aspects of these questions, which I think may be of interest to most readers of this post:

Recent Advances in Scalable Network Generation by Manuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders, Christian Schulz, 2020

For the specific problem of graphs with prescribed degree sequence, I recommend:

• Configuring Random Graph Models with Fixed Degree Sequences by Bailey K. Fosdick, Daniel B. Larremore, Joel Nishimura, Johan Ugander, 2016
• Fast uniform generation of random graphs with given degree sequences by Andrii Arman, Pu Gao, Nicholas Wormald, 2020

but this is a very partial list, of course.

The last reference has a dedicated discussion of the regular case.

Answer 2

This certainly isn't the most advanced algorithm, but it should be able to do what you need:

A subset of the $d$-regular graphs are the $d$-regular graphs that are 1-factorizable (they're a union of perfect matchings). So

1. Let $G$ be the empty graph on $n$ vertices, with $n$ even.
2. Pick a perfect matching for $n$
3. If none of the edges in your perfect matching are already in $G$, add the whole matching to $G$ (else discard it). If $G$ has degree $d$, halt; otherwise go to 2.

The key comes in with how you perform step 2. If $d$ is fairly small, then a greedy random algorithm that avoids edges in $G$ should work. As $d$ gets larger the probability that an iteration doesn't increase the degree of your graph grows, and you'll need to start using a matching algorithm or at least looking for augmenting paths. I've deliberately underspecified step 2, because it is also where you'll get the variation in graph properties. For example, if $d$ is small you could run the algorithm 3 times with the following variations to step 2

• The perfect matchings are constructed greedily uniformly at random
• The perfect matchings are constructed greedily with $v$ being matched to $u$ with higher weight if $u$ is further from $v$ (give each unmatched vertex $u$ weight $d(v,u)$ when picking which is matched to $v$)
• The perfect matchings are constructed greedily with $v$ being matched to $u$ with higher weight if $u$ is closer to $v$ (give each unmatched vertex $u$ weight $\frac{1}{d(u,v)}$)

Also note, if $d$ is large but $n - d$ is not, you can do all of this and then take $\overline{G}$. If $d$ is $\frac{n}{2}$ or such, you'll need to be much smarter about step 2, probably implementing an algorithm to find a matching in the remaining graph.

Regardless, unless you're keen on using graphs that aren't 1-factorizable, approaching it 1 degree at a time makes sense, because the marriage theorem tells you that you should always be able to perform step 2 to add another perfect matching (since the remaining edges are a regular graph, so they have a perfect matching).