We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On Minimal Unique Induced Subgraph Queries.
- Authors
Jiang, Lincheng; Zhao, Xiang; Ge, Bin; Hu, Shengze; Xiao, Weidong; Shang, Haichuan; Jing, Yumei
- Abstract
Featured Application: MUIS (Minimal Unique Induced Subgraph) query can be used in many potential applications, such as subgraph retrieval, graph visualization, representative subgraph discovery and vertex property exploration. In this paper, a novel type of interesting subgraph query is proposed: Minimal Unique Induced Subgraph (MUIS) query. Given a (large) graph G and a query vertex (position) q in the graph, can we find an induced subgraph containing q with the minimal number of vertices that is unique in G? MUIS query has many potential applications, such as subgraph retrieval, graph visualization, representative subgraph discovery and vertex property exploration. The formal definition of MUIS is given and the properties are discussed in this paper. The baseline and EQA (Efficient Query Answering) algorithms are proposed to solve the MUIS query problem under the filtering-validation framework. In the EQA algorithm, the Breadth First Search (BFS)-based candidate set generation strategy is proposed to ensure the minimality property of MUIS; the matched vertices-based pruning strategy is proposed to prune useless candidate sets and the unnecessary subgraph isomorphism; and the query position-based subgraph isomorphism is proposed to check efficiently the uniqueness of the subgraphs. Experiments are carried on real datasets and synthetic datasets to verify the effectiveness and efficiency of the proposed algorithm under novel measurements. The influencing factors of the process speed are discussed at last in the paper.
- Subjects
SUBGRAPHS; DATA visualization; QUERYING (Computer science)
- Publication
Applied Sciences (2076-3417), 2018, Vol 8, Issue 10, p1798
- ISSN
2076-3417
- Publication type
Article
- DOI
10.3390/app8101798