0
$\begingroup$

Given a random $d$-regular graph on $n$ nodes, what is the expected number of common neighbors between two nodes?

I don't know if it is as simple as just assuming that each neighbor of the first node has a $\frac{d}{n}$ probability of being a neighbor of the second, as the set of $d$-regular graphs on $n$ nodes is difficult to construct.

Improve this question
$\endgroup$
2
  • $\begingroup$ Not quite as simple if you are looking for the exact value. If $d=1$, you will certainly get a wrong answer this way and there is no reason to believe that other values of $d$ are any better. $\endgroup$
    – fedja
    Commented Sep 10, 2018 at 20:21
  • $\begingroup$ @fedja Well if $d=1$, then the expected value is 0. Some experimental results using networkx's random_regular_graph (which, if I'm reading the API right, seems to be good if $d<n^{\frac{1}{3}}$) gives E(n=1000, d=10) as approx .09. For E(n=1000, d=8) I got about .055. $\endgroup$
    – theresawalrus
    Commented Sep 10, 2018 at 21:13

1 Answer 1

Reset to default
2
$\begingroup$

Yep, it is $\frac{d(d-1)}{n-1}$ in general. Fix a $d$-regular graph and average over the action of the permutation group on the vertices. We are interested in the event $S(x,y,z)=$"$x$ is connected to $y$ and $z$". If $E$ is the expected number of neighbors, then $\sum_{x,y,z}P(S(x,y,z))=n(n-1)E$, summing over $x$ first. On the other hand, if we sum over $y,z$ first, the same sum is evaluated as $nd(d-1)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .