0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.