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.


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.