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



Some models for random graphs that I am curious about
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").


