Cargando…

Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition

We introduce a network statistic that measures structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and interpretable at a glance. Our statistic, the onion spectrum, is based on the onion decomposition, which refines the k-core decomposition, a standa...

Descripción completa

Detalles Bibliográficos
Autores principales: Hébert-Dufresne, Laurent, Grochow, Joshua A., Allard, Antoine
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Nature Publishing Group 2016
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4989159/
https://www.ncbi.nlm.nih.gov/pubmed/27535466
http://dx.doi.org/10.1038/srep31708
_version_ 1782448526658109440
author Hébert-Dufresne, Laurent
Grochow, Joshua A.
Allard, Antoine
author_facet Hébert-Dufresne, Laurent
Grochow, Joshua A.
Allard, Antoine
author_sort Hébert-Dufresne, Laurent
collection PubMed
description We introduce a network statistic that measures structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and interpretable at a glance. Our statistic, the onion spectrum, is based on the onion decomposition, which refines the k-core decomposition, a standard network fingerprinting method. The onion spectrum is exactly as easy to compute as the k-cores: It is based on the stages at which each vertex gets removed from a graph in the standard algorithm for computing the k-cores. Yet, the onion spectrum reveals much more information about a network, and at multiple scales; for example, it can be used to quantify node heterogeneity, degree correlations, centrality, and tree- or lattice-likeness. Furthermore, unlike the k-core decomposition, the combined degree-onion spectrum immediately gives a clear local picture of the network around each node which allows the detection of interesting subgraphs whose topological structure differs from the global network organization. This local description can also be leveraged to easily generate samples from the ensemble of networks with a given joint degree-onion distribution. We demonstrate the utility of the onion spectrum for understanding both static and dynamic properties on several standard graph models and on many real-world networks.
format Online
Article
Text
id pubmed-4989159
institution National Center for Biotechnology Information
language English
publishDate 2016
publisher Nature Publishing Group
record_format MEDLINE/PubMed
spelling pubmed-49891592016-08-30 Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition Hébert-Dufresne, Laurent Grochow, Joshua A. Allard, Antoine Sci Rep Article We introduce a network statistic that measures structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and interpretable at a glance. Our statistic, the onion spectrum, is based on the onion decomposition, which refines the k-core decomposition, a standard network fingerprinting method. The onion spectrum is exactly as easy to compute as the k-cores: It is based on the stages at which each vertex gets removed from a graph in the standard algorithm for computing the k-cores. Yet, the onion spectrum reveals much more information about a network, and at multiple scales; for example, it can be used to quantify node heterogeneity, degree correlations, centrality, and tree- or lattice-likeness. Furthermore, unlike the k-core decomposition, the combined degree-onion spectrum immediately gives a clear local picture of the network around each node which allows the detection of interesting subgraphs whose topological structure differs from the global network organization. This local description can also be leveraged to easily generate samples from the ensemble of networks with a given joint degree-onion distribution. We demonstrate the utility of the onion spectrum for understanding both static and dynamic properties on several standard graph models and on many real-world networks. Nature Publishing Group 2016-08-18 /pmc/articles/PMC4989159/ /pubmed/27535466 http://dx.doi.org/10.1038/srep31708 Text en Copyright © 2016, The Author(s) http://creativecommons.org/licenses/by/4.0/ This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/
spellingShingle Article
Hébert-Dufresne, Laurent
Grochow, Joshua A.
Allard, Antoine
Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
title Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
title_full Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
title_fullStr Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
title_full_unstemmed Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
title_short Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
title_sort multi-scale structure and topological anomaly detection via a new network statistic: the onion decomposition
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4989159/
https://www.ncbi.nlm.nih.gov/pubmed/27535466
http://dx.doi.org/10.1038/srep31708
work_keys_str_mv AT hebertdufresnelaurent multiscalestructureandtopologicalanomalydetectionviaanewnetworkstatistictheoniondecomposition
AT grochowjoshuaa multiscalestructureandtopologicalanomalydetectionviaanewnetworkstatistictheoniondecomposition
AT allardantoine multiscalestructureandtopologicalanomalydetectionviaanewnetworkstatistictheoniondecomposition