Randomly generating graph based off number of connections on each node

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.

• What did you try a) using "paper and pencil" to find a solution to a couple of examples yourself b) denoting an algorithm? Commented Sep 9, 2020 at 6:04

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.