Advanced search
2 files | 2.17 MB

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).
Author
Organization
Project
Bioinformatics: from nucleotids to networks (N2N)
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.
Keywords
GRAPH, TOPOLOGICAL MOTIFS, ISOMORPHISM, PRINCIPLES, AGGREGATION, TOOL, IBCN

Downloads

  • 5626 i.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 1.05 MB
  • 5626.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 1.12 MB

Citation

Please use this url to cite or link to this publication:

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.
@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},
}

Altmetric
View in Altmetric
Web of Science
Times cited: