- I’ve found out several clustering algorithms such as chameleon or even Spectral Clustering. its work to converting data to a weighted. KNN graph based on the distance between points. I'd like to know how those graphs are generated. Could you please show me those graphs directed? If a point A has another point B as a near neighbor but point B doesn’t have point A as a near neighbor, is an edge still drawn? How are the weights computed?
.
https://en.wikipedia.org/wiki/Nearest_neighbor_graph
as for the weighting of the edges, it is sometimes derived from a rescaled version of the inverse distance (the higher the weight, the closer the neighbour and weights between 0 and 1)
.
Dear Ali Al-Fatemi,
Look the link, maybe useful.
https://arxiv.org/pdf/1705.01813.pdf
Regards,
Shafagat
The graph is generated based on the problem that is modeled, graph is a powerfull tool. Normally associated with contiguity or relationships. Also from the similarity matrix between all pairs of objects, where the weights of the edges would be the similarity. These approaches make the undirected graph. If the distances between the objects are used as weights, it is possible to obtain a weighted and directed graph. Weights can be calculated based on similarity, distance or any other criteria between pairs of objects.
To make it short:
Step1: compute for every node the k-nearest neighbors. Denote with A the adjacency matrix having A_{ji}=1 if node i is among the k-nearest neighbors of node j. A is not symmetric, because (as you mentioned) if node i is among the k-nearest neighbors of node j, then this does not imply that node j is among the k-nearest neighbors of node i.
Step2: Spectral clustering is designed for undirected graphs, which have a symmetric (weighted) adjacency matrix. Thus, the matrix A is converted to a symmetric (weighted) adjacency matrix
W=1/2(A+A^T).
The weight of the edge from node j to node i is given as W_ji=(A_ji + A_ij)/2.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs