How to define probability over graphs?

How can one formally define a random graph variable?

If G is a random graph variable, then any finite graph is a realization of G. Formally a r.v maps the set of outcomes to a measurable space (may be Real or not). So, what does this set of possible outcomes look like if the r.v is a graph structure and what does the r.v map it to ?

Further, how do we assign probability to elements of the set of all finite graphs ?

I am not able to find resources that talk about these points and their properties.

I am aware that a whole field "Random Graphs" exists but, it only talks about graphs with size n and probability is defined over occurrence of edges.

2 Answers

So, what does this set of possible outcomes look like if the r.v is a graph structure and what does the r.v map it to?

Further, how do we assign probability to elements of the set of all finite graphs ?

$$\newcommand\B{\mathscr B}$$Suppose that the set of vertices of each realization of the finite random graph $$G$$ is $$[n]=\{1,\dots,n\}$$ for some natural $$n$$. Let $$S_n$$ denote the set of all graphs with the vertex set $$[n]$$. Then all realizations of $$G$$ are in the set $$S:=\bigcup_{n=1}^\infty S_n.$$ For each natural $$n$$, the set $$S_n$$ is finite and hence the set $$S$$ is countable.

Let $$\B_n$$ and $$\B$$ denote the powersets of $$S_n$$ and $$S$$, respectively. Let $$P_n$$ be any probability measure on $$\B_n$$; for instance, one can let $$P_n$$ be the uniform distribution over the set $$S_n$$. Take any sequence $$(p_n)_{n=1}^\infty$$ of nonnegative real numbers such that $$\sum_{n=1}^\infty p_n=1$$. Define the probability measure $$P$$ on $$\B$$ by the formula $$P(A):=\sum_{n=1}^\infty p_n P_n(A\cap S_n) \tag{1}$$ for all $$A\in\B$$.

Then the random graph $$G$$ can be defined on the probability space $$(S,\B,P)$$ as the identity mapping of $$S$$ to itself ($$G(g):=g$$ for all graphs $$g\in S$$). Then the distribution of the random graph $$G$$ will obviously be $$P$$.

Since any probability measure on $$\B$$ can be represented by (1), this way you can define a random graph with values in $$S$$ and any prescribed distribution over $$S$$ (that is, any prescribed distribution on the $$\sigma$$-algebra $$\B$$).

One simple way is to first take a random integer, and then generate a random graph with that size. Typically, take a Poisson distribution, so that you'll be able to control the typical size of your graph.

You can't have a uniform probability over a countable infinite set, so you're bound to have a way to decrease the probability of some graphs sizes anyway.

Other approaches build graphs locally, with Boltzmann generators. Those approaches don't let you control the exact size of the graph, which, for some time, made some people cringe because the asymptotic analysis is less straightforward. But they allow to generate very efficiently graphs with given structural properties, which is sometimes harder to do once the vertex set is fixed.