The localization of non-backtracking centrality in networks and its physical consequences

Abstract The spectrum of the non-backtracking matrix plays a crucial role in determining various structural and dynamical properties of networked systems, ranging from the threshold in bond percolation and non-recurrent epidemic processes, to community structure, to node importance. Here we calculat...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Romualdo Pastor-Satorras, Claudio Castellano
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2020
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/9e0c175180e54faeab0b429c62930bf3
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:9e0c175180e54faeab0b429c62930bf3
record_format	dspace
spelling	oai:doaj.org-article:9e0c175180e54faeab0b429c62930bf32021-12-02T15:11:52ZThe localization of non-backtracking centrality in networks and its physical consequences10.1038/s41598-020-78582-x2045-2322https://doaj.org/article/9e0c175180e54faeab0b429c62930bf32020-12-01T00:00:00Zhttps://doi.org/10.1038/s41598-020-78582-xhttps://doaj.org/toc/2045-2322Abstract The spectrum of the non-backtracking matrix plays a crucial role in determining various structural and dynamical properties of networked systems, ranging from the threshold in bond percolation and non-recurrent epidemic processes, to community structure, to node importance. Here we calculate the largest eigenvalue of the non-backtracking matrix and the associated non-backtracking centrality for uncorrelated random networks, finding expressions in excellent agreement with numerical results. We show however that the same formulas do not work well for many real-world networks. We identify the mechanism responsible for this violation in the localization of the non-backtracking centrality on network subgraphs whose formation is highly unlikely in uncorrelated networks, but rather common in real-world structures. Exploiting this knowledge we present an heuristic generalized formula for the largest eigenvalue, which is remarkably accurate for all networks of a large empirical dataset. We show that this newly uncovered localization phenomenon allows to understand the failure of the message-passing prediction for the percolation threshold in many real-world structures.Romualdo Pastor-SatorrasClaudio CastellanoNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 10, Iss 1, Pp 1-12 (2020)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Romualdo Pastor-Satorras Claudio Castellano The localization of non-backtracking centrality in networks and its physical consequences
description	Abstract The spectrum of the non-backtracking matrix plays a crucial role in determining various structural and dynamical properties of networked systems, ranging from the threshold in bond percolation and non-recurrent epidemic processes, to community structure, to node importance. Here we calculate the largest eigenvalue of the non-backtracking matrix and the associated non-backtracking centrality for uncorrelated random networks, finding expressions in excellent agreement with numerical results. We show however that the same formulas do not work well for many real-world networks. We identify the mechanism responsible for this violation in the localization of the non-backtracking centrality on network subgraphs whose formation is highly unlikely in uncorrelated networks, but rather common in real-world structures. Exploiting this knowledge we present an heuristic generalized formula for the largest eigenvalue, which is remarkably accurate for all networks of a large empirical dataset. We show that this newly uncovered localization phenomenon allows to understand the failure of the message-passing prediction for the percolation threshold in many real-world structures.
format	article
author	Romualdo Pastor-Satorras Claudio Castellano
author_facet	Romualdo Pastor-Satorras Claudio Castellano
author_sort	Romualdo Pastor-Satorras
title	The localization of non-backtracking centrality in networks and its physical consequences
title_short	The localization of non-backtracking centrality in networks and its physical consequences
title_full	The localization of non-backtracking centrality in networks and its physical consequences
title_fullStr	The localization of non-backtracking centrality in networks and its physical consequences
title_full_unstemmed	The localization of non-backtracking centrality in networks and its physical consequences
title_sort	localization of non-backtracking centrality in networks and its physical consequences
publisher	Nature Portfolio
publishDate	2020
url	https://doaj.org/article/9e0c175180e54faeab0b429c62930bf3
work_keys_str_mv	AT romualdopastorsatorras thelocalizationofnonbacktrackingcentralityinnetworksanditsphysicalconsequences AT claudiocastellano thelocalizationofnonbacktrackingcentralityinnetworksanditsphysicalconsequences AT romualdopastorsatorras localizationofnonbacktrackingcentralityinnetworksanditsphysicalconsequences AT claudiocastellano localizationofnonbacktrackingcentralityinnetworksanditsphysicalconsequences
_version_	1718387647818235904

The localization of non-backtracking centrality in networks and its physical consequences

Ejemplares similares