@article{3f241d90dbb64fafab64eab41727d40f,
title = "The Index-Based Subgraph Matching Algorithm (ISMA): Fast Subgraph Enumeration in Large Networks Using Optimized Search Trees",
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/.",
author = "Sofie Demeyer and Tom Michoel and Jan Fostier and Pieter Audenaert and Mario Pickavet and Piet Demeester",
year = "2013",
doi = "10.1371/journal.pone.0061183",
language = "English",
volume = "8",
pages = "e61183",
journal = "PLoS ONE",
issn = "1932-6203",
publisher = "Public Library of Science",
number = "4",
}