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.
Titolo: | Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks |
Autori interni: | |
Data di pubblicazione: | 2019 |
Serie: | |
Handle: | http://hdl.handle.net/20.500.11769/361595 |
ISBN: | 9783319987019 |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |