1. Optimizing Frequent Subgraph Mining for Single Large Graph
- Author
-
Sarika Jain and Aarzoo Dhiman
- Subjects
Optimization ,Factor-critical graph ,Mathematical optimization ,Computer science ,Subgraph isomorphism problem ,Color-coding ,02 engineering and technology ,Reconstruction conjecture ,Degeneracy (graph theory) ,Graph ,Maximum common subgraph isomorphism problem ,law.invention ,Combinatorics ,Claw-free graph ,Computer Science::Discrete Mathematics ,Graph power ,law ,020204 information systems ,Line graph ,0202 electrical engineering, electronic engineering, information engineering ,Cograph ,Induced subgraph isomorphism problem ,Graph homomorphism ,Rook's graph ,Subgraph Isomorphism ,Computer Science::Data Structures and Algorithms ,Time complexity ,General Environmental Science ,Universal graph ,Forbidden graph characterization ,Distance-hereditary graph ,Connected component ,Mathematics::Combinatorics ,Single Graph ,Butterfly graph ,General Earth and Planetary Sciences ,020201 artificial intelligence & image processing ,Isomorphism ,Frequent Subgraph Mining ,Graph factorization ,MathematicsofComputing_DISCRETEMATHEMATICS - 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.
- Published
- 2016
- Full Text
- View/download PDF