The subgraph isomorphism (SubGI) problem is known to be a NP-Complete problem. Several methodologies use heuristic approaches to solve it, differing into the strategy to search the occurrences of a graph into another. This choice strongly influences their computational effort requirement. We investigate seven search strategies where global and local topological properties of the graphs are exploited by means of weighted graph centrality measures. Results on benchmarks of biological networks show the competitiveness of the proposed seven alternatives and that, among them, local strategies predominate on sparse target graphs, and closeness- and eigenvector-based strategies outperform on dense graphs.

Centrality Speeds the Subgraph Isomorphism Search Up in Target Aware Contexts / Bonnici, Vincenzo; Caligola, Simone; Aparo, Antonino; Giugno, Rosalba. - ELETTRONICO. - 11925:1(2020), pp. 19-26. ((Intervento presentato al convegno Computational Intelligence Methods for Bioinformatics and Biostatistics. CIBB 2018 tenutosi a Caparica, Prortugal. nel 5-8 September 2018 [10.1007/978-3-030-34585-3_3].

Centrality Speeds the Subgraph Isomorphism Search Up in Target Aware Contexts

Bonnici, Vincenzo;
2020

Abstract

The subgraph isomorphism (SubGI) problem is known to be a NP-Complete problem. Several methodologies use heuristic approaches to solve it, differing into the strategy to search the occurrences of a graph into another. This choice strongly influences their computational effort requirement. We investigate seven search strategies where global and local topological properties of the graphs are exploited by means of weighted graph centrality measures. Results on benchmarks of biological networks show the competitiveness of the proposed seven alternatives and that, among them, local strategies predominate on sparse target graphs, and closeness- and eigenvector-based strategies outperform on dense graphs.
978-3-030-34584-6
Centrality Speeds the Subgraph Isomorphism Search Up in Target Aware Contexts / Bonnici, Vincenzo; Caligola, Simone; Aparo, Antonino; Giugno, Rosalba. - ELETTRONICO. - 11925:1(2020), pp. 19-26. ((Intervento presentato al convegno Computational Intelligence Methods for Bioinformatics and Biostatistics. CIBB 2018 tenutosi a Caparica, Prortugal. nel 5-8 September 2018 [10.1007/978-3-030-34585-3_3].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2901546
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact