Publications
Detailed Information
A method getting the transitive kNN graph of a kNN graph preserving topology
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Advisor
- 강명주
- Issue Date
- 2020
- Publisher
- 서울대학교 대학원
- Keywords
- kNN graph ; transitive directed graph ; finite topology ; kNN그래프 ; transitive 유향그래프 ; 유한위상
- Description
- 학위논문 (석사) -- 서울대학교 대학원 : 자연과학대학 수리과학부, 2020. 8. 강명주.
- 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그래프를 구하는 계산 알고리즘을 제안한다.
- Language
- eng
- Files in This Item:
- Appears in Collections:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.