Problem Detail: 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?
Asked By : skyork
Answered By : Jernej
There are no general algorithms for your problem but what one usually does (for graphs of small orders) is
- Use nauty to generate graphs satisfying some rough constraints (you can make nauty generate only (bi)connected graphs, regular graphs, triangle/quadrangle free graphs,..)
- 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6744
