Publications
Detailed Information
최대 이분 매칭 기반의 가지치기를 활용한 부분 그래프 동형 알고리즘 성능 향상 : Improving Subgraph Isomorphism with Pruning by Maximum Bipartite Matching
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Advisor
- 박근수
- Issue Date
- 2021-02
- Publisher
- 서울대학교 대학원
- Keywords
- 부분 그래프 동형 ; Subgraph isomorphism
- Description
- 학위논문 (석사) -- 서울대학교 대학원 : 공과대학 컴퓨터공학부, 2021. 2. 박근수.
- Abstract
- 대형 그래프에 대한 분석은 최근 소셜 네트워크, 생물 정보학, 화학 등 다양한
분야에서 점차 중요해지고 있다. 그래프 분석에서 가장 핵심적인 문제 중 하나로
부분 그래프 동형 문제 (subgraph isomorphism) 가 있다.
부분 동형 그래프 문제를 backtracking 활용하여 해결하는 많은 알고리즘이
제시되어왔다. 하지만 최악의 경우 지수적인 시간 복잡도를 가지는 backtracking
특성상 여전히 특정 입력에서는 답을 찾기 위해서 지나치게 긴 시간을 소모하기
때문에 여전히 실제 문제에 적용이 어려운 경우가 존재한다.
본 논문에서는 backtracking 과정에서 알고리즘 동작 시간을 길게 만들 수 있
는 요인을 탐구하고, 이를 해결함으로써 실행 시간을 획기적으로 줄일 수 있는
새로운 기법을 소개한다. 또한, 기존 알고리즘 중 state-of-the-art 인 DAF[4] 에
기법을 적용한 경우와 그렇지 않은 경우를 구현하고 실제 그래프 데이터 상에서
실험을 진행하여 제시한 기법이 문제를 효과적으로 해결하는데 도움이 될 수 있는
방법임을 입증했다.
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.
- Language
- kor
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.