3
$\begingroup$

Given a random graph $G(n, p)$, where $n$ is the number of nodes and $p$ is the probability of connecting any two edges, it is known that $t = \frac{\ln(n)}{n}$ is a threshold for the connectedness of the graph: if $p$ is greater than $t$ the graph will be almost surely connected, otherwise disconnected. The farther you move $p$ from the threshold the higher the chance that the resulting graph will be disconnected/connected (source: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model).

I am currently trying to output from an Erdős–Rényi process a graph that is as sparse as possible. In my case $n=10000$ and therefore $t=0.00092$, which means that a connected random graph of 10000 nodes should have on average 46000 edges. Through testing with igraph I could go as low as 37000 edges: $t=0.00074$. Now I'm stuck (because the probability of outputting a sparser graph is too low) and I don't know how to further lower the degree of the graphs. Is there a way to generate sparser random graphs? I know I'm already far below the threshold. In case no solution is found for this model what is the best way to generate a very sparse connected graph?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – orlp
    Commented Feb 2, 2021 at 15:27
  • $\begingroup$ 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. $\endgroup$
    – Gilbes
    Commented Feb 2, 2021 at 17:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – orlp
    Commented Feb 2, 2021 at 17:14
  • $\begingroup$ 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. $\endgroup$
    – Gilbes
    Commented Feb 2, 2021 at 17:30
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Commented Feb 3, 2021 at 0:45

1 Answer 1

Reset to default
2
$\begingroup$

Brenday McKay suggests an algorithm on mathoverflow. He considers a fixed number of edges, but you can also sample from $G(n,p)$ according to his method. First, calculate $c_{n,m}$ for all $m$. Then sample $m$ in proportion to $p^m (1-p)^{\binom{n}{2}-m} c_{n,m}$. Then use his algorithm.

Gray, Mitchell, and Roughan, Generating connected random graphs, suggest an MCMC algorithm, and analyze it empirically.

Both of these algorithms are for sampling $G(n,p)$ random graphs conditioned on the result being connected. There are also many heuristics for sampling other distributions of random connected graphs in the sparse regime, where usually the focus is on generating some "random-looking" distribution rather than a specific one. For example, you can generate a $G(N,p)$ random graph and pick a connected component, or you can add a random spanning tree to a $G(n,p')$ random graph.

Improve this answer
$\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.