지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers Journal of KIISE Journal of KIISE Vol.48 No.9
- 발행연도
- 2021.9
- 수록면
- 973 - 980 (8page)
- DOI
- 10.5626/JOK.2021.48.9.973
이용수
초록· 키워드
오류제보하기
대형 그래프에 대한 분석은 최근 다양한 분야에서 점차 중요해지고 있다. 그래프 분석에서 가장 핵심적인 문제 중 하나로 부분 그래프 동형(subgraph isomorphism) 문제가 있다. 부분 그래프 동형 문제란 데이터 그래프와 쿼리 그래프가 주어졌을 때, 데이터 그래프에서 쿼리 그래프의 임베딩이 존재하는지 확인하는 문제이다. 부분 그래프 동형 문제를 해결하는 많은 알고리즘이 제시되어왔지만 여전히 특정 입력에서는 답을 찾기 위해 알고리즘이 동작하는 시간이 긴 경우가 있어서 실제 문제에 적용이 어려운 경우가 있다. 본 논문에서는 실행 시간을 획기적으로 줄일 수 있는 이분 매칭 알고리즘을 활용한 가지치기 기법을 소개하고 실제 그래프 데이터상에서 실험을 진행하여 제시한 기법이 문제를 효율적으로 해결하는 데 도움이 되는 방법임을 입증했다.
목차
요약
Abstract
1. 서론
2. 부분 그래프 동형 알고리즘
3. 이분매칭을 활용한 가지치기 기법
4. 실험결과
5. 결론 및 향후 연구
References
참고문헌 (10)
참고문헌 신청
Wenfei Fan, Graph pattern matching revised for social network analysis, Proc. of the 15th International Conference on Database Theory, pp. 8-21, 2012.
N Pržulj, Derek G Corneil, and Igor Jurisica, Efficient estimation of graphlet frequency distributions in protein-protein interaction networks, Bioinformatics, Vol. 22, No. 8, pp. 974-980, 2006.
Xifeng Yan, Philip S Yu, and Jiawei Han, Graph indexing: a frequent structure-based approach, Proc. of the 2004 ACM SIGMOD International Conference on Management of Data, pp. 335-346, 2004.
Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento, A (sub) graph isomorphism algorithm for matching large graphs, IEEE transactions on pattern analysis and machine intelligence, Vol. 26, No. 10, pp. 1367-1372, 2004.
Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee, Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases, Proc. of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 337-348, 2013.
N Pržulj, Derek G Corneil, and Igor Jurisica, Efficient estimation of graphlet frequency distributions in protein-protein interaction networks, Bioinformatics, Vol. 22, No. 8, pp. 974-980, 2006.
Xifeng Yan, Philip S Yu, and Jiawei Han, Graph indexing: a frequent structure-based approach, Proc. of the 2004 ACM SIGMOD International Conference on Management of Data, pp. 335-346, 2004.
Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento, A (sub) graph isomorphism algorithm for matching large graphs, IEEE transactions on pattern analysis and machine intelligence, Vol. 26, No. 10, pp. 1367-1372, 2004.
Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee, Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases, Proc. of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 337-348, 2013.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
New Adaptive Matching Order and Performance Comparison for Subgraph Matching Problem
Journal of KIISE
2022 .01
-
부분 그래프 동형 문제를 위한 동적 매칭 순서들의 성능 비교
정보과학회 컴퓨팅의 실제 논문지
2020 .01
-
Spark 환경에서 대용량 그래프 유사 서브 그래프 매칭 기법
정보과학회 컴퓨팅의 실제 논문지
2018 .09
-
이분 매칭 기반의 가지치기를 활용한 부분 그래프 동형 알고리즘 성능 향상
한국정보과학회 학술발표논문집
2020 .12
-
요약 그래프 상에서 효과적인 그래프 압축 기법
한국정보과학회 학술발표논문집
2016 .06
-
그래프 국소 정보 추출을 통한 분할 알고리즘 기반 그래프 분류 방법
한국정보과학회 학술발표논문집
2021 .12
-
동적 그래프에서 효율적인 그래프 요약 기법
한국정보과학회 학술발표논문집
2015 .12
-
그래프 동형 문제를 위한 최신 알고리즘 비교
한국정보과학회 학술발표논문집
2023 .06
-
Efficient Shortest Path Techniques on a Summarized Graph based on the Relationships
Journal of KIISE
2017 .07
-
그래프 동형 문제를 위한 최신 알고리즘 비교
정보과학회 컴퓨팅의 실제 논문지
2023 .12
-
Index-based Searching for Isomorphic Subgraphs in Hypergraph Databases
Journal of KIISE
2019 .07
-
이질형 그래프에서의 간선 예측을 위한 고차 그래프 뉴럴 네트워크
한국정보과학회 학술발표논문집
2021 .06
-
An Embedding Technique for Weighted Graphs using LSTM Autoencoders
Journal of KIISE
2021 .01
-
고차 그래프 뉴럴 네트워크를 활용한 이질형 그래프에서의 링크 예측
정보과학회 컴퓨팅의 실제 논문지
2022 .08
-
동적 환경 소셜 네트워크 그래프에서 다중 제약 조건 그래프 패턴 매칭
한국정보과학회 학술발표논문집
2015 .12
-
GPU를 이용한 경로 기반 하이브리드 그래프 처리 기법
정보과학회 컴퓨팅의 실제 논문지
2024 .11
-
영상 검색에서 그래프 구조를 이용한 스켈레톤 데이터 그래프 모델링 기법
한국정보과학회 학술발표논문집
2020 .12
-
그래프 오더링을 활용한 그래프 병렬 처리의 성능 향상
한국정보과학회 학술발표논문집
2017 .12
-
동형 서브그래프 질의 처리를 위한 효율적인 그래프 경로 기반 인덱싱 기법
정보과학회 컴퓨팅의 실제 논문지
2018 .05
-
외부 지식 그래프 결합을 위한 그래프 트랜스포머 알고리즘
한국정보과학회 학술발표논문집
2023 .06
이 논문의 저자 정보
최근 본 자료
댓글(0)
0