Average Nearest Neighbors' Degree

up:: 041 MOC Graph Theory

Example from 0_CS7280_NetworkScience, for $v$‘s average nearest neighbors degree, which is $4$: note it takes into account paths from $v$ to itself as well!!!

Given a node $i$ from a graph with Adjacency Matrix $A$, its average nearest neighbor degree is

$$\begin{array}{rl}{k}_i^{nn}& =\frac{1}{k_i}\sum _{j=1}^N{A}_{ij}{k}_j\\ & =\frac{{\sum }_{j,k}{A}_{ij}{A}_{jk}}{{\sum }_j{A}_{ij}}\end{array}$$

That is, it is the weighted average degree from $i$‘s neighbors (weighted by $i$‘s row of the adjacency matrix). Do not forget that these degrees also take $i$ into account! In fact, A simple graph’s node is a (local) star graph center iff its average nearest neighbors degree equals 1!

$k_{nn}$ in terms of powers of the adjacency matrix

One can also see this measure as referring to the second power of the adjacency matrix, i.e. to $2$-paths coming out of $i$:

$$k_i^{nn}=\frac{{\sum }_j(A^2{)}_{ij}}{{\sum }_j{A}_{ij}}$$

---

References

• BOCCALETTI, S. et al. Complex networks: Structure and dynamics. Physics reports, v. 424, n. 4–5, p. 175–308, 2006.