probability distribution of communities in Stochastic Block Model

Question

Consider a simple case of Stochastic Block Model: all nodes in the graph are equally divided into two communities, the probability of edge connection for nodes in the same community is $p$, nodes in different communities $q$. Given a node $v$, consider the random variable $\Delta(v)$: the difference of numbers of neighbors in the two communities. I am wondering how to calculate the probability distribution of $\Delta(v)$.

Answer 1

Let $C_1$ and $C_2$ denote those communities. Also let $N_j(v):=\{w\in C_j:w\leftrightarrow v\}$. Assume that $v\in C_1$. Then for $0\le x< |C_1|$ and $0\le y\le |C_2|$, $$ \mathsf{P}(N_1(v)=x)=\binom{|C_1|-1}{x}p^x(1-p)^{|C_1|-x-1} $$ and $$ \mathsf{P}(N_2(v)=y)=\binom{|C_2|}{y}q^y(1-q)^{|C_2|-y}. $$ Consequently, the distribution of $\Delta(v):=N_1(v)-N_2(v)$ is determined by $$ \mathsf{P}(\Delta(v)=z)=\sum_{y}\mathsf{P}(N_1(v)=z+y)\mathsf{P}(N_2(v)=y). $$