utils.epsilon_graph(X, epsilon=None, percentile=0.05)

Construct an epsilon-neighborhood graph, represented by an adjacency list. Two vertices are connected by an edge if they are within ‘epsilon’ distance of each other, according to the Euclidean metric. The implementation is a brute-force computation of all O(n^2) pairwise distances of the rows in X.


X : 2D numpy array

The rows of ‘X’ are the observations which become graph vertices.

epsilon : float, optional

The distance threshold for neighbors.

percentile : float, optional

If ‘epsilon’ is unspecified, this determines the distance threshold. ‘epsilon’ is set to the desired percentile of all (n choose 2) pairwise distances, where n is the number of rows in ‘X’.


neighbors : numpy array

Each row contains the nearest neighbors of the corresponding row in ‘X’, indicated by row indices.

See also



>>> X = numpy.random.rand(100, 2)
>>> neighbors = debacl.utils.epsilon_graph(X, epsilon=0.2)