Algoritmos para geração de gráficos usando determinadas propriedades

Pode haver um grande número de algoritmos propostos para gerar gráficos que satisfaçam algumas propriedades comuns (por exemplo, coeficiente de agrupamento, comprimento médio do caminho mais curto, distribuição de graus, etc.).

Minha pergunta diz respeito a um caso específico: quero gerar alguns gráficos regulares não direcionados (ou seja, cada nó desses gráficos tem o mesmo número de vizinhos) com diferentes coeficientes de agrupamento e comprimentos médios de caminho mais curto. De maneira mais geral, ao fixar uma distribuição de graus, desejo gerar gráficos com diferentes coeficientes de agrupamento e comprimentos médios de caminho mais curto.

Gostaria de saber quais são os algoritmos conhecidos para fazer isso (ou, de fato, há algum?) E quais são os softwares recomendados para o mesmo objetivo?

Não há algoritmos gerais para o seu problema, mas o que geralmente se faz (para gráficos de pequenas encomendas) é

1. Use nauty para gerar gráficos que satisfaçam algumas restrições grosseiras (você pode fazer nauty gerar apenas (bi) gráficos conectados, gráficos regulares, gráficos livres de triângulo / quadrângulo, ..)

2. Use um programa externo para extrair apenas os gráficos necessários em relação a algumas propriedades adicionais desejadas.

Você pode fazer 1 e 2 em sálvia ! Por exemplo, considere que você deseja gerar todos os gráficos regulares regulares 5 da ordem 20 que têm distância média 10 (índice de Wiener ??) e algum coeficiente de agrupamento. Você faz o seguinte

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

Deixe-me saber se você precisa de respostas mais específicas relacionadas ao sábio.