Introduction.
- I have a kNN graph, which is a directed graph where each node $i$ has out-degree $k^{out}_i$.
- The out-degree $k^{out}_i$ is equal for every node $i$, and it is equal to the number of $k-$nearest neighbours of node $i$, i.e. $k^{out}_i=k$.
- This means that from each node $i$ of the graph, k-edges are starting at node $i$ and ending at $k$ nearest neighbours.
- Just to show an example, the following picture illustrates a kNN graph with $5$ nodes and $k=2$ (therefore $k^{out}_i=2$).
- Just for a sake of completeness, I write the in-degrees and out-degrees of that exemplifying graph: $k^{out}_1=k^{out}_2=k^{out}_3=k^{out}_4=2$ and $k^{in}_1= 4$, $k^{in}_2= 3$, $k^{in}_3= 3$, $k^{in}_4= 0$, $k^{in}_5= 0$.
- The set ${kNN}_i$ indicates the $k-$nearest neighborhood of node $i$, i.e. the $k$ nearest neighbours of node $i$. In the exemplifying graph we have, $kNN_1=\{2,3\}$, $kNN_2=\{1,3\}$, $kNN_3=\{1,2\}$, $kNN_4=\{1,3\}$, $kNN_5=\{1,2\}$.
Question. I am not able to find a proper definition of in-degree and out-degree (except than by using the adjacency matrix - that I would like to avoid now). If I indicate two nodes with the indices $i$ and $j$, I would write $k^{out}_i$ as:
- $k^{out}_i = \left| \{ (i,j) : j \in {kNN}_i \} \right|$
(and probably it is not fully correct), but how to write $k^{in}_i$?
Maybe in this way?
- $k^{in}_i = \left| \{ (j,i) : i \in {kNN}_j \} \right|$
Note. $k^{out}_i$ in words: the out-degree of node $i$ is equal to the number (given by the two vertical bars $|\cdot|$) of $(i,j)$ edges, where $i$ is the starting node of the edge and $j$ is the end node of the edge, such that $j$ indicates the nearest neighbor nodes of the node $i$.