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.