| Title |
The Index-Based Subgraph Matching Algorithm (ISMA): Fast Subgraph Enumeration in Large Networks Using Optimized Search Trees
|
|---|---|
| Published in |
PLOS ONE, April 2013
|
| DOI | 10.1371/journal.pone.0061183 |
| Pubmed ID | |
| Authors |
Sofie Demeyer, Tom Michoel, Jan Fostier, Pieter Audenaert, Mario Pickavet, Piet Demeester |
| 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/. |
X Demographics
The data shown below were collected from the profiles of 4 X users who shared this research output. Click here to find out more about how the information was compiled.
Geographical breakdown
| Country | Count | As % |
|---|---|---|
| Canada | 1 | 25% |
| Korea, Republic of | 1 | 25% |
| Italy | 1 | 25% |
| United States | 1 | 25% |
Demographic breakdown
| Type | Count | As % |
|---|---|---|
| Members of the public | 4 | 100% |
Mendeley readers
The data shown below were compiled from readership statistics for 38 Mendeley readers of this research output. Click here to see the associated Mendeley record.
Geographical breakdown
| Country | Count | As % |
|---|---|---|
| United Kingdom | 1 | 3% |
| China | 1 | 3% |
| Luxembourg | 1 | 3% |
| Unknown | 35 | 92% |
Demographic breakdown
| Readers by professional status | Count | As % |
|---|---|---|
| Student > Ph. D. Student | 12 | 32% |
| Researcher | 9 | 24% |
| Other | 3 | 8% |
| Student > Doctoral Student | 2 | 5% |
| Student > Bachelor | 2 | 5% |
| Other | 5 | 13% |
| Unknown | 5 | 13% |
| Readers by discipline | Count | As % |
|---|---|---|
| Computer Science | 14 | 37% |
| Agricultural and Biological Sciences | 4 | 11% |
| Psychology | 3 | 8% |
| Engineering | 3 | 8% |
| Biochemistry, Genetics and Molecular Biology | 2 | 5% |
| Other | 6 | 16% |
| Unknown | 6 | 16% |