Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks

Antonino Aparo, Vincenzo Bonnici, Giovanni Micale, Alfredo Ferro, Dennis Shasha, Alfredo Pulvirenti, Rosalba Giugno

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A wide range of biomedical applications entails solving the subgraph isomorphism problem, i.e. finding all the possible subgraphs of a target graph that are structurally equivalent to an input pattern graph. Targets may be very large and complex structures compared to patterns. Methods that address this NP-complete problem use heuristics. Their performance in both time and quality depends on a few subtleties of those heuristics. This paper compares the performance of state-of-the-art algorithms for subgraph isomorphism on small, medium and very large graphs. Results show that heuristics based on pattern graphs alone prove to be the most efficient, an unexpected result.

Original languageEnglish (US)
Title of host publicationPractical Applications of Computational Biology and Bioinformatics, 12th International Conference
EditorsMiguel Rocha, Mohd Saberi Mohamad, Juan F. De Paz, Florentino Fdez-Riverola, Pascual Gonzalez
PublisherSpringer Verlag
Pages131-138
Number of pages8
ISBN (Print)9783319987019
DOIs
StatePublished - Jan 1 2019
Event12th International Conference on Practical Applications of Computational Biology and Bioinformatics, PACBB 2018 - Toledo, Spain
Duration: Jun 20 2018Jun 22 2018

Publication series

NameAdvances in Intelligent Systems and Computing
Volume803
ISSN (Print)2194-5357

Other

Other12th International Conference on Practical Applications of Computational Biology and Bioinformatics, PACBB 2018
CountrySpain
CityToledo
Period6/20/186/22/18

Keywords

  • Networks biology
  • Search strategy
  • Subgraph isomorphism

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks'. Together they form a unique fingerprint.

  • Cite this

    Aparo, A., Bonnici, V., Micale, G., Ferro, A., Shasha, D., Pulvirenti, A., & Giugno, R. (2019). Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks. In M. Rocha, M. S. Mohamad, J. F. De Paz, F. Fdez-Riverola, & P. Gonzalez (Eds.), Practical Applications of Computational Biology and Bioinformatics, 12th International Conference (pp. 131-138). (Advances in Intelligent Systems and Computing; Vol. 803). Springer Verlag. https://doi.org/10.1007/978-3-319-98702-6_16