A method getting the transitive kNN graph of a kNN graph preserving topology

Abstract

In this paper, we recall some previous research of a bijection between transitive directed graphs and topologies on a finite set. In data science area, k Nearest Neighbor(kNN) graph is a widely used graph. It can be interpreted by a directed graph in the sense of in and out degrees. kNN graph is not transitive in general. Adding or eliminating edges, there are various methods to get a transitive directed graph from a given kNN graph. In this paper, we prove that there is a unique way which make a transitive directed graph preserving topology. Moreover, we suggest a simple method to make the transitive directed graph without computing the topology of a given kNN graph.

이 학위 논문에서는 유한집합 위에서의 위상들과 transitive 유향그래프의 일대일대응에 관련된 내용들을 상기한다. kNN 그래프는 데이터를 활용한 과학 분야에서 널리 사용된다. 우리는 kNN그래프의 in-degree와 out-degree를 기준으로 kNN그래프를 유향그래프로 해석할 수 있다. 하지만 일반적으로 kNN그래프는 transitive 유향그래프가 아니고 주어진 kNN그래프의 간선을 추가하거나 빼는 등 다양한 방법으로 transitive 유향그래프를 만들 수 있다. 이 학위 논문을 통해서 우리는 위상을 보존하는 transitive 유향그래프를 얻는 방법이 유일함을 증명하고 구체적인 방법을 제시한다. 더 나아가서 위상의 계산 없이 transitive kNN그래프를 구하는 계산 알고리즘을 제안한다.