Dear Tiago,
I happened to be looking at the code for random graph generation (graph_generation.hh). The code checks whether a generated degree sequence is Graphic or not using Erdos-Gallai condition. If the condition is not satisfied, the code seems to randomly choose a vertex and re-generate its degree. This is logical in most cases.
However, if any of the degree value is greater than "n-1", the size of the graph, clearly a simple graph cannot be generated from such sequence, and it should be immediately changed by re-generating degrees for such vertices. This happens a lot when the degrees are sampled from a right-skewed distribution. But I don't see anything like this in the code. My question is, isn't it inefficient to keep randomly choosing vertices one at a time and change their degrees until the vertices with degree greater than n-1 are reassigned degrees? Is it being done for correctly sampling from a given degree distribution? Or am I missing something? Thank you.
Best regards, SMS
I would highly appreciate if Tiago or anyone else in this list has an answer to my question in the trailing e-mail. Thank you.
On 30/04/22 10:19, Snehal Shekatkar wrote:
Dear Tiago,
I happened to be looking at the code for random graph generation (graph_generation.hh). The code checks whether a generated degree sequence is Graphic or not using Erdos-Gallai condition. If the condition is not satisfied, the code seems to randomly choose a vertex and re-generate its degree. This is logical in most cases.
However, if any of the degree value is greater than "n-1", the size of the graph, clearly a simple graph cannot be generated from such sequence, and it should be immediately changed by re-generating degrees for such vertices. This happens a lot when the degrees are sampled from a right-skewed distribution. But I don't see anything like this in the code. My question is, isn't it inefficient to keep randomly choosing vertices one at a time and change their degrees until the vertices with degree greater than n-1 are reassigned degrees? Is it being done for correctly sampling from a given degree distribution? Or am I missing something? Thank you.
Best regards, SMS
Am 30.04.22 um 06:49 schrieb Snehal Shekatkar:
However, if any of the degree value is greater than "n-1", the size of the graph, clearly a simple graph cannot be generated from such sequence, and it should be immediately changed by re-generating degrees for such vertices. This happens a lot when the degrees are sampled from a right-skewed distribution. But I don't see anything like this in the code. My question is, isn't it inefficient to keep randomly choosing vertices one at a time and change their degrees until the vertices with degree greater than n-1 are reassigned degrees? Is it being done for correctly sampling from a given degree distribution? Or am I missing something?
This can be implemented in a trivial way simply by rejecting these large numbers already in the `deg_sampler` function that you supply to random_graph().
-
Snehal Shekatkar -
Tiago de Paula Peixoto