Browse

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 graphtransitive directed graphfinite topologykNN그래프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
URI
http://hdl.handle.net/10371/170703

http://dcollection.snu.ac.kr/common/orgView/000000162183
Files in This Item:
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Master's Degree_수리과학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse