Graph diffusion using nearest neighbors

Share:

Description

For every node in a set of nodes the graph gets traversed along the node's shortest paths to its neighbors. Nearest neighbors are added until a maximum depth of k is reached. For settings where there are more than k neighbors having the same distance, all neighbors are returned.

Usage

1
nearest.neighbors(nodes, graph, k = 1L, ...)

Arguments

nodes

a n-dimensional integer vector of node indexes (1-based) for which the algorithm is applied iteratively

graph

an (n x n)-dimensional numeric non-negative adjacence matrix representing the graph

k

the depth of the nearest neighbor search, e.g. the depth of the graph traversal

...

additional parameters

Value

returns the kNN nodes as list of integer vectors of node indexes

Author(s)

Simon Dirmeier, simon.dirmeier@gmx.de

Examples

1
2
3
4
5
6
7
8
 # count of nodes
 n <- 10
 # indexes (integer) of nodes for which neighbors should be searched
 node.idxs <- c(1L, 5L)
 # the adjaceny matrix (does not need to be symmetric)
 graph <- rbind(cbind(0, diag(n-1)), 0)
 # compute the neighbors until depth 3
 neighs <- nearest.neighbors(node.idxs, graph, 3)