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:
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:
the space of equivalence classes of correlation matrices \(\widetilde{C}_{n\times n}\),
the space of unweighted adjacency matrices \(\mathcal{A}_{n\times n}=\left(A,2^{A},P_{A}\right)\),
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.
(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
∎