Some models for random graphs that I am curious about

Question

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.)

Answer 1

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").

Answer 2

(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.

Answer 3

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.