Satz

Let \(\rho\in{\mathbb{R}}\), and the function \(f_{\rho}\) so that

\begin{equation} \label{eqn:function}f_{\rho}:C\rightarrow A\\ \\ a_{ij}=\begin{cases}1&\text{if }c_{ij}>\rho\\ 0&\text{if }c_{ij}\leq\rho\\ 0&\text{if }i=j\end{cases}\\ \end{equation}

Let \(g\) the pdf and \(G\) the cdf of each element \(c_{ij}\) of \(C\).

By defining \(p=1-G(\rho)\), we can write

\begin{equation} P(a_{ij}=0)=P(c_{ij}\leq\rho)=G(\rho)=1-p\nonumber \\ \end{equation}

and conversely

\begin{equation} P(a_{ij}=1)=P(c_{ij}>\rho)=1-G(\rho)=p\nonumber \\ \end{equation}

In a first step we define the space of correlation matrices

The space of correlation matrices \(\mathcal{C}_{n\times n}=\left(C,\mathcal{F},g_{C}\right)\) consists of all matrices where

  • -

    \(C\in{\mathbb{R}}^{n\times n}\), such that \(c_{ij}=c_{ji}\), \(c_{ii}=0\),

  • -

    \(\mathcal{F}\) is the Borel \(\sigma-\)algebra on \(C\),

  • -

    and all elements \(c_{ij}\) are i.i.d. random variables with a probability distribution \(g\).

We want to identify matrices in \(\mathcal{C}\) with adjacency matrices using a construction like the function \ref{eqn:function} defined above. As the image of \(f\) depends only on \(G(\rho)\) this map is not injective; more precisely two matrices \(C_{1}\) and \(C_{2}\) are mapped to the the same matrix \(A\) if for each pair \(i\neq j\) of indices the equation \(G(\rho)=1-p\) is satisfied. We use this relation to define equivalence classes:

\label{def:equiv_correlation}

Two matrices \(C_{1}\) and \(C_{2}\) are equivalent if the following condition is satisfied:

\begin{equation} C_{1}\sim C_{2}\quad\Leftrightarrow\quad\forall i,j\,\ f_{\rho}(c^{1}_{ij})=f_{\rho}(c^{2}_{ij})\,.\\ \end{equation}

Then the space of equivalence classes is denoted by \(\widetilde{C}_{n\times n}\).

Equivalence to random graph model Consider the following probability spaces:

  1. 1.

    the space of equivalence classes of correlation matrices \(\widetilde{C}_{n\times n}\),

  2. 2.

    the space of unweighted adjacency matrices \(\mathcal{A}_{n\times n}=\left(A,2^{A},P_{A}\right)\),

  3. 3.

    the space of random graphs \(G_{n,p}\)

where,

  • \(A\in\{0,1\}^{n\times n}\) such that \(\forall i,j\,a_{ij}=a_{ji}\text{ and }a_{ii}=0\),

  • \(P_{A}=\begin{cases}1&\text{with probability }p,\\ 0&\text{with probability }1-p\end{cases}\),

  • \(P_{C}\) is some probability distribution,

  • an adjacency matrix is a (0,1)-matrix with zeros on its diagonal.

The probability spaces are equivalent.

Proof.

(2) \(\Leftrightarrow\) (3): Given that a graph is defined unequivocally by its adjacency matrix, that all elements of \(a_{ij}\) are by definition independent and that \(P_{A}\) follows the same probability distribution as in \(G_{n,p}\), both probability spaces are equivalent. follows by the definition of \(G_{n,p}\).
(1) \(\Leftrightarrow\) (2): The equivalence of \(\widetilde{\mathcal{C}}_{n\times n}\) and \(\mathcal{A}_{n}\) is a direct consequence of the definition \ref{def:equiv_correlation} of the equivalence classes