Expected number of neighbor nodes of a subset of nodes of a randomly constructed bipartite graph

154 Views Asked by At

Suppose a right-regular bipartite graph with $m$ left nodes and $n$ right nodes ($m>n$ and $B=m/n$ is an integer) is constructed as follows: First, each successive $B=m/n$ left nodes are connected to a distinct right node, respectively. After that, for each right node, randomly select another $H$ left nodes as neighbors from the rest of $(m-B)$ left nodes (i.e., from left nodes other than the $B$ already-connected left nodes of the right node).

The question is: Given a bipartite graph constructed as above, for a random $k<m$ subset of left nodes, is that possible to determine the expected number of neighboring right nodes of the left nodes in this size-$k$ subset? Thanks.