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...

Descripción completa

Detalles Bibliográficos
Autores principales: Milano, Marianna, Guzzi, Pietro Hiram, Cannataro, Mario
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