Cargando…
Design and Implementation of a New Local Alignment Algorithm for Multilayer Networks
Network alignment (NA) is a popular research field that aims to develop algorithms for comparing networks. Applications of network alignment span many fields, from biology to social network analysis. NA comes in two forms: global network alignment (GNA), which aims to find a global similarity, and L...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
MDPI
2022
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9497667/ https://www.ncbi.nlm.nih.gov/pubmed/36141158 http://dx.doi.org/10.3390/e24091272 |
_version_ | 1784794562799075328 |
---|---|
author | Milano, Marianna Guzzi, Pietro Hiram Cannataro, Mario |
author_facet | Milano, Marianna Guzzi, Pietro Hiram Cannataro, Mario |
author_sort | Milano, Marianna |
collection | PubMed |
description | Network alignment (NA) is a popular research field that aims to develop algorithms for comparing networks. Applications of network alignment span many fields, from biology to social network analysis. NA comes in two forms: global network alignment (GNA), which aims to find a global similarity, and LNA, which aims to find local regions of similarity. Recently, there has been an increasing interest in introducing complex network models such as multilayer networks. Multilayer networks are common in many application scenarios, such as modelling of relations among people in a social network or representing the interplay of different molecules in a cell or different cells in the brain. Consequently, the need to introduce algorithms for the comparison of such multilayer networks, i.e., local network alignment, arises. Existing algorithms for LNA do not perform well on multilayer networks since they cannot consider inter-layer edges. Thus, we propose local alignment of multilayer networks (MultiLoAl), a novel algorithm for the local alignment of multilayer networks. We define the local alignment of multilayer networks and propose a heuristic for solving it. We present an extensive assessment indicating the strength of the algorithm. Furthermore, we implemented a synthetic multilayer network generator to build the data for the algorithm’s evaluation. |
format | Online Article Text |
id | pubmed-9497667 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2022 |
publisher | MDPI |
record_format | MEDLINE/PubMed |
spelling | pubmed-94976672022-09-23 Design and Implementation of a New Local Alignment Algorithm for Multilayer Networks Milano, Marianna Guzzi, Pietro Hiram Cannataro, Mario Entropy (Basel) Article Network alignment (NA) is a popular research field that aims to develop algorithms for comparing networks. Applications of network alignment span many fields, from biology to social network analysis. NA comes in two forms: global network alignment (GNA), which aims to find a global similarity, and LNA, which aims to find local regions of similarity. Recently, there has been an increasing interest in introducing complex network models such as multilayer networks. Multilayer networks are common in many application scenarios, such as modelling of relations among people in a social network or representing the interplay of different molecules in a cell or different cells in the brain. Consequently, the need to introduce algorithms for the comparison of such multilayer networks, i.e., local network alignment, arises. Existing algorithms for LNA do not perform well on multilayer networks since they cannot consider inter-layer edges. Thus, we propose local alignment of multilayer networks (MultiLoAl), a novel algorithm for the local alignment of multilayer networks. We define the local alignment of multilayer networks and propose a heuristic for solving it. We present an extensive assessment indicating the strength of the algorithm. Furthermore, we implemented a synthetic multilayer network generator to build the data for the algorithm’s evaluation. MDPI 2022-09-09 /pmc/articles/PMC9497667/ /pubmed/36141158 http://dx.doi.org/10.3390/e24091272 Text en © 2022 by the authors. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). |
spellingShingle | Article Milano, Marianna Guzzi, Pietro Hiram Cannataro, Mario Design and Implementation of a New Local Alignment Algorithm for Multilayer Networks |
title | Design and Implementation of a New Local Alignment Algorithm for Multilayer Networks |
title_full | Design and Implementation of a New Local Alignment Algorithm for Multilayer Networks |
title_fullStr | Design and Implementation of a New Local Alignment Algorithm for Multilayer Networks |
title_full_unstemmed | Design and Implementation of a New Local Alignment Algorithm for Multilayer Networks |
title_short | Design and Implementation of a New Local Alignment Algorithm for Multilayer Networks |
title_sort | design and implementation of a new local alignment algorithm for multilayer networks |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9497667/ https://www.ncbi.nlm.nih.gov/pubmed/36141158 http://dx.doi.org/10.3390/e24091272 |
work_keys_str_mv | AT milanomarianna designandimplementationofanewlocalalignmentalgorithmformultilayernetworks AT guzzipietrohiram designandimplementationofanewlocalalignmentalgorithmformultilayernetworks AT cannataromario designandimplementationofanewlocalalignmentalgorithmformultilayernetworks |