Menu
What is the best algorithm to generate a random simple (no parallel edges or self-loops) undirected graph with a given number of nodes, where each node has a number of edges that is no less than min and no greater than max?
For example, if min = 2 and max = 5, I would like a graph where approximately 25% of the nodes have 2 edges, approximately 25% of the nodes have 3 edges, approximately 25% of the nodes have 4 edges, and approximately 25% of the nodes have 5 edges.
209
The simplest and oldest network model is the random model, also known as Erdős-Rényi model. According to this model, a network is generated by laying down a number n of nodes and adding edges between them with independent probability p for each node pair.
To construct a random network we follow these steps: 1) Start with N isolated nodes. 2) Select a node pair and generate a random number between 0 and 1. If the number exceeds p, connect the selected node pair with a link, otherwise leave them disconnected.
You could use random_degree_sequence_graph from NetworkX, which uses an algorithm due to Bayati, Kim, and Saberi.
97
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
