Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

G(n,p)

We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This model is referred to as G(n,1/2) or more generally G(n,p).

Random graphs with prescribed marginal behavior

Now, suppose that rather than prescribe the probability for every edge, you presecribe the marginal probability for every induced subgraph H on r vertices. (So r should be a small integer, 3,4,5, etc.) You make the additional assumptions that

a) the probability $p_H$ does not depend on the identity of the r vertices,

and

b) It depends only on the isomorphism type of $H$.

So, for example: for r=3 you can think about the case that $p_H = 1/9$ if H is a triangle or an empty graph and $p_H=7/54$ otherwise.

Once these $p_H$ are assigned you consider among all the probability distributions with these marginal behavior (if there are any) the one with maximal entropy. (But this choice is negotiable; if there is something different worth doing this is fine too.)

My questions:

1) Are these models studied in the literature?

2) When are such $p_H$'s feasible?

3) Given such feasible $p_H$'s say on graphs with 4 vertices, is there a quick algorithm to sample from the maximal-Entropy distribution which will allow to experiment with this model?

Background

This question is motivated by a recent talk by Nati Linial in our "basic notion" seminar on extremal graph theory. (Maybe these are well studied models that I simply forgot, but I don't recall it now.)

share|improve this question
1  
Great question! The difficulty for these is that the random variables involved are no longer independent. If I remember correctly, there is a decent way to handle triangles and stars which are useful when studying social networks and epidemiology. I'll try to dig up that reference... –  François G. Dorais May 23 '10 at 17:53
5  
Gil, this feels like things that Bela Bollobas, Svante Janson and Oliver Riordan have thought about. If you don't mind using old-fashioned methods, then contacting one of them by email might be a good starting point. –  gowers May 23 '10 at 21:25
2  
I was remembering notes from a colleague along the lines of what Leandro described. I think such models are also widely studied in physics. There is a relevant paper by Park and Newman where they get some precise information on the 2-star case: Phys. Rev. E (3) 70 (2004) - ams.org/mathscinet-getitem?mr=2133810 –  François G. Dorais May 23 '10 at 21:30
3  
I can't help noticing that email is getting old-fashioned... –  Victor Protsak May 24 '10 at 6:34
    
Tim, sure, I will ask Bela, Svante, and Oliver (and perhaps a couple of others). I think that asking via email, or even the old-fashion habit of just thinking about the problem on my own, have still more advantages. But it is exciting to explore new paths. –  Gil Kalai Jun 1 '10 at 7:14
show 1 more comment

3 Answers

up vote 11 down vote accepted

The Lovasz-Szegedy theory of graphons is likely to be relevant. Every measurable symmetric function $p: [0,1] \times [0,1] \to [0,1]$ (otherwise known as a graphon) determines a random graph model, in which every vertex v is assigned a colour c(v) uniformly at random from the unit interval [0,1], and then any two vertices v, w are connected by an edge with an independent probability of p(c(v),c(w)). These are in some sense the only models of large graphs in the sense that any sequence of increasingly large graphs has a subsequence that converges to a graphon (in the sense that the $p_H$ statistics converge).

Each $p_H$ (in the asymptotic limit $n \to \infty$) can be read off from the graphon as an integral. For instance, the density of triangles is $\int\int\int_{[0,1]^3} p(x,y) p(y,z) p(z,x)\ dx dy dz$.

If the $p_H$ are specified for all finite graphs H, then this determines p up to change of variables (measure-preserving bijections on [0,1]) outside of a set of measure zero. But if one only specifies the $p_H$ for a finite number of H then there are multiple choices for p (and in some cases, no choices at all) and it is not obvious to me how to find a solution or even to determine whether when a solution exists. (Note that even for just two choices of H, one being an edge and the other being a bipartite graph, the question of determining the possible values of $p_H$ is essentially Sidorenko's conjecture, which is still not fully resolved.) But perhaps numerical methods (annealing, gradient descent, etc.) may be able to find solutions some of the time (though they will hardly be "canonical").

share|improve this answer
add comment

(It is not an answer but I put it here because I am having problems to post it in the comments)

Hi Gil, thinking about the question 3 comes in my mind the Gibbs measures. It does not maximize the entropy, but it is extremal in the sense I will describe below:

Let be $\Omega_n$ the collection of all subgraphs of $K_n$ and be $E_n:\Omega\to\mathbb R$ a function having the same values any any pairs of isomorphic subgraphs. So the Gibbs measure determined by $E_n$ is $$\mu_n(\{H\})=\frac{e^{-E_n(H)}}{Z_n}$$, where $Z_n=\sum_{H\in\Omega_n}e^{-E_n(H)}$. This probability measure don't have the property of maximize the entropy but instead it solves the problem $$ \sup_{\mu\in \mathcal M} \left[ h(\mu)-\int_{\Omega_n} E_n d\mu\right]. $$ having the function $E_n$ writing down you could use the algorithms similar to the ones we have for the Ising model to sample the random graphs.

share|improve this answer
    
This seems very nice; how should we design the E_n's so that they will give us the required marginal probability on small graphs? And otherwise will have a large "support". Certainly thinking about Gibbs measures and the Ising model example looks useful. –  Gil Kalai May 23 '10 at 18:49
    
If the Tutte polynomial is computable ( I really don't know if they are), we could try to use some special values of it. Because it captures the information you want to be invariant, like isomorphism class. If they were computable, maybe multiplying it for some quantity that depends on the number of edges and vertices could give us some thing that is invariant for Isomorphism at the same time, take care about the geometry and the sizes involved. –  Leandro May 23 '10 at 19:24
    
For instance, $E_N(H)= -V(H)E(H)T_H(2,1)$ Is invariant for isomorphisms and also have small values of probability for small subgraphs. –  Leandro May 23 '10 at 19:33
add comment

ERGM (the exponential random graph model), well studied in the sociology / social network analysis literature, does something like this: it fixes a vertex set, assigns a weight to each of some given set of features (which commonly include small induced subgraphs as you suggest) and sets the probability of seeing any particular graph on the given vertex set to be exp(sum w_i)/Z where Z is a normalizing constant and the terms in the sum are the weights of the features that are present in the graph.

The features and their weights may depend on the individual vertices, so that not every induced subgraph of the same isomorphism class has the same effect on the probability, or they may be symmetric.

Usually nothing (including Z) can be computed exactly, so the social scientists resort to Markov chain Monte Carlo methods for solving statistical inference problems on these models (e.g., generating graphs with the right probabilities for a given set of weights, or inferring the weights from a given set of data). More specifically, one can perform a random walk in which each step uses the Metropolis-Hastings rule to decide whether or not to add or remove a randomly chosen edge; this converges eventually to the correct distribution and the sociologists don't seem to be too concerned that they don't really know how soon the convergence time is.

share|improve this answer
    
I presume one of the uncomputable quantities is the actual probability that a given induced subgraph appears... –  Dylan Thurston Jun 13 '10 at 13:41
    
Yes, sadly. And "uncomputable" is not true in any mathematical sense (Z is just a finite sum over all possible graphs with a given number of vertices), only a practical one. –  David Eppstein Jun 13 '10 at 14:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.