Randomly generating graph based off number of connections on each node

Question

I'm trying to generate a graph based off some data I have.

This graph should have N nodes where the number of edges each node has is equal to a random number P(k), where k is the "index" of the node (mostly arbitrary).

My question is, is there an actual way to do this? I'm thinking that I need more data that either determines the density or another degree of connections out (N1->N2->N3), but I'm not entirely sure.

Answer 1

You essentially want to generate a graph with some degree sequence (which you want to be random, but this is not relevant); this is called the graph realization problem which is solved e.g. by the Havel-Hakimi algorithm in the sense that the algorithm will return a (simple) graph with the desired degree sequence if that is possible (such sequences are called graphic). Note that not all finite sequences over $\mathbb N$ are graphic as e.g. any sequence whose members sum to an odd number cannot be graphic by the handshake lemma (which states that the sum of all degrees in a graph is equal to 2 times the number of edges in a graph and thus even). Further, the solutions will in general not be unique: The degree sequence $(2, 2, 2, 2, 2, 2)$ for example can be realized by the cycle graph $C_6$ of size $6$ or the disjoint union $C_3 \mathop{\dot\cup} C_3$ of two cycle graphs $C_3$ of size $3$ each.

Many graph libraries for programming languages have implementations of algorithms for this problem, for example the Python library networkx.