Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4962178 | Procedia Computer Science | 2016 | 8 Pages |
Abstract
Frequent subgraph mining (FSM) is defined as finding all the subgraphs in a given graph that appear more number of times than a given value. It consists of two steps broadly, first is generating a candidate subgraph and second is calculating support of that subgraph. When the input to FSM algorithm is a single graph, calculating support of subgraph needs identifying its isomorphisms in the input graph. Identifying subgraph isomorphisms is NP-Complete problem. Evidently, fewer the number of candidates, fewer the support computations needed. In this paper we present a filtration technique that reduces the number of candidate subgraphs thereby reducing the overall time complexity by 7 to 18% experimentally.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Aarzoo Dhiman, S.K. Jain,