from statistics.

communities

Tuning the weight noticeably improved our clustering. Below, you can see the difference between our embedding prior to tuning and our embedding after tuning.

𝑋𝑋𝑇𝑖,𝑗XXi,jTXX^T_{i, j}

title="Visualization of the covariates", xticks=[], ylabel="Rows

data that matches the data near perfectly

the information we did not get to observe

vertices

That is, the statistical network model indicates what, exactly, is random, and how we can characterize its behavior statistically.

graphs

we can still summarize that more complex model using a 𝑝pp term without much work

positive aspects to the ER network’s simplicity

If we do not know any patterns defining how people are or are not friends

For instance, in our social network example, we might only know whether two people are from the same school, and might not know whether they are in the same grade or share classes together, even though we would expect these facts to impact whether they might have a higher chance of being friends.

ss you are looking at a graph in which the vertices are already arranged in an order which respects the community struucture.

ipython-input-11-8581568507e8>:8: FutureWarning: Using a non-tuple sequence for multidimensional indexing is deprecated; use `arr[tuple(seq)]` instead of `arr[seq]`. In the future this will be interpreted as an array index, `arr[np.array(seq)]`, which will result either in an error or a different result. heatmap(A[[vtx_perm]] [:,vtx_perm])

The graph has an identical block structuure (up to the reordering of the vertices) as the preceding graph illustrated.

ll. Consider, for instance, a s

The below graph shows the exact same set of adjacencies as-above, but wherein 𝐴𝐴AA\pmb A has had its vertices resorted randomly.

Consider, for instance, a similar adjacency matrix to the graph plotted above, with the exact same realization, up to a permutation (reordering) of the vertice

Indeed, the block structure may only be apparent given a particular ordering of the vertices,

may

a block structure is visually discernable.

The block structure is clearly delineated by the first 505050 vertices being from a single community, and the second 505050 vertices being from a different community.

These blocks are the apparent “subgraphs”, or square patterns, observed in the above graph.

n the above simulation, we can clearly see an apparent 444-“block structure”, which describes the fact that the probability of an edge existing depends upon which of the 444 “blocks” the edge falls into

In the above simulation,

# for simplicity, the simulation code generates samples wherein # vertices from the same community are ordered in the vertex set by # their community order.

the adjacency matrices describing a graph which has the 𝑆𝐵𝑀𝑛(𝜏⃗ ,𝐵𝐵)SBMn(τ→,BB)SBM_n(\vec \tau, \pmb B) distribution.

graph which has the 𝑆𝐵𝑀𝑛(𝜏⃗ ,𝐵𝐵)SBMn(τ→,BB)SBM_n(\vec \tau, \pmb B) distribution.

o the symmetry of 𝐵𝐵BB\pmb B, 𝐴𝑗𝑖|𝑣𝑖=𝑘,𝑣𝑗=𝑙∼𝐵𝑒𝑟𝑛𝑜𝑢𝑙𝑙𝑖(𝑏𝑘𝑙)Aji|vi=k,vj=l∼Bernoulli(bkl)A_{ji} | v_i = k, v_j = l \sim Bernoulli(b_{kl}), for all 𝑖,𝑗∈1,...,𝑛i,j∈1,...,ni,j \in 1,...,n.

if vertex 𝑣𝑖viv_i is in community 𝑘kk and vetex 𝑣𝑗vjv_j is in community 𝑙ll, then an edge 𝑒𝑖𝑗eije_{ij} or 𝑒𝑗𝑖ejie_{ji} exists between 𝑣𝑖viv_i and 𝑣𝑗vjv_j with probability 𝑏𝑘𝑙=𝑏𝑙𝑘bkl=blkb_{kl}=b_{lk}. Fomally, we wite that 𝐴𝐴∼𝑆𝐵𝑀𝑛(𝜏⃗ ,𝐵𝐵)AA∼SBMn(τ→,BB)\pmb A \sim SBM_n(\vec \tau, \pmb B) if 𝐴𝑖𝑗|𝑣𝑖=𝑘,𝑣𝑗=𝑙∼𝐵𝑒𝑟𝑛𝑜𝑢𝑙𝑙𝑖(𝑏𝑘𝑙)Aij|vi=k,vj=l∼Bernoulli(bkl)A_{ij} | v_i = k, v_j = l \sim Bernoulli(b_{kl}),

ntuitionally, this would correspond to the graph in which each of the The m

Further, the matrix 𝐵𝐵BB\pmb B is supposed to be symmetric; that is, for any 𝑏𝑘𝑙bklb_{kl}, it is always the case that 𝑏𝑘,𝑙=𝑏𝑙𝑘bk,l=blkb_{k,l} = b_{lk} for all 𝑘=1,...,𝐾k=1,...,Kk = 1,..., K.

𝑘=1,...,𝐾k=1,...,Kk = 1,..., K tend to exceed off-diagonal entries 𝑏𝑘𝑙bklb_{kl} where 𝑘≠𝑙k≠lk \neq l and 𝑘,𝑙=1,...,𝐾k,l=1,...,Kk,l = 1,...,K

𝐵𝐵BB\pmb B such that the diagonal entries 𝑏𝑘𝑘

𝐵𝐵BB\pmb B with entries 𝑏𝑘𝑙bklb_{kl} for 𝑘,𝑙=1,...,𝐾k,l=1,...,Kk, l = 1,..., K defines the probability of an edge existing between vertices which are in community 𝑘kk

For instance, in a social network in which the vertices are students and the edges define whether two students are friends, a vertex assignment vector might denote the school in which each student learns.

ex assignment vector has entries 𝜏⃗ 𝑖τ→i\vec \tau_i, where 𝑖=1,...,𝑛i=1,...,ni = 1, ..., n, for each of the vertices in the graph. For a given vertex 𝑣𝑖∈vi∈Vv_i \in \mathcal V, the corresponding vertex assignment 𝜏⃗ 𝑖τ→i\vec \tau_i defines which of the 𝐾KK communities in which 𝑣𝑖viv_i is a member.

n this case, rather than having a single edge existence probability, each pair of communities has its own unique edge existence probabili

𝐺=(,)G=(V,E)G = (\mathcal V, \mathcal E) is an SBM with 𝑛nn vertices, each vertex 𝑣𝑖viv_i can take be a member of one (and only one) of 𝐾KK possible communities.

The Stochastic Block Model, or SBM, is a random graph model which produces graphs in which edge existence probabilities depend upon which vertices a given edge is adjacent to

l

Which is in close agreement to the true probability, 𝑝=0.3p=0.3p = 0.3

Given a graph with an adjacency matrix 𝐴𝐴(𝑠)AA(s)\pmb A^{(s)}, we can also use graspologic to estimate the probability parameter of the 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) model:

uare is dark red if an edge is present, and white if no edge is pr

n the simple simulation above, we sample a single, undirected, network with loops, with adjacency matrix 𝐴𝐴(𝑠)AA(s)\pmb A^{(s)}.

0 vertices ps = 0.3 # probability of an edge existing is .3 # sample a single adj. mtx from ER(50, .3) As = er_np(n=n, p=ps, directed=True, loops=True) # and plot it heatmap(As, title="ER(50, 0.3) Simulation")

single adj. mtx from ER(50, .3)

The following python code can be used to generate and visualize a graph which is generated by the 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) model. Here, we let 𝑛=50n=50n=50 vertices, and the probability of an edge 𝑝=.3p=.3p=.3:

E[deg(vi)]=E[∑j≠iAij]=∑j≠iE[Aij]Expectation of a finite sum is the sum of the expectations=(n−1)p\begin{align*} \mathbb E[deg(v_i)] &= \mathbb E\left[\sum_{j \neq i} A_{ij}\right] \\ &= \sum_{j \neq i} \mathbb E[A_{ij}]\;\;\;\;\textrm{Expectation of a finite sum is the sum of the expectations} \\ &= (n-1) p \end{align*} Which follows by using the fact that all of the 𝑛−1n−1n-1 possible edges which are incident vertex 𝑣𝑖viv_i have the same expected probability of occurence, 𝑝pp, governed by the parameter for the 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) model. This tractability of theoretical results makes the 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) an ideal candidate graph to study in describing properties of networks to be expected if the network is 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p). Similarly, we can easily invert the properties of 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) networks, to study when a graph is not an 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) random graph, and may merit more careful inferential tasks. On another front, when one wishes to devise new computational techniques and deduce the efficiency or effectiveness of a technique on a network with a given number of nodes and a given number of edges, and is not concerned with how efficient the technique is if the network displays other (potentially exploitable) properties, the 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) model also makes a good candidate for analysis. This is particularly common when dealing with graphs which are known to be sparse; that is, 𝑝pp is very small (usually, on the order or less than 1/𝑛1/n1/n).

This is particularly common when dealing with graphs which are known to be sparse; that is, 𝑝pp is very small (usually, on the order or less than 1/𝑛1/n1/n).

given number of nodes and a given number of edges, and is not concerned with how efficient the technique is if the network displays other (potentially exploitable) properties, the 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) model also makes a good candidate for analysis

deduce the efficiency or effectiveness of a technique on a networ

larly, we can easily invert the properties of 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) networks, to study when a graph is not an 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) random graph, and may merit more careful inferential tasks. On

This tractability of theoretical results makes the 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p) an ideal candidate graph to study in describing properties of networks to be expected if the network is 𝐸𝑅𝑛(𝑝)ERn(p)ER_n(p).

incident vertex 𝑣𝑖viv_i

𝐸𝑅𝑛(𝑝)

𝔼[𝑑𝑒𝑔(𝑣𝑖)]=𝔼[∑𝑗≠𝑖𝐴𝑖𝑗]=∑𝑗≠𝑖𝔼[𝐴𝑖𝑗]

a trivial exercise:

𝑑𝑒𝑔(𝑣𝑖)=∑𝑗≠𝑖𝐴𝑖𝑗deg(vi)=∑j≠iAijdeg(v_i) = \sum_{j \neq i}A_{ij}

“identical” clarifies that the edge probability 𝑝pp (or the probability of no edge, 1−𝑝1−p1-p) is the same for all edges within the network.

the occurence or not occurence of other edges in the network does not impact the probability of occurence of a given edge

(including which vertices an edge is incident, other edges within the graph, nor other factors)

vertices

we may lack obvious things such as knowing

generative model we select for our network will not be the true generative model that underlies our network

The vertex assignment vector has entries $\vec \tau_i$, where $i = 1, …, n$, for each of the vertices in the graph. For a given vertex $v_i \in \mathcal V$, the corresponding vertex assignment $\vec \tau_i$ defines which of the $K$ communities in which $v_i$ is a member. For instance, in a social network in which the vertices are students and the edges define whether two students are friends, a vertex assignment vector might denote the school in which each student learns. The matrix $\pmb B$ with entries $b_{kl}$ for $k, l = 1,…, K$ defines the probability of an edge existing between vertices which are in community $k$ with vertices which are in community $l$. For instance, in the social network example, one might select $\pmb B$ such that the diagonal entries $b_{kk}$ for $k = 1,…, K$ tend to exceed off-diagonal entries $b_{kl}$ where $k \neq l$ and $k,l = 1,…,K$. Further, the matrix $\pmb B$ is supposed to be symmetric; that is, for any $b_{kl}$, it is always the case that $b_{k,l} = b_{lk}$ for all $k = 1,…, K$. Intuitionally, this would correspond to the graph in which each of the The matrix $\pmb B$ defines that if vertex $v_i$ is in community $k$ and vetex $v_j$ is in community $l$, then an edge $e_{ij}$ or $e_{ji}$ exists between $v_i$ and $v_j$ with probability $b_{kl}=b_{lk}$. Fomally, we wite that $\pmb A \sim SBM_n(\vec \tau, \pmb B)$ if $A_{ij} | v_i = k, v_j = l \sim Bernoulli(b_{kl})$, or equivalently due to the symmetry of $\pmb B$, $A_{ji} | v_i = k, v_j = l \sim Bernoulli(b_{kl})$, for all $i,j \in 1,…,n$.

We need a graph and some covariates. To start off, we’ll make a pretty straightforward Stochastic Block Model with 1500 nodes and 3 communities.