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/.
authors.affiliation: Department of Information Technology, Ghent University, Ghent, Belgium. Sofie.Demeyer@intec.ugent.be
authors.forename: Sofie
authors.initials: S
authors.lastname: Demeyer
authors.forename: Tom
authors.initials: T
authors.lastname: Michoel
authors.forename: Jan
authors.initials: J
authors.lastname: Fostier
authors.forename: Pieter
authors.initials: P
authors.lastname: Audenaert
authors.forename: Mario
authors.initials: M
authors.lastname: Pickavet
authors.forename: Piet
authors.initials: P
authors.lastname: Demeester
mesh_terms: D000465:Algorithms; D015398:Signal Transduction; D012984:Software; D013997:Time Factors