Algorithms for graph generation using given properties

Question

There may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g., clustering coefficient, average shortest path length, degree distribution, etc).

My question concerns a specific case: I want to generate a few undirected regular graphs (i.e., every node in these graphs has the same number of neighbors) with different clustering coefficients and average shortest path lengths. More generally, by fixing a degree distribution, I want to generate graphs with different clustering coefficients and average shortest path lengths.

I wonder what are the well-known algorithms for doing this (or in fact, is there any?), and what are the recommended software for the same purpose?

• Juho: See also the question Generating inputs for random-testing graph algorithms?

Answer 1

There are no general algorithms for your problem but what one usually does (for graphs of small orders) is

1. Use nauty to generate graphs satisfying some rough constraints (you can make nauty generate only (bi)connected graphs, regular graphs, triangle/quadrangle free graphs,..)

2. Use an external program to extract only the graphs you need with respect to some additional properties that you want.

You can do both 1 and 2 in sage! For example consider that you want to generate all connected 5-regular graphs of order 20 that have average distance 10 (Wiener index??) and some clustering coefficient. You do the following

for G in graphs.nauty_geng(" 20 -c -d5 -D5" ):
 if G.wiener_index() == 10 and G.clustering_coeff() == SOMETHING:
 print G.adjacency_matrix()

Let me know if you need some more specific answers related to sage.