Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  William Macrae Nov 18 '12 at 2:52
    
@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 Nov 18 '12 at 13:04
    
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 and Steger, A. and Wormald, N. Generating random regular graphs quickly. –  Pål GD Nov 19 '12 at 10:59
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.