We connect all nodes in the graph that are at most  $\epsilon$  'distance' away from each other

University of Michigan - Ann Arbor

The first thing we need to do for the algorithm is build a similarity graph from the similarity matrix. There are three types of similarity graphs that can be generated :
1. $\epsilon$ -neighbourhood graph
2. K nearest neighbours graph
3. Fully connected graph

Building Similarity Graph

$\epsilon$ neighbourhood graph

We connect nodes to their k nearest neighbours. However there are times when this relation is NOT symmetric i.e. A's kth nearest neighbour is B, but A is B's k+1th nearest neighbour. This causes the graph to be directed which is a problem. 
This can be dealt with in two ways described in the child nodes.

K nearest neighbours graph

We connect all nodes that have a non zero similarity value ($s_{i,j}$) in the similarity matrix and weigh their edges by the value of $s_{i,j}$ .

Learn Before

Related