Ghent University Academic Bibliography

Advanced

The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees

Sofie Demeyer UGent, Tom Michoel, Jan Fostier UGent, Pieter Audenaert UGent, Mario Pickavet UGent and Piet Demeester UGent (2013) PLOS ONE. 8(4).
abstract
Subgraph matching algorithms are designed to find all instances of predefined subgraphs in a large graph or network and play an important role in the discovery and analysis of so-called network motifs, subgraph patterns which occur more often than expected by chance. We present the index-based subgraph matching algorithm (ISMA), a novel tree-based algorithm. ISMA realizes a speedup compared to existing algorithms by carefully selecting the order in which the nodes of a query subgraph are investigated. In order to achieve this, we developed a number of data structures and maximally exploited symmetry characteristics of the subgraph. We compared ISMA to a naive recursive tree-based algorithm and to a number of well-known subgraph matching algorithms. Our algorithm outperforms the other algorithms, especially on large networks and with large query subgraphs. An implementation of ISMA in Java is freely available at http://sourceforge.net/projects/isma.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
GRAPH, TOPOLOGICAL MOTIFS, ISOMORPHISM, PRINCIPLES, AGGREGATION, TOOL, IBCN
journal title
PLOS ONE
PLoS One
volume
8
issue
4
article number
e61183
pages
15 pages
Web of Science type
Article
Web of Science id
000317909500010
JCR category
MULTIDISCIPLINARY SCIENCES
JCR impact factor
3.534 (2013)
JCR rank
8/55 (2013)
JCR quartile
1 (2013)
ISSN
1932-6203
DOI
10.1371/journal.pone.0061183
project
Bioinformatics: from nucleotids to networks (N2N)
language
English
UGent publication?
yes
classification
A1
copyright statement
I have transferred the copyright for this publication to the publisher
id
4089593
handle
http://hdl.handle.net/1854/LU-4089593
date created
2013-06-28 11:34:29
date last changed
2016-12-21 15:41:18
@article{4089593,
  abstract     = {Subgraph matching algorithms are designed to find all instances of predefined subgraphs in a large graph or network and play an important role in the discovery and analysis of so-called network motifs, subgraph patterns which occur more often than expected by chance. We present the index-based subgraph matching algorithm (ISMA), a novel tree-based algorithm. ISMA realizes a speedup compared to existing algorithms by carefully selecting the order in which the nodes of a query subgraph are investigated. In order to achieve this, we developed a number of data structures and maximally exploited symmetry characteristics of the subgraph. We compared ISMA to a naive recursive tree-based algorithm and to a number of well-known subgraph matching algorithms. Our algorithm outperforms the other algorithms, especially on large networks and with large query subgraphs. An implementation of ISMA in Java is freely available at http://sourceforge.net/projects/isma.},
  articleno    = {e61183},
  author       = {Demeyer, Sofie and Michoel, Tom and Fostier, Jan and Audenaert, Pieter and Pickavet, Mario and Demeester, Piet},
  issn         = {1932-6203},
  journal      = {PLOS ONE},
  keyword      = {GRAPH,TOPOLOGICAL MOTIFS,ISOMORPHISM,PRINCIPLES,AGGREGATION,TOOL,IBCN},
  language     = {eng},
  number       = {4},
  pages        = {15},
  title        = {The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees},
  url          = {http://dx.doi.org/10.1371/journal.pone.0061183},
  volume       = {8},
  year         = {2013},
}

Chicago
Demeyer, Sofie, Tom Michoel, Jan Fostier, Pieter Audenaert, Mario Pickavet, and Piet Demeester. 2013. “The Index-based Subgraph Matching Algorithm (ISMA): Fast Subgraph Enumeration in Large Networks Using Optimized Search Trees.” Plos One 8 (4).
APA
Demeyer, S., Michoel, T., Fostier, J., Audenaert, P., Pickavet, M., & Demeester, P. (2013). The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees. PLOS ONE, 8(4).
Vancouver
1.
Demeyer S, Michoel T, Fostier J, Audenaert P, Pickavet M, Demeester P. The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees. PLOS ONE. 2013;8(4).
MLA
Demeyer, Sofie, Tom Michoel, Jan Fostier, et al. “The Index-based Subgraph Matching Algorithm (ISMA): Fast Subgraph Enumeration in Large Networks Using Optimized Search Trees.” PLOS ONE 8.4 (2013): n. pag. Print.