Click here for the source material of these notes.
The standard Stochastic Blockmodel (SBM) says that each node is partitioned into one of \(K\) blocks. We represent this partition with the function \(z: \{1, \dots, N\} \rightarrow \{1, \dots, K\}\) and the partition matrix \(Z \in \{0,1\}^{N\times K}\), where each row has exactly one 1. Conditioned on \(z\), \[E(A|z) = ZBZ^T.\] See previous notes for more details.
The key “sociological construct” which motivates the SBM is the idea of stochastic equivalence.
Definition: Two nodes \(i,j\) in an undirected network are stochastically equivalence if for all other nodes \(\ell\) \[P((i,\ell) \in E) = P((j,\ell) \in E)\] where \(E\) is the edge set.
This forms “equivalence classes” of nodes. Each equivalence class is then a block in the SBM.
This definition can also be applied to directed networks.
Definition: Two nodes \(i,j\) in a directed network are stochastically equivalence if \[P((i,\ell) \in E) = P((j,\ell) \in E)\] for all other nodes \(\ell\) and \[P((\ell,i) \in E) = P((\ell,j) \in E)\] for all other nodes \(\ell\).
These notes show that it in directed networks, is not necessary to have a single notion of stochastic equivalence. In fact, there are two forms “stochastically equivalent senders” and “stochastically equivalent receivers”.
I typically prefer to presume that nodes have already been assigned to blocks by some exogenous process. Then, edges are (conditionally) independent given that process. If you prefer to specify that process, that is fine. If you do that, you can make the graph exchangeable (which is nice, but not something that we have talked about).
Definition: A graph is sampled from the Stochastic Co-Blockmodel (ScBM) if there exists partition matrices \[Y \in \{0,1\}^{N \times K_s} \mbox{ and } Z \in \{0,1\}^{N \times K_r}\] and block proability matrix \(B\in [0,1]^{K_s \times K_r}\) such that the adjacency matrix satisfies \[E(A) = YBZ^T.\]
Fact: If the \(i\) and \(j\) rows of \(Y\) are equal, then nodes \(i\) and \(j\) are stochastically equivalent senders, \[P((i,\ell) \in E) = P((j,\ell) \in E),\] for all other nodes \(\ell\). Alternatively, if the \(i\) and \(j\) rows of \(Z\) are equal, then nodes \(i\) and \(j\) are stochastically equivalent receivers, \[P((\ell,i) \in E) = P((\ell,j) \in E)\] for all other nodes \(\ell\).
\([AA^T]_{ij}\) contains “the number of common offspring” for nodes \(i\) and \(j\). These statistics (i.e. over the values \(i\) and \(j\)) contain information about the sending stochastic equivalence. \([A^TA]_{ij}\) contains “the number of common parents” for nodes \(i\) and \(j\). These statistics (i.e. over the values \(i\) and \(j\)) contain information about the receiving stochastic equivalence. To see this, note that under the ScBM, \[E(A)E(A)^T = Y M Y^T,\] for \(M = Z^TBZ\) and \[E(A)^TE(A) = Z M Z^T,\] for \(M = Y^TBY\). Think of each of these matrices as SBM’s. So, by running spectral clustering on \(AA^T\) and \(A^TA\), we should be able to estimate \(Y\) and \(Z\).
Fun fact: Recall that you compute the singular vectors of \(A\) by computing the eigenvectors of \(AA^T\) and \(A^TA\). This highlights the duality between the sending and receiveing clusters.
Note: A more straight forward way to model the asymmetry is to simply use the standard SBM, but allow for \(B\) to be asymmetric. One way estimate this partition with spectral clustering is to run spectral clustering on \(A + A^T\). Here, \(E(A + A^T) = ZB^{(2)}Z^T\), where \(B^{(2)} = B + B^T\), is symmetric and it retains the block structure that is necessary for spectral clustering to perform well.