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})$

For example, here enter image description here

(dark circles are $G'$) the total degrees are equal, but the probabilities to stay in $G'$ are not.

  • $\begingroup$ Thank you, this is what I wanted, but how do I get those values, somehow I have trouble arriving at those numbers. $\endgroup$ – xdertz Jun 5 '14 at 17:32
  • $\begingroup$ 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. $\endgroup$ – PA6OTA Jun 5 '14 at 17:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.