Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
Open Access
- 18 August 2016
- journal article
- research article
- Published by Springer Nature in Scientific Reports
- Vol. 6 (1) , 31708
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 theonion decomposition, which refines thek-core decomposition, a standard network fingerprinting method. The onion spectrum is exactly as easy to compute as thek-cores: It is based on the stages at which each vertex gets removed from a graph in the standard algorithm for computing thek-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 thek-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.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Ak-shell decomposition method for weighted networksNew Journal of Physics, 2012
- Communities, modules and large-scale structure in networksNature Physics, 2011
- Community detection in graphsPhysics Reports, 2010
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined ClustersInternet Mathematics, 2009
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Why social networks are different from other types of networksPhysical Review E, 2003
- Universal Behavior of Load Distribution in Scale-Free NetworksPhysical Review Letters, 2001
- Birds of a Feather: Homophily in Social NetworksAnnual Review of Sociology, 2001
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- Network structure and minimum degreeSocial Networks, 1983