I have a finite undirected graph with a probability $p_e$ given for each edge $e$. This gives a random graph by removing each edge e with probability $1-p_e$ independently of the others.

I'm interested in computing probabilities like the probability that some given subset of the graph is connected (in particular pairs of vertices). This seems hard to do exactly. Has it been proven to be hard? Are there approximation algorithms?

Also, I am interested in sampling from the distribution conditioned on certain subsets being connected (again, just conditioning on a pair of vertices being connected seems interesting enough). How to do this?

  • $\begingroup$ Does your graph have more structure? The classical results are for the complete graph, and special cases that are easy to analyse like paths, barbells, or complete bipartite graphs. $\endgroup$ – András Salamon May 5 '16 at 12:56
  • $\begingroup$ No, though any results on special cases are of interest. Since my probabilities are general, the complete graph contains all other graphs by letting some p_e's be 0. $\endgroup$ – crestmods May 5 '16 at 13:10
  • 3
    $\begingroup$ I think you are asking too general a question. A standard reference like the Bollobás book on random graphs doesn't even cover cases where the underlying space of graphs is not uniform. On the other hand, Ising and other statistical physics models impose a strict lattice structure on the graph as it is intended to model real systems of interacting parts. For a model as general as the one you posit, the best we have are simulations, and it is hard to draw general conclusions when there is metastability everywhere. $\endgroup$ – András Salamon May 5 '16 at 15:28
  • 1
    $\begingroup$ Have a look at Advanced Topics in Graph Theory: Random Graphs course by Mike Molloy. There are many similar courses that you can find using Google. $\endgroup$ – Kaveh May 5 '16 at 17:31
  • $\begingroup$ Another thing you might want to look at is Razborov's flag algebras. $\endgroup$ – Kaveh May 5 '16 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.