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

ABSTRACT: 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 combin

SUBMITTER: Hebert-Dufresne L 

PROVIDER: S-EPMC4989159 | biostudies-literature | 2016 Aug

REPOSITORIES: biostudies-literature