4

We choose a graph distribution $\mathcal D$. We draw a graph $g$ from $\mathcal D$. We choose a vertex $v$ uniformly at random. We look at its degree. What is the distribution of the degrees of the neihgbours of $v$ (conditioned on the degree of $v$)?

I will be happy to learn of any such result. I am especially interested in power law graphs, but I'm happy to learn of even trivial results.

tst
  • 1,415
  • 9
  • 18
  • There's absolutely nothing to say here for general $\mathcal D$, and the answer is really boring for the obvious choice of $\mathcal D = \mathcal G_{n,p}$, so can you please specify a graph distribution you want to ask about? – Misha Lavrov Apr 16 '18 at 21:37
  • @MishaLavrov I would like to find out the answer in power law graphs but I am interested even in boring results actually. I did change the question a bit though as you suggested. – tst Apr 16 '18 at 23:14

1 Answers1

3

One possible scale-free model, which is the sort of thing you're interested in, is the Barabási–Albert model where each new vertex is joined to $\beta$ previous vertices with probabilities proportional to their degrees. In this case, the degree distribution of neighbors of a node with given degree is known precisely.

The probability that the neighbor of a node with degree $k$ will have degree $\ell$ is $$ p(\ell\mid k) = \frac{\beta(k+2)}{k\ell(\ell+1)} - \frac{\beta}{k\ell}\binom{2\beta+2}{\beta+1} \frac{\binom{k+\ell-2\beta}{\ell-\beta}}{\binom{k+\ell+2}{\ell}} $$ as shown by Fotouhi and Rabbat in Degree correlation in scale-free graphs.

In a more typical random graph model, we don't expect a significant correlation. For example, in $\mathcal G_{n,p}$, degrees of adjacent vertices are independent except for the small term contributed by the edge between them. While the degree of an arbitrary vertex has the $\text{Binomial}(n-1,p)$ distribution, the degree of a neighbor of a vertex of any degree $k$ has the $1 + \text{Binomial}(n-2,p)$ distribution, regardless of $k$.

Misha Lavrov
  • 142,276