Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
See also the question Generating inputs for random-testing graph algorithms? –  Juho Nov 22 '12 at 3:28

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

share|improve this answer

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.