Optimizing Frequent Subgraph Mining for Single Large Graph

被引：9

作者：

Dhiman, Aarzoo ^{[1
]}

Jain, S. K. ^{[1
]}

机构：

[1] Natl Inst Technol, Kurukshetra 136119, Haryana, India

来源：

TWELFTH INTERNATIONAL CONFERENCE ON COMMUNICATION NETWORKS, ICCN 2016 / TWELFTH INTERNATIONAL CONFERENCE ON DATA MINING AND WAREHOUSING, ICDMW 2016 / TWELFTH INTERNATIONAL CONFERENCE ON IMAGE AND SIGNAL PROCESSING, ICISP 2016 | 2016年 / 89卷

关键词：

Frequent Subgraph Mining; Graph; Optimization; Single Graph; Subgraph Isomorphism; PATTERNS;

D O I：

10.1016/j.procs.2016.06.085

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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. (C) 2016 The Authors. Published by Elsevier B.V.

引用

页码：378 / 385

页数：8

共 16 条

[1]

Aggarwal CC, 2010, ADV DATABASE SYST, V40, P1, DOI 10.1007/978-1-4419-6045-0

[2]

[Anonymous], 2015, Graph Databases

[3]

Bringmann B, 2008, LECT NOTES ARTIF INT, V5012, P858, DOI 10.1007/978-3-540-68125-0_84

[4] Graph mining: Laws, generators, and algorithms [J].

Chakrabarti, Deepayan ;

Faloutsos, Christos .

ACM COMPUTING SURVEYS, 2006, 38 (01) :A1-A69

[5] GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph [J].

Elseidy, Mohammed ;

Abdelhamid, Ehab ;

Skiadopoulos, Spiros ;

Kalnis, Panos .

PROCEEDINGS OF THE VLDB ENDOWMENT, 2014, 7 (07) :517-528

[6]

Fiedler M., 2007, PROC ICDMW, P399

[7]

Ghazizadeh S, 2002, LECT NOTES COMPUT SC, V2534, P71

[8] Discovering frequent graph patterns using disjoint paths [J].

Gudes, Ehud ;

Shimony, Solomon Eyal ;

Vanetik, Natalia .

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2006, 18 (11) :1441-1456

[9] NODAR: mining globally distributed substructures from a single labeled graph [J].

Hellal, Aya ;

Ben Romdhane, Lotfi .

JOURNAL OF INTELLIGENT INFORMATION SYSTEMS, 2013, 40 (01) :1-15

[10] Mining globally distributed frequent subgraphs in a single labeled graph [J].

Jiang, Xing ;

Xiong, Hui ;

Wang, Chen ;

Tan, Ah-Hwee .

DATA & KNOWLEDGE ENGINEERING, 2009, 68 (10) :1034-1058

← 1 2 →