# Probability of staying in a sub graph

Assume that I have an undirected graph $G$ with $n_1+n_2$ vertices and $e_1+e_2+e_3$ many edges, and a subgraph $G^{\prime}$ of $G$.

Assume further, I now that $G^{\prime}$ has $n_1$ vertices and $e_1$ many edges where both endpoints lie in G' and $e_2$ many where only one is in $G^{\prime}$.

If I pick a vertex from $G^{\prime}$ uniformly at random, what is the expected number of neighbors that are from $G^{\prime}$?

I worked out that the average degree of a vertex from $G^{\prime}$ is $\frac{2e_1+e_2}{n_1}$ but I have problems calculating the fractions of neighbors inside and outside of $G^{\prime}$.

It's just $2e_1/n_1$ for inside neighbors and $e_2/n_1$ for outside neighbors. If you need average fractions/ratios of outside to inside neighbors, this is not easy and I suspect depends on the geometry of the graph, as $\frac{mean(X)}{mean(Y)} \ne mean(\frac{X}{Y})$
(dark circles are $G'$) the total degrees are equal, but the probabilities to stay in $G'$ are not.
• You have to sum over all vertices, $P(\mbox{ stay in }G') = \left(\sum_{i \in G'} s_i/t_i\right) / |G'|$ where $s_i$ is number of inside neighbors of vertex $i$ and $t_i$ number of total neighbors. – PA6OTA Jun 5 '14 at 17:35