Probability of staying in a sub graph

30 Views Asked by At

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

1

There are 1 best solutions below

2
On

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.