# Random Graph Models¶

## This tutorial will introduce the following random graph models:¶

• Erdos-Reyni (ER)
• Degree-corrected Erdos-Reyni (DCER)
• Stochastic block model (SBM)
• Degree-corrected stochastic block model (DCSBM)
• Random dot product graph (RDPG)

### Load some data from GraSPy¶

For this example we will use the Drosophila melanogaster larva right mushroom body connectome. Here we will consider a binarized, undirected version of the graph.

:

import numpy as np
from graspy.plot import heatmap
from graspy.utils import binarize, symmetrize
%matplotlib inline

inner_hier_labels=labels,
title='Drosophila right MB',
font_scale=1.5); ### Preliminaries¶

$$n$$ - the number of nodes in the graph

$$A$$ - $$n \times n$$ adjacency matrix

$$P$$ - $$n \times n$$ matrix of probabilities

For the class of models we will consider here, a graph (adjacency matrix) $$A$$ is sampled as follows:

$A \sim Bernoulli(P)$

While each model we will discuss follows this formulation, they differ in how the matrix $$P$$ is constructed. So, for each model, we will consider how to model $$P_{ij}$$, or the probability of connection between any node $$i$$ and $$j$$, with $$i \neq j$$ in this case (i.e. no “loops” are allowed for the sake of this tutorial).

## For each graph model we will show:¶

• how the model is formulated
• how to fit the model using GraSPy
• the P matrix that was fit by the model
• a single sample from the fit model

### Erdos-Reyni (ER)¶

The Erdos-Reyni (ER) model is the simplest random graph model one could write down. We are interested in modeling the probability of an edge existing between any two nodes, $$i$$ and $$j$$. We denote this probability $$P_{ij}$$. For the ER model:

$P_{ij} = p$

for any combination of $$i$$ and $$j$$

This means that the one parameter $$p$$ is the overall probability of connection for any two nodes.

:

from graspy.models import EREstimator
er = EREstimator(directed=True,loops=False)
print(f"ER \"p\" parameter: {er.p_}")
heatmap(er.p_mat_,
inner_hier_labels=labels,
font_scale=1.5,
title="ER probability matrix",
vmin=0, vmax=1)
heatmap(er.sample(),
inner_hier_labels=labels,
font_scale=1.5,
title="ER sample");

ER "p" parameter: 0.2479666732791113  ### Degree-corrected Erdos-Reyni (DCER)¶

A slightly more complicated variant of the ER model is the degree-corrected Erdos-Reyni model (DCER). Here, there is still a global parameter $$p$$ to specify relative connection probability between all edges. However, we add a promiscuity parameter $$\theta_i$$ for each node $$i$$ which specifies its expected degree relative to other nodes:

$P_{ij} = \theta_i \theta_j p$

so the probility of an edge from $$i$$ to $$j$$ is a function of the two nodes’ degree-correction parameters, and the overall probability of an edge in the graph.

:

from graspy.models import DCEREstimator
dcer = DCEREstimator(directed=True,loops=False)
print(f"DCER \"p\" parameter: {dcer.p_}")
heatmap(dcer.p_mat_,
inner_hier_labels=labels,
vmin=0,
vmax=1,
font_scale=1.5,
title="DCER probability matrix");
heatmap(dcer.sample(),
inner_hier_labels=labels,
font_scale=1.5,
title="DCER sample");

DCER "p" parameter: 11250.0  ### Stochastic block model (SBM)¶

Under the stochastic block model (SBM), each node is modeled as belonging to a block (sometimes called a community or group). The probability of node $$i$$ connecting to node $$j$$ is simply a function of the block membership of the two nodes. Let $$n$$ be the number of nodes in the graph, then $$\tau$$ is a length $$n$$ vector which indicates the block membership of each node in the graph. Let $$K$$ be the number of blocks, then $$B$$ is a $$K \times K$$ matrix of block-block connection probabilities.

$P_{ij} = B_{\tau_i \tau_j}$
:

from graspy.models import SBMEstimator
sbme = SBMEstimator(directed=True,loops=False)
print("SBM \"B\" matrix:")
print(sbme.block_p_)
heatmap(sbme.p_mat_,
inner_hier_labels=labels,
vmin=0,
vmax=1,
font_scale=1.5,
title="SBM probability matrix")
heatmap(sbme.sample(),
inner_hier_labels=labels,
font_scale=1.5,
title="SBM sample");

SBM "B" matrix:
[[0.         0.53238095 0.17077176 0.        ]
[0.53238095 0.4714     0.49448276 0.07587302]
[0.17077176 0.49448276 0.31866825 0.        ]
[0.         0.07587302 0.         0.        ]]  ### Degree-corrected stochastic block model (DCSBM)¶

Just as we could add a degree-correction term to the ER model, so too can we modify the stochastic block model to allow for heterogeneous expected degrees. Again, we let $$\theta$$ be a length $$n$$ vector of degree correction parameters, and all other parameters remain as they were defined above for the SBM:

$P_{ij} = \theta_i \theta_j B_{\tau_i, \tau_j}$

Note that the matrix $$B$$ may no longer represent true probabilities, becuase the addition of the $$\theta$$ vectors introduces a multiplicative constant that can be absorbed into the elements of $$\theta$$

:

from graspy.models import DCSBMEstimator
dcsbme = DCSBMEstimator(directed=True,loops=False)
print("DCSBM \"B\" matrix:")
print(dcsbme.block_p_)
heatmap(dcsbme.p_mat_,
inner_hier_labels=labels,
font_scale=1.5,
title="DCSBM probability matrix",
vmin=0,
vmax=1,)
heatmap(dcsbme.sample(),
inner_hier_labels=labels,
title="DCSBM sample",
font_scale=1.5);

DCSBM "B" matrix:
[[   0. 1118.  104.    0.]
[1118. 4714. 1434.  478.]
[ 104. 1434.  268.    0.]
[   0.  478.    0.    0.]]  ### Random dot product graph (RDPG)¶

Under the random dot product graph model, each node is assumed to have a “latent position” in some $$d$$-dimensional Euclidian space. This vector dictates that node’s probability of connection to other nodes. For a given pair of nodes $$i$$ and $$j$$, the probability of connection is the dot product between their latent positions. If $$x_i$$ and $$x_j$$ are the latent positions of nodes $$i$$ and $$j$$, respectively:

$P_{ij} = \langle x_i, x_j \rangle$
:

from graspy.models import RDPGEstimator
rdpge = RDPGEstimator(loops=False)
heatmap(rdpge.p_mat_,
inner_hier_labels=labels,
vmin=0,
vmax=1,
font_scale=1.5,
title="RDPG probability matrix",
)
heatmap(rdpge.sample(),
inner_hier_labels=labels,
font_scale=1.5,
title="RDPG sample");  