Publications
Detailed Information
최대 이분 매칭 기반의 가지치기를 활용한 부분 그래프 동형 알고리즘 성능 향상 : Improving Subgraph Isomorphism with Pruning by Maximum Bipartite Matching
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | 박근수 | - |
dc.contributor.author | 최윤영 | - |
dc.date.accessioned | 2021-11-30T02:42:52Z | - |
dc.date.available | 2021-11-30T02:42:52Z | - |
dc.date.issued | 2021-02 | - |
dc.identifier.other | 000000165829 | - |
dc.identifier.uri | https://hdl.handle.net/10371/175449 | - |
dc.identifier.uri | https://dcollection.snu.ac.kr/common/orgView/000000165829 | ko_KR |
dc.description | 학위논문 (석사) -- 서울대학교 대학원 : 공과대학 컴퓨터공학부, 2021. 2. 박근수. | - |
dc.description.abstract | 대형 그래프에 대한 분석은 최근 소셜 네트워크, 생물 정보학, 화학 등 다양한
분야에서 점차 중요해지고 있다. 그래프 분석에서 가장 핵심적인 문제 중 하나로 부분 그래프 동형 문제 (subgraph isomorphism) 가 있다. 부분 동형 그래프 문제를 backtracking 활용하여 해결하는 많은 알고리즘이 제시되어왔다. 하지만 최악의 경우 지수적인 시간 복잡도를 가지는 backtracking 특성상 여전히 특정 입력에서는 답을 찾기 위해서 지나치게 긴 시간을 소모하기 때문에 여전히 실제 문제에 적용이 어려운 경우가 존재한다. 본 논문에서는 backtracking 과정에서 알고리즘 동작 시간을 길게 만들 수 있 는 요인을 탐구하고, 이를 해결함으로써 실행 시간을 획기적으로 줄일 수 있는 새로운 기법을 소개한다. 또한, 기존 알고리즘 중 state-of-the-art 인 DAF[4] 에 기법을 적용한 경우와 그렇지 않은 경우를 구현하고 실제 그래프 데이터 상에서 실험을 진행하여 제시한 기법이 문제를 효과적으로 해결하는데 도움이 될 수 있는 방법임을 입증했다. | - |
dc.description.abstract | In recent years, graphs have been playing an increasingly important role in
various domains, e.g., social networks [3], bioinformatics [8], chemistry [10] etc. One of the most fundamental problems in graph analysis is subgraph isomor- phism. Many practical solutions have been suggested for subgraph isomorphism. However, those algorithms show limited response time and scalability in han- dling real-world applications because, by the nature of backtracking, there could be many redundant computations. In this paper, we develop a new technique to prune out some parts of the search space. Furthermore, we incorporate our method to one of them and show the efficacy by conducting experiments on several real-world datasets. | - |
dc.description.tableofcontents | Chapter 1 서론 1
Chapter 2 배경지식 3 Chapter 3 DAF 알고리즘 8 Chapter 4 최대 이분 매칭에 활용한 가지치기 16 Chapter 5 성능 평가 26 | - |
dc.format.extent | iv, 43 | - |
dc.language.iso | kor | - |
dc.publisher | 서울대학교 대학원 | - |
dc.subject | 부분 그래프 동형 | - |
dc.subject | Subgraph isomorphism | - |
dc.subject.ddc | 621.39 | - |
dc.title | 최대 이분 매칭 기반의 가지치기를 활용한 부분 그래프 동형 알고리즘 성능 향상 | - |
dc.title.alternative | Improving Subgraph Isomorphism with Pruning by Maximum Bipartite Matching | - |
dc.type | Thesis | - |
dc.type | Dissertation | - |
dc.contributor.AlternativeAuthor | Yunyoung Choi | - |
dc.contributor.department | 공과대학 컴퓨터공학부 | - |
dc.description.degree | Master | - |
dc.date.awarded | 2021-02 | - |
dc.identifier.uci | I804:11032-000000165829 | - |
dc.identifier.holdings | 000000000044▲000000000050▲000000165829▲ | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.