<p>This question was posted more than 8 years ago, and much progress was done since then. However, <strong>many questions remain open, even very natural ones</strong> like sampling a random graph with prescribed clustering coefficient. Also, sampling <em>simple</em> graphs (no loop, no multi-edge) with prescribed degree sequence made much progress but remains difficult.</p>
<p>I would like to give a pointer to <strong>a quite comprehensive and recent survey</strong> on many aspects of these questions, which I think may be of interest to most readers of this post:</p>
<p><em><a href="https://arxiv.org/abs/2003.00736" rel="nofollow noreferrer">Recent Advances in Scalable Network Generation</a></em> by
Manuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders, Christian Schulz, 2020</p>
<p>For the specific problem of graphs with prescribed degree sequence, I recommend:</p>
<ul>
<li><em><a href="https://arxiv.org/abs/1608.00607" rel="nofollow noreferrer">Configuring Random Graph Models with Fixed Degree Sequences</a></em> by
Bailey K. Fosdick, Daniel B. Larremore, Joel Nishimura, Johan Ugander, 2016</li>
<li><em><a href="https://arxiv.org/abs/1905.03446" rel="nofollow noreferrer">Fast uniform generation of random graphs with given degree sequences</a></em> by
Andrii Arman, Pu Gao, Nicholas Wormald, 2020</li>
</ul>
<p>but this is a very partial list, of course.</p>
<p>The last reference has a dedicated discussion of the regular case.</p>

CC BY-SA 4.0
2021-02-17T23:02:59.237Z
2021-02-18T14:13:28.690Z
2021-02-18T14:13:28.690Z
Matthieu Latapy
<p>This certainly isn't the most advanced algorithm, but it should be able to do what you need:</p>

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

<ol>
<li>Let $G$ be the empty graph on $n$ vertices, with $n$ even.</li>
<li>Pick a perfect matching for $n$</li>
<li>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.</li>
</ol>

<p>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</p>

<ul>
<li>The perfect matchings are constructed greedily uniformly at random</li>
<li>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$)</li>
<li>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)}$)</li>
</ul>

<p>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.</p>

<p>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).</p>

CC BY-SA 3.0
2012-11-18T21:57:34.917Z
2012-11-18T21:57:34.917Z
William Macrae
<p>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.</p>

<p>My question concerns a specific case: I want to generate a few <em>undirected regular</em> 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.</p>

<p>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?</p>

CC BY-SA 3.0
2012-11-18T02:52:05.223Z
More specifics on _why_ you want to do this would probably be helpful. When you mention "degree distribution", do you mean you want to find different graphs for a particular degree sequence (which specifies all of the degrees exactly), or are you just looking for _similar_ degrees (perhaps something with a long tail, for example, which could simulate Twitter). Is your degree distribution normal or regular or uniform? Any of those would probably help greatly too.
William Macrae
CC BY-SA 3.0
2012-11-18T13:04:24.603Z
@WilliamMacrae, my specific question is to generate *regular* graphs of the *same* degree (e.g. 3 graphs and every node of them has 3 connections) but with different clustering coefficients and average path lengths. the more general question is to generate graphs given a single degree distribution (yes, that can be specified using a sequence of degrees) but with different CCs and APLs. The reason I want to do this is to use these graphs to perform some comparative analysis in an application with a fixed parameter of degree distribution, but varying parameters of CCs and APLs.
skyork
CC BY-SA 3.0
2012-11-19T10:59:44.450Z
Sage can generate random regular graphs for you.  They cite two references for their algorithm, [Kim, Jeong Han and Vu, Van H. Generating random regular graphs](http://doi.acm.org/10.1145/780542.780576) and Steger, A. and Wormald, N. Generating random regular graphs quickly.
John K.
CC BY-SA 4.0
2021-02-18T14:11:22.900Z
You may be interested by the following discussion, close to your specific question on regular graphs with prescribed path lengths: https://mathoverflow.net/questions/382508/generating-a-random-graph-with-bounds-on-degree-and-diameter
Matthieu Latapy
<ds.algorithms><graph-theory><graph-algorithms><big-list>
Algorithms for graph generation given parameters
skyork
# Algorithms for graph generation given parameters

(Asked by: username_0 on 2012-11-17)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, big-list
> **Comments:**
> **username_1**: More specifics on _why_ you want to do this would probably be helpful. When you mention "degree distribution", do you mean you want to find different graphs for a particular degree sequence (which specifies all of the degrees exactly), or are you just looking for _similar_ degrees (perhaps something with a long tail, for example, which could simulate Twitter). Is your degree distribution normal or regular or uniform? Any of those would probably help greatly too.  
> **username_0**: @WilliamMacrae, my specific question is to generate *regular* graphs of the *same* degree (e.g. 3 graphs and every node of them has 3 connections) but with different clustering coefficients and average path lengths. the more general question is to generate graphs given a single degree distribution (yes, that can be specified using a sequence of degrees) but with different CCs and APLs. The reason I want to do this is to use these graphs to perform some comparative analysis in an application with a fixed parameter of degree distribution, but varying parameters of CCs and APLs.  
> **username_2**: Sage can generate random regular graphs for you.  They cite two references for their algorithm, [Kim, Jeong Han and Vu, Van H. Generating random regular graphs](http://doi.acm.org/10.1145/780542.780576) and Steger, A. and Wormald, N. Generating random regular graphs quickly.  
> **username_3**: You may be interested by the following discussion, close to your specific question on regular graphs with prescribed path lengths: https://mathoverflow.net/questions/382508/generating-a-random-graph-with-bounds-on-degree-and-diameter  

---

## 2 answers

### Answer by username_3 on 2021-02-17. Score: 3

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](https://arxiv.org/abs/2003.00736)* 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](https://arxiv.org/abs/1608.00607)* by
  Bailey K. Fosdick, Daniel B. Larremore, Joel Nishimura, Johan Ugander, 2016
* *[Fast uniform generation of random graphs with given degree sequences](https://arxiv.org/abs/1905.03446)* 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 by username_1 on 2012-11-18. Score: 1

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).


---

