sgtl.graph.knn_graph#

sgtl.graph.knn_graph(data, k: int)#

Construct the k-nearest neighbours graph from the given data.

The data paramenter must have two dimensions. If data has dimension (n, d), then the resulting graph will have n vertices. Each vertex will be connected to the k vertices which are closest to it in the dataset. Notice that this does not necessarily result in a k-regular graph since neighbours may or may not be mutually within the k nearest.

The data should be either a dense numpy array or a sparse scipy matrix.

The graph will have at most n * k edges.

The running time of this construction is \(O\left(d \log(n) + n k\right)\) where

  • d is the dimensionality of each data point

  • n is the number of data points

  • k is the parameter k in the knn graph

This is likely to be dominated by the \(O(n k)\) term.

Parameters:

  • data – the data to construct the graph from

  • k – how many neighbours to connect to

Returns:

An sgtl.Graph object representing the k-nearest neighbour graph of the input.