n-degree neighborhood of a node v

943 Views Asked by At

I am confused about the definition of the n-degree neighborhood of a node v in a graph. The definition says: "The $n$-degree neighborhood of a node $v_i$ is the set of nodes exactly $n$ hops away from $v_i$".

Suppose I have the following graph and I want to find the $n=1$ neighborhood of node $v_1$. That would be $v_2$ and $v_3$. Next suppose I want to find the $n=2$ neighborhood of node $v_1$, now my question: do we retrieve all nodes recursively from $v_1$? i.e. is the answer is $v_2$, $v_3$, $v_4$ or JUST $v_4$?

enter image description here

1

There are 1 best solutions below

1
On

If this is where the definition is from:

In link prediction, graph distance plays a primary role in determining the imbalance ratio. We define the $n$-degree neighborhood of a node $v_i$ as the set of nodes exactly $n$ hops away from $v_i$. --- Lichtenwalter et al., New Perspectives and Methods in Link Prediction (pdf).

Then from the context, the "the $n$-degree neighborhood" would most likely mean the set of vertices at distance $n$, The use of "degree" here will be in the same sense as in six degrees of separation.

If this is correct, $v_1$ has just $v_4$ as the $2$-degree neighbor.