# Expected number of distinct nodes visited in a directed bipartite graph

Let $G = (V,E)$ be a directed bipartite graph with $V = \{I \cup O\}$ where $\left\vert{I}\right\vert = n$ and $\left\vert{O}\right\vert = m$. All the edges start from a vertex in $I$ and end on a vertex in $O$. Let $d_{I_i}$ represent the outdegree of the $i^{th}$ vertex in $I$ and $d_{O_j}$ represent the indegree of the $j^{th}$ vertex in $O$.

Vertices in $I$ are allowed to be adjacent to the same vertices in $O$. We sample for $k$ vertices from the set $I$ uniformly at random with replacement. If a vertex from $I$ is selected in the sampled set then we mark all the nodes in $O$ adjacent to it. Initially all the nodes in $O$ are unmarked.

Thus, in $k$ queries what is the expected number of distinct nodes marked in $O$ by such a sampling mechanism.

I have an expression for the case where $d_{I_i}$'s are same i.e. $d_{I_i} = d_I$ and all $d_{O_j}$'s are same (regular graph). Expected number of distinct vertices marked in $O$ for the regular case is $m(1 - (1 - d_I/m)^k)$.

In the general case where degrees are not same, can I replace the $d_I$ by the average degree of the graph in the previous equation? Does it vary with the variance of the degree distribution? Any leads will be appreciated. Thank you.

Getting the expected number of distinct vertices seen in $O$ is not too much harder than the case that you have computed. Now that $$\# \text{ of vertices marked in }O = \sum_{v_j \in O} 1_{v_j \text{ is marked}}.$$ By linearity of expectation, you have that $$E[\# \text{ of vertices marked in }O] = \sum_{v_j \in O} P(v_j \text{ is marked}).$$ On the event that $v_j$ is marked, on at least one of the $k$ queries, one of its $d_{O_j}$ neighbors must have been chosen in $I$. So $$P(v_j \text{ is marked}) = \left( 1 - \left( 1 - \frac{d_{O_j}}{n} \right)^k \right),$$ and you get that $$E[\# \text{ of vertices marked in }O] = \sum_{v_j \in O} \left( 1 - \left( 1 - \frac{d_{O_j}}{n} \right)^k \right).$$ This simplifies to your formula in the case where $n=m$ and $d_{O_j}=d_{I_j}=d$ for all $j$.
EDIT: I missed the last part of the question. Now suppose the bipartite directed graph is chosen randomly (according to some probability distribution). Now, just as before $$P(v_j \text{ is marked}) = 1 - P(v_j \text{ is unmarked after }k) = 1 - P(v_j \text{ is unmarked after }1)^k.$$ Note that $v_j$ is unmarked if none of its neighbors is chosen. We can break up this probability depending upon the outcome of $v_j$'s in-degree. $$P(v_j \text{ is marked after }1) = \sum_{d=0}^{n} P(\text{in-deg}(v_j)=d) \left( \frac{n-d}{n}\right).$$ This uses an assumption that we chose the vertex from $I$ uniformly at random independently of the potential edges of the directed graph. We can rewrite the above as \begin{align*} P(v_j \text{ is unmarked after }1) &= \sum_{d=0}^{n} P(\text{in-deg}(v_j)=d) -\sum_{d=0}^{n} P(\text{in-deg}(v_j)=d) \left( \frac{d}{n}\right). \\ &= 1 - \frac{E[\text{in-deg}(v_j)]}{n}. \end{align*} Therefore $$E[\# \text{ of vertices marked in }O] = \sum_{v_j \in O} \left( 1 - \left( 1 - \frac{E[\text{in-deg}(v_j)]}{n} \right)^k \right).$$
• Thank you. You are right. But I am trying to take this one step further. I want to know if I can replace the $d_{O_j}$ in the expression with the mean or variance of the degree distribution. – Pratik Soni Nov 7 '14 at 16:54
• I like your approach but won't the probability of the node $v_j$ being marked after 1 and after 2 be different. In your answer, you have assumed them to be same and hence you have replaced $P(v_j \text{is marked after$k$})$ with $P(v_j \text{is unmarked after 1})^k$? – Pratik Soni Nov 10 '14 at 1:45
• Also, do you mean $P(v_j \text{is marked after} 1)$ instead of $P(v_j \text{is unmarked after} 1)$ in the second equation of the edit? – Pratik Soni Nov 10 '14 at 1:51
• @PratikSoni The assumption that that each time you choose a vertex of $I$, you do so uniformly at random independent of earlier choices. My event "$v_j$ is marked" means that $v_j$ is marked at the end, i.e. after $k$ queries. For your second question: yeah, it should be unmarked. – D Poole Nov 11 '14 at 3:59