0

Let $G(n,p)$ be the usual random graph on $n$ vertices with each edge existing independently with probability $p$ (no self loops , or double edges not are allowed). I would like to simulate the distribution of a random graph given the event $T\geq a$ where $T$ is the number of triangles in the random graph. The natural approach is Metropolis Hastings. I've already found some semi-efficient algorithms that approximate the number of triangles in a given random graph, however I am still at a loss of what Markov chain to pick for a good rate of convergence. I would immensely appreciate a push in the right direction. In particular, some references would be fantastic. Thanks!

flag
what value of $a$ are you interested in? Also, if you are interested in computing expectations of the form $E[\phi(G) | T(G) \geq a]$, importance sampling might just work as well. – Alekk Apr 26 2012 at 23:33
My question would be: which values of $p$ are you interested in? Are you talking about the regime where you expect to have lots of triangles or few? – Anthony Quas Apr 26 2012 at 23:41
@Alekk: I am interested in all values of $a$ but in particular for $a>E(T)$ which is on the order of $n^3p^3/6$. I'm not so much interested in calculating expectations as just seeing what the graphs look like. – Alex R. Apr 27 2012 at 2:11
@Anthony Quas: I would be interested in all (fixed) values of $p$. What I am sure of is the number of triangles is expected to be much less than $a$, which translates to $P(T\geq a)$ being very small by itself. – Alex R. Apr 27 2012 at 2:13
@Alex R: just being curious but how are you planning to "see what the graphs look like"? For small graphs that might be easy to plot some of them, but for large graphs I think that you are going to compute some expectations (number of copie of K_4, is it connected, etc...), aren't you? – Alekk Apr 27 2012 at 8:48
show 3 more comments

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.