Esta clase de grafo se crea a partir de un conjunto de datos que contiene entidades y sus respectivas distancias. Dado un parámetro k, el objetivo es obtener un grafo que vincule cada nodo con sus k vecinos más próximos:
| Nodo 1 | Nodo 2 | Distancia | Fecha |
|---|---|---|---|
| 53123 | 63152 | 10 | 12/03/2007 |
| 68129 | 15487 | 12 | 13/03/2007 |
| 43261 | 32536 | 6 | 14/03/2007 |
| 12993 | 22866 | 2 | 15/03/2007 |
| 60765 | 63152 | 75 | 16/03/2007 |
| 18934 | 48765 | 23 | 17/03/2007 |
Se puede utilizar la misma condición de filtro que para la opción Solo enlaces, más el parámetro k.
Tenga en cuenta que esta clase de grafo siempre es dirigido. Esto se puede comprender fácilmente con el siguiente ejemplo, en el que el grafo se crea y cada nodo está conectado a un único vecino más próximo:

A es el vecino más próximo de B, y también de C. En un grafo no dirigido, A estaría vinculado a dos vecinos diferentes. Es decir, A tendría dos vecinos más próximos, lo cual es una contradicción. Esto de debe al hecho de que "es un vecino más próximo" no es una relación simétrica.