Finding a Minimum Source Set in Directed Hypergraphs

HYUN JUN KIM ； KWANG HEE LEE ； MYOUNG HO KIM

《Journal of Information Science and Engineering》 33卷2期 (2017/03) Pp. 413-428

https://doi.org/10.6688/JISE.2017.33.2.8

摘要

A directed hypergraph has hyperedges that connect multiple source nodes and multiple target nodes. These hyperedges are useful to model relationships between multiple entities, which often occur in the biological network. This paper focuses on the problem to find a minimum cardinality source set shortly, a Minimum Source Set (MinSS) that can reach a set of given target nodes. However, this problem is NP-hard, and hence requires a large amount of computation time even for a problem with a small size. We propose the MSS index where for each node the set of precomputed all minimal source sets is maintained. By constructing an MSS index in advance, a MinSS for any node can be obtained in a very short time. To avoid too much large size of the MSS index for a very large hypergraph, we propose a reduction method using the source set proxy. We also describe how to maintain the MSS index for insertion and deletion of nodes and hyperedges. We show through performance experiments that our proposed method can be a viable solution for the MinSS problem in the sense that the MSS index can handle the problems with reasonably large sizes in acceptable amounts of time.

關鍵字

directed hypergraph ； minimal source set ； index ； graph processing ； knowledge discovery