# Satz

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

$$\label{eqn:function} \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}\\$$

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

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

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

and conversely

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

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:

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

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