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: