Shortest Paths in Multiplex Networks

Abstract The shortest path problem is one of the most fundamental networks optimization problems. Nowadays, individuals interact in extraordinarily numerous ways through their offline and online life (e.g., co-authorship, co-workership, or retweet relation in Twitter). These interactions have two ke...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Saeed Ghariblou, Mostafa Salehi, Matteo Magnani, Mahdi Jalili
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2017
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/de36e3bfc2314b6585af54655cffc61c
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:de36e3bfc2314b6585af54655cffc61c
record_format	dspace
spelling	oai:doaj.org-article:de36e3bfc2314b6585af54655cffc61c2021-12-02T11:40:50ZShortest Paths in Multiplex Networks10.1038/s41598-017-01655-x2045-2322https://doaj.org/article/de36e3bfc2314b6585af54655cffc61c2017-05-01T00:00:00Zhttps://doi.org/10.1038/s41598-017-01655-xhttps://doaj.org/toc/2045-2322Abstract The shortest path problem is one of the most fundamental networks optimization problems. Nowadays, individuals interact in extraordinarily numerous ways through their offline and online life (e.g., co-authorship, co-workership, or retweet relation in Twitter). These interactions have two key features. First, they have a heterogeneous nature, and second, they have different strengths that are weighted based on their degree of intimacy, trustworthiness, service exchange or influence among individuals. These networks are known as multiplex networks. To our knowledge, none of the previous shortest path definitions on social interactions have properly reflected these features. In this work, we introduce a new distance measure in multiplex networks based on the concept of Pareto efficiency taking both heterogeneity and weighted nature of relations into account. We then model the problem of finding the whole set of paths as a form of multiple objective decision making and propose an exact algorithm for that. The method is evaluated on five real-world datasets to test the impact of considering weights and multiplexity in the resulting shortest paths. As an application to find the most influential nodes, we redefine the concept of betweenness centrality based on the proposed shortest paths and evaluate it on a real-world dataset from two-layer trade relation among countries between years 2000 and 2015.Saeed GhariblouMostafa SalehiMatteo MagnaniMahdi JaliliNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 7, Iss 1, Pp 1-8 (2017)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Saeed Ghariblou Mostafa Salehi Matteo Magnani Mahdi Jalili Shortest Paths in Multiplex Networks
description	Abstract The shortest path problem is one of the most fundamental networks optimization problems. Nowadays, individuals interact in extraordinarily numerous ways through their offline and online life (e.g., co-authorship, co-workership, or retweet relation in Twitter). These interactions have two key features. First, they have a heterogeneous nature, and second, they have different strengths that are weighted based on their degree of intimacy, trustworthiness, service exchange or influence among individuals. These networks are known as multiplex networks. To our knowledge, none of the previous shortest path definitions on social interactions have properly reflected these features. In this work, we introduce a new distance measure in multiplex networks based on the concept of Pareto efficiency taking both heterogeneity and weighted nature of relations into account. We then model the problem of finding the whole set of paths as a form of multiple objective decision making and propose an exact algorithm for that. The method is evaluated on five real-world datasets to test the impact of considering weights and multiplexity in the resulting shortest paths. As an application to find the most influential nodes, we redefine the concept of betweenness centrality based on the proposed shortest paths and evaluate it on a real-world dataset from two-layer trade relation among countries between years 2000 and 2015.
format	article
author	Saeed Ghariblou Mostafa Salehi Matteo Magnani Mahdi Jalili
author_facet	Saeed Ghariblou Mostafa Salehi Matteo Magnani Mahdi Jalili
author_sort	Saeed Ghariblou
title	Shortest Paths in Multiplex Networks
title_short	Shortest Paths in Multiplex Networks
title_full	Shortest Paths in Multiplex Networks
title_fullStr	Shortest Paths in Multiplex Networks
title_full_unstemmed	Shortest Paths in Multiplex Networks
title_sort	shortest paths in multiplex networks
publisher	Nature Portfolio
publishDate	2017
url	https://doaj.org/article/de36e3bfc2314b6585af54655cffc61c
work_keys_str_mv	AT saeedghariblou shortestpathsinmultiplexnetworks AT mostafasalehi shortestpathsinmultiplexnetworks AT matteomagnani shortestpathsinmultiplexnetworks AT mahdijalili shortestpathsinmultiplexnetworks
_version_	1718395551774408704

Shortest Paths in Multiplex Networks

Ejemplares similares