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-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
