1
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\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
    Commented May 5, 2016 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
    Commented May 5, 2016 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
    Commented May 5, 2016 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
    Commented May 5, 2016 at 17:31
  • $\begingroup$ Another thing you might want to look at is Razborov's flag algebras. $\endgroup$
    – Kaveh
    Commented May 5, 2016 at 17:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.