Distribution of a random vertex's neighbours' degrees

445 Views Asked by At

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.

1

There are 1 best solutions below

3
On BEST ANSWER

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