Generación aleatoria de gráficos en función del número de conexiones en cada nodo

Question

Estoy intentando generar un gráfico basado en algunos datos que tengo.

Este gráfico debería tener N nodos donde el número de aristas que tiene cada nodo es igual a un número aleatorio P(k), donde k es el "índice" del nodo (en su mayoría arbitrario).

Mi pregunta es, ¿existe una manera real de hacer esto?Estoy pensando que necesito más datos que determinen la densidad u otro grado de conexiones (N1->N2->N3), pero no estoy del todo seguro.

Answer 1

Básicamente, desea generar un gráfico con alguna secuencia de grados (que desea que sea aleatoria, pero esto no es relevante);esto se llama el problema de realización de gráficos que se resuelve p.e.por el Algoritmo de Havel-Hakimi en el sentido de que el algoritmo devolverá un gráfico (simple) con la secuencia de grados deseada si eso es posible (dichas secuencias se denominan gráfico).Tenga en cuenta que no todas las secuencias finitas sobre $\mathbb N$ son gráficos como p.e.cualquier secuencia cuyos miembros sumen un número impar no puede ser gráfica por el lema del apretón de manos (que establece que la suma de todos los grados en un gráfico es igual a 2 veces el número de aristas en un gráfico y, por lo tanto, es par).Además, las soluciones en general no serán únicas:la secuencia de grados $(2, 2, 2, 2, 2, 2)$ por ejemplo, se puede realizar mediante el gráfico de ciclo $C_6$ de tamaño $6$ o la unión disjunta $C_3 \matop{\punto\copa} C_3$ de dos gráficos de ciclo $C_3$ de tamaño $3$ cada.

Muchas bibliotecas de gráficos para lenguajes de programación tienen implementaciones de algoritmos para este problema, por ejemplo la biblioteca Python. redx.