0
$\begingroup$

Let $G(U,V,E)$ be a simple, undirected, bipartite graph and $U=\{u_1,u_2,{\cdots},u_n\}$ and $V=\{ v_{1},v_{2},\cdots,v_{n}\}$. Let $d_k^l$ be the number of vertex with degree $k$ in $l$, where $l \in L=\{U,V\}$ and $k \in X=\{1,2,\cdots,n\}$. Note that $ M = |E|= \frac{1}{2}\sum_{i \in X }\sum_{j \in L}d_i^j$ is the total number of edges of $G$.

Now, randomly select $m$ edges from $E$ without replacement and call a vertex "covered" if it is one of the ends of the randomly selected edges. Then, induce a graph with the covered vertex subset ($S$), i.e, a graph $G_{S}$ with vertex set $S$ and all the edges connecting pairs of vertices in that subset in $G$.

The question: is there any way to derive the expected value of the number of edges of $G_{S}$ ($E{[E_{s}]}$) based on the probability of edge selection $p_{e} = \frac{m}{M}$ and the degree distribution of $G$?

For the case of the uniform degree distribution, the results in 1 or 2 can be applied, but I would like to see if there is a way to calculate it for an arbitrary degree distribution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.