Hunting for vital nodes in complex networks using local information

Abstract Complex networks in the real world are often with heterogeneous degree distributions. The structure and function of nodes can vary significantly, with vital nodes playing a crucial role in information spread and other spreading phenomena. Identifying and taking action on vital nodes enables...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Zhihao Dong, Yuanzhu Chen, Terrence S. Tricco, Cheng Li, Ting Hu
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/806530f6fa604145b6d5aa6e10722bb7
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:806530f6fa604145b6d5aa6e10722bb7
record_format	dspace
spelling	oai:doaj.org-article:806530f6fa604145b6d5aa6e10722bb72021-12-02T16:55:34ZHunting for vital nodes in complex networks using local information10.1038/s41598-021-88692-92045-2322https://doaj.org/article/806530f6fa604145b6d5aa6e10722bb72021-04-01T00:00:00Zhttps://doi.org/10.1038/s41598-021-88692-9https://doaj.org/toc/2045-2322Abstract Complex networks in the real world are often with heterogeneous degree distributions. The structure and function of nodes can vary significantly, with vital nodes playing a crucial role in information spread and other spreading phenomena. Identifying and taking action on vital nodes enables change to the network’s structure and function more efficiently. Previous work either redefines metrics used to measure the nodes’ importance or focuses on developing algorithms to efficiently find vital nodes. These approaches typically rely on global knowledge of the network and assume that the structure of the network does not change over time, both of which are difficult to achieve in the real world. In this paper, we propose a localized strategy that can find vital nodes without global knowledge of the network. Our joint nomination (JN) strategy selects a random set of nodes along with a set of nodes connected to those nodes, and together they nominate the vital node set. Experiments are conducted on 12 network datasets that include synthetic and real-world networks, and undirected and directed networks. Results show that average degree of the identified node set is about 3–8 times higher than that of the full node set, and higher-degree nodes take larger proportions in the degree distribution of the identified vital node set. Removal of vital nodes increases the average shortest path length by 20–70% over the original network, or about 8–15% longer than the other decentralized strategies. Immunization based on JN is more efficient than other strategies, consuming around 12–40% less immunization resources to raise the epidemic threshold to $$\tau \sim 0.1$$ τ ∼ 0.1 . Susceptible-infected-recovered simulations on networks with 30% vital nodes removed using JN delays the arrival time of infection peak significantly and reduce the total infection scale to 15%. The proposed strategy can effectively identify vital nodes using only local information and is feasible to implement in the real world to cope with time-critical scenarios such as the sudden outbreak of COVID-19.Zhihao DongYuanzhu ChenTerrence S. TriccoCheng LiTing HuNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 11, Iss 1, Pp 1-13 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Zhihao Dong Yuanzhu Chen Terrence S. Tricco Cheng Li Ting Hu Hunting for vital nodes in complex networks using local information
description	Abstract Complex networks in the real world are often with heterogeneous degree distributions. The structure and function of nodes can vary significantly, with vital nodes playing a crucial role in information spread and other spreading phenomena. Identifying and taking action on vital nodes enables change to the network’s structure and function more efficiently. Previous work either redefines metrics used to measure the nodes’ importance or focuses on developing algorithms to efficiently find vital nodes. These approaches typically rely on global knowledge of the network and assume that the structure of the network does not change over time, both of which are difficult to achieve in the real world. In this paper, we propose a localized strategy that can find vital nodes without global knowledge of the network. Our joint nomination (JN) strategy selects a random set of nodes along with a set of nodes connected to those nodes, and together they nominate the vital node set. Experiments are conducted on 12 network datasets that include synthetic and real-world networks, and undirected and directed networks. Results show that average degree of the identified node set is about 3–8 times higher than that of the full node set, and higher-degree nodes take larger proportions in the degree distribution of the identified vital node set. Removal of vital nodes increases the average shortest path length by 20–70% over the original network, or about 8–15% longer than the other decentralized strategies. Immunization based on JN is more efficient than other strategies, consuming around 12–40% less immunization resources to raise the epidemic threshold to $$\tau \sim 0.1$$ τ ∼ 0.1 . Susceptible-infected-recovered simulations on networks with 30% vital nodes removed using JN delays the arrival time of infection peak significantly and reduce the total infection scale to 15%. The proposed strategy can effectively identify vital nodes using only local information and is feasible to implement in the real world to cope with time-critical scenarios such as the sudden outbreak of COVID-19.
format	article
author	Zhihao Dong Yuanzhu Chen Terrence S. Tricco Cheng Li Ting Hu
author_facet	Zhihao Dong Yuanzhu Chen Terrence S. Tricco Cheng Li Ting Hu
author_sort	Zhihao Dong
title	Hunting for vital nodes in complex networks using local information
title_short	Hunting for vital nodes in complex networks using local information
title_full	Hunting for vital nodes in complex networks using local information
title_fullStr	Hunting for vital nodes in complex networks using local information
title_full_unstemmed	Hunting for vital nodes in complex networks using local information
title_sort	hunting for vital nodes in complex networks using local information
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/806530f6fa604145b6d5aa6e10722bb7
work_keys_str_mv	AT zhihaodong huntingforvitalnodesincomplexnetworksusinglocalinformation AT yuanzhuchen huntingforvitalnodesincomplexnetworksusinglocalinformation AT terrencestricco huntingforvitalnodesincomplexnetworksusinglocalinformation AT chengli huntingforvitalnodesincomplexnetworksusinglocalinformation AT tinghu huntingforvitalnodesincomplexnetworksusinglocalinformation
_version_	1718382808964005888

Hunting for vital nodes in complex networks using local information

Ejemplares similares