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.



The expected value of common neighbors on a random regular graph
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)$. 


