A directed hypergraph is a generalized concept of a directed graph. A directed hypergraph has hy-peredges which have multiple source nodes and multiple target nodes. Hyperedges are useful to model rela-tionships that exists between multiple entities. For example we can model chemical reactions that have mul-tiple substrates and multiple products and protein-protein interaction networks with hypergraphs. Moreover graph structure supports heterogeneous nodes and relationships between those nodes. Thus we can model a heterogeneous types of data like a hypergraph of chemicals, genes, drugs, and diseases.
With such hypergraphs we can consider problems finding reachable target nodes from given source nodes and finding minimum source nodes that can reach given target nodes. We named those problems as Target Set Finding Problem (TSFP) and Source Set Finding Problem (SSFP) respectively. TSFP can be solved in polynomial time but SSFP is NP-hard. Thus, we proposed an indexing approach, MSS Index. MSS Index precomputes all minimal source sets (MSS) of each nodes to solve SSFP.
In a large hypergraph, MSS Index may grows very largely thus we suggest a decomposition method and a reconstruction method. Moreover, we suggest ways to managing MSS Index when some nodes or hy-peredges are inserted or deleted. We extended TSFP/SSFP to solve with conditions of disabled nodes/hyperedges and the always reachable nodes.
We implemented a hypergraph store with neo4j. TSFP can be solved even in large graph and SSFP saved many computation times with MSS Index. MSS Index enables online computation of SSFP and can be applied with real dataset around 100 thousands of nodes.
유향 하이퍼그래프는 유향 그래프의 일반화된 개념으로 다수의 노드를 연결하는 하이퍼에지를 가진다. 이는 다수의 엔티티가 동시에 관계를 맺는 데이터를 모델링하는데 적합하다. 예를 들면 다수의 화합물이 동시에 반응하는 화학 작용이나 다수의 단백질간의 관계를 표현한 단백질 상호작용 네트워크를 모델링하는데 사용할 수 있다.
이러한 유향 하이퍼그래프 기반의 데이터에서 주어진 노드들로부터 닿을 수 있는 타겟 노드를 찾는 문제와, 주어진 타겟 노드들에 닿기 위해 필요한 최소의 소스 집합(minimum source set)을 찾는 문제를 생각해 볼 수 있다. 본 연구에서는 타겟 노드를 찾는 문제인 타겟 집합 찾기 문제(Target Set Finding Problem, TSFP)와 최소의 소스 집합을 찾는 문제인 소스 집합 찾기 문제(Source Set Finding Problem, SSFP)를 정의하고 이를 해결하기 위한 알고리즘을 제시한다.
TSFP는 다항 시간에 해결할 수 있는 문제이지만, SSFP는 NP-hard이다. 본 연구에서는 이 문제의 해답을 찾기 위해 노드에 도착할 수 있는 최적 소스 집합(minimal source set)을 미리 계산하여 인덱싱 하는 방법을 제안한다.
크기가 큰 그래프에서는 최적 소스 집합 인덱스의 크기가 커지므로 분할하여 저장하고 이후 질의가 주어지면 분할된 인덱스를 다시 조합하여 최적 소스 집합을 찾는다. 또한, 하이퍼그래프 데이터가 변경되었을 때 인덱스를 수정하는 방법도 제시한다. 그리고 TSFP와 SSFP문제를 확장하여 어떤 에지나 노드가 비활성화된 상황에서나 항상 접근이 가능한 노드가 존재하는 경우에도 소스 집합과 타겟 집합을 찾을 수 있는 방법을 제시한다.
그래프 데이터베이스인 neo4j를 이용하여 하이퍼그래프 저장소를 구현했다. 실험을 통해 살펴본 결과 TSFP는 대용량 그래프에서도 적용 가능함을 보였고, SSFP의 해답은 MSS Index를 사용하면 계산량을 대폭 줄일 수 있었고, 또한 온라인 계산도 가능하게 되었다. MSS Index는 10만개 정도 노드를 가지고 있는 실제 바이오 데이터에서도 적용 가능함을 보였다.
