Gerar aleatoriamente gráfico base o número de conexões em cada nó

Question

Eu estou tentando gerar um gráfico com base alguns dados que eu tenho.

Este gráfico deve ter N nós em que o número de arestas de cada nó é igual a um número aleatório P(k), onde k é o "índice" do nó (principalmente arbitrário).

A minha pergunta é, existe uma forma real de fazer isso?Eu estou pensando que eu preciso de mais dados do que determina a densidade ou a outro grau de ligações (N1->N2->N3), mas eu não sou inteiramente certo.

Answer 1

Basicamente você deseja gerar um gráfico com algum grau de sequência (o que você quer ser aleatório, mas isso não é relevante);este é o chamado gráfico realização problema o que pode ser resolvido e.g.pelo Havel-Hakimi algoritmo no sentido de que o algoritmo irá devolver uma (simples) gráfico com o grau desejado de sequência se que é possível (tais sequências são chamados de gráfico).Note que nem todas as seqüências finitas mais $\mathbb N$ são gráficos como por exemplo,qualquer sequência cujos membros soma de um número ímpar não pode ser gráfico pela aperto de mão lema (o que indica que a soma de todos os graus em um gráfico é igual a 2 vezes o número de arestas em um grafo e assim mesmo).Além disso, as soluções, em geral, não ser exclusiva:O grau de sequência $(2, 2, 2, 2, 2, 2)$ por exemplo, pode ser realizado com o ciclo gráfico $C_6$ tamanho $6$ ou disjunto união $C_3 \mathop{\dot\copa} C_3$ de duas ciclo de gráficos $C_3$ tamanho $3$ cada.

Muitas gráfico bibliotecas para as linguagens de programação têm implementações de algoritmos para este problema, por exemplo, a biblioteca em Python networkx.