A hypergraph consisting of vertices and hyperedges that connect multiple vertices can model complex relationships among entities effectively. In this work, we study a searching of subhypergraph isomorphism that finds all isomorphic subhypergraphs to the query. Existing works of subgraph isomorphism in an ordinary graph try to reduce search space for a query graph to decrease computational costs, since a subgraph isomorphism problem is known to be NP-hard. However, previous methods of finding isomorphic subhypergraphs for hypergraphs do not make much effort for decreasing costs. In this thesis, we propose a method that finds subhypergraph isomorphism efficiently. We first select vertices and hyperedges that are likely to match to a query hypergraph, with consideration for characteristics of hyperedges. Then, we verify isomorphism between remaining subgraphs of data hypergraph and a query hypergraph. Experimental results show that our proposed method outperforms existing methods.
노드와 다수의 노드를 연결하는 하이퍼에지로 구성된 하이퍼그래프는 개체 간의 복잡한 복잡한 관계를 효율적으로 모델링할 수 있다. 본 연구에서는 질의와 동형인 모든 서브하이퍼그래프를 찾는 동형 서브하이퍼그래프 탐색 방법을 연구하였다. 보통의 일반 그래프에 대한 기존 동형 서브그래프 탐색 연구들은 동형 서브그래프 문제가 NP-hard에 속하기 때문에, 계산 비용을 줄이기 위해 질의 그래프에 대한 탐색 공간을 줄이고자 하였다. 그러나 동형 서브하이퍼그래프를 찾는 이전 연구에서는 계산 비용을 줄이기 위한 연구가 제대로 진행되지 않았다. 본 논문에서는 동형 서브하이퍼그래프를 효율적으로 찾는 방법에 대해 제안한다. 제안한 방법은 먼저 하이퍼에지의 특성을 고려하여, 질의 하이퍼그래프 매치될 수 있는 노드와 하이퍼에지를 선택한다. 그 후, 선택된 데이터 하이퍼그래프의 서브그래프들에 대해 질의 하이퍼그래프와 동형 여부를 확인한다. 실험 결과는 제안한 방법이 기존 방법에 비해 효율적임을 보인다.
