Timeline for Generating sparse connected Erdős–Rényi random graphs
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 3, 2021 at 0:45 | comment | added | D.W.♦ | You say "sparser random graphs" but do you want to require that the output be connected? What distribution do you want it to have? Do you want to sample from the distribution given by the Erdős–Rényi process, conditioned on the resulting graph being connected and having fewer edges than some threshold? | |
| Feb 2, 2021 at 20:44 | answer | added | Yuval Filmus | timeline score: 2 | |
| Feb 2, 2021 at 17:35 | history | edited | Gilbes | CC BY-SA 4.0 |
deleted 200 characters in body
|
| Feb 2, 2021 at 17:30 | comment | added | Gilbes | My objective was indeed to try and see if I could directly generate the graph. But now I think the best way to get such graph is to manipulate some spanning tree of the graph. I think it would also be less expensive complexity-wise whenever I'll put more nodes in. Thank you really much for the tree suggestion, it basically solved the case. | |
| Feb 2, 2021 at 17:14 | comment | added | orlp | The reason I ask is because you're evidently aware of the limitations of your original definition. If you insist that 'a randomly generated graph' must be generated in the way you define with a fixed connection probability $p$ then the result you cite applies and it becomes exceedingly rare that the graph is connected. Another alternative to generate sparse graphs that aren't trees is to repeatedly pick two random vertices and connect them, continuing until the graph is fully connected. Or applying this method after the original method is done and the result wasn't fully connected. | |
| Feb 2, 2021 at 17:07 | comment | added | Gilbes | No, random means that for each node i we add an edge directed to another node j with probability p. In this case I suppose the graph as undirected and unweighted. I do really like the idea of using a spanning tree, thank you. | |
| Feb 2, 2021 at 15:27 | comment | added | orlp | Define 'a random graph'. Is assigning random weights to edges and then computing a minimum spanning tree a 'random graph'? That would be maximally sparse yet still have a random component. | |
| Feb 2, 2021 at 14:49 | review | First posts | |||
| Feb 8, 2021 at 18:12 | |||||
| Feb 2, 2021 at 14:44 | history | asked | Gilbes | CC BY-SA 4.0 |