Multi-Scale Structure and Topological Anomaly Detection via a New Network Statistic: The Onion Decomposition

Multi-Scale Structure and Topological Anomaly Detection via a New Network Statistic: The Onion Decomposition. Hébert-Dufresne, L., Grochow, J. A., & Allard, A.

Paper doi abstract bibtex

We introduce a new network statistic that measures diverse structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and easy to interpret 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. But 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 of the whole network as well as of each k-core. 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.

@article{hebert-dufresneMultiscaleStructureTopological2016,
  archivePrefix = {arXiv},
  eprinttype = {arxiv},
  eprint = {1510.08542},
  title = {Multi-Scale Structure and Topological Anomaly Detection via a New Network Statistic: {{The}} Onion Decomposition},
  volume = {6},
  issn = {2045-2322},
  url = {http://arxiv.org/abs/1510.08542},
  doi = {10.1038/srep31708},
  shorttitle = {Multi-Scale Structure and Topological Anomaly Detection via a New Network Statistic},
  abstract = {We introduce a new network statistic that measures diverse structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and easy to interpret 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. But 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 of the whole network as well as of each k-core. 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.},
  number = {1},
  journaltitle = {Scientific Reports},
  urldate = {2019-01-30},
  date = {2016-10},
  keywords = {Physics - Physics and Society,Computer Science - Social and Information Networks,Condensed Matter - Disordered Systems and Neural Networks,Computer Science - Discrete Mathematics,Mathematics - Combinatorics},
  author = {Hébert-Dufresne, Laurent and Grochow, Joshua A. and Allard, Antoine},
  file = {/home/dimitri/Nextcloud/Zotero/storage/V6WP4EGA/Hébert-Dufresne et al. - 2016 - Multi-scale structure and topological anomaly dete.pdf;/home/dimitri/Nextcloud/Zotero/storage/UWCVXDE4/1510.html}
}

Downloads: 0

{"_id":"ta2RKS6dzg8CdSSPf","bibbaseid":"hbertdufresne-grochow-allard-multiscalestructureandtopologicalanomalydetectionviaanewnetworkstatistictheoniondecomposition","authorIDs":[],"author_short":["Hébert-Dufresne, L.","Grochow, J. A.","Allard, A."],"bibdata":{"bibtype":"article","type":"article","archiveprefix":"arXiv","eprinttype":"arxiv","eprint":"1510.08542","title":"Multi-Scale Structure and Topological Anomaly Detection via a New Network Statistic: The Onion Decomposition","volume":"6","issn":"2045-2322","url":"http://arxiv.org/abs/1510.08542","doi":"10.1038/srep31708","shorttitle":"Multi-Scale Structure and Topological Anomaly Detection via a New Network Statistic","abstract":"We introduce a new network statistic that measures diverse structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and easy to interpret 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. But 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 of the whole network as well as of each k-core. 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.","number":"1","journaltitle":"Scientific Reports","urldate":"2019-01-30","date":"2016-10","keywords":"Physics - Physics and Society,Computer Science - Social and Information Networks,Condensed Matter - Disordered Systems and Neural Networks,Computer Science - Discrete Mathematics,Mathematics - Combinatorics","author":[{"propositions":[],"lastnames":["Hébert-Dufresne"],"firstnames":["Laurent"],"suffixes":[]},{"propositions":[],"lastnames":["Grochow"],"firstnames":["Joshua","A."],"suffixes":[]},{"propositions":[],"lastnames":["Allard"],"firstnames":["Antoine"],"suffixes":[]}],"file":"/home/dimitri/Nextcloud/Zotero/storage/V6WP4EGA/Hébert-Dufresne et al. - 2016 - Multi-scale structure and topological anomaly dete.pdf;/home/dimitri/Nextcloud/Zotero/storage/UWCVXDE4/1510.html","bibtex":"@article{hebert-dufresneMultiscaleStructureTopological2016,\n archivePrefix = {arXiv},\n eprinttype = {arxiv},\n eprint = {1510.08542},\n title = {Multi-Scale Structure and Topological Anomaly Detection via a New Network Statistic: {{The}} Onion Decomposition},\n volume = {6},\n issn = {2045-2322},\n url = {http://arxiv.org/abs/1510.08542},\n doi = {10.1038/srep31708},\n shorttitle = {Multi-Scale Structure and Topological Anomaly Detection via a New Network Statistic},\n abstract = {We introduce a new network statistic that measures diverse structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and easy to interpret 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. But 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 of the whole network as well as of each k-core. 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.},\n number = {1},\n journaltitle = {Scientific Reports},\n urldate = {2019-01-30},\n date = {2016-10},\n keywords = {Physics - Physics and Society,Computer Science - Social and Information Networks,Condensed Matter - Disordered Systems and Neural Networks,Computer Science - Discrete Mathematics,Mathematics - Combinatorics},\n author = {Hébert-Dufresne, Laurent and Grochow, Joshua A. and Allard, Antoine},\n file = {/home/dimitri/Nextcloud/Zotero/storage/V6WP4EGA/Hébert-Dufresne et al. - 2016 - Multi-scale structure and topological anomaly dete.pdf;/home/dimitri/Nextcloud/Zotero/storage/UWCVXDE4/1510.html}\n}\n\n","author_short":["Hébert-Dufresne, L.","Grochow, J. A.","Allard, A."],"key":"hebert-dufresneMultiscaleStructureTopological2016","id":"hebert-dufresneMultiscaleStructureTopological2016","bibbaseid":"hbertdufresne-grochow-allard-multiscalestructureandtopologicalanomalydetectionviaanewnetworkstatistictheoniondecomposition","role":"author","urls":{"Paper":"http://arxiv.org/abs/1510.08542"},"keyword":["Physics - Physics and Society","Computer Science - Social and Information Networks","Condensed Matter - Disordered Systems and Neural Networks","Computer Science - Discrete Mathematics","Mathematics - Combinatorics"],"downloads":0},"bibtype":"article","biburl":"https://raw.githubusercontent.com/dlozeve/newblog/master/bib/all.bib","creationDate":"2020-01-08T20:39:39.241Z","downloads":0,"keywords":["physics - physics and society","computer science - social and information networks","condensed matter - disordered systems and neural networks","computer science - discrete mathematics","mathematics - combinatorics"],"search_terms":["multi","scale","structure","topological","anomaly","detection","via","new","network","statistic","onion","decomposition","hébert-dufresne","grochow","allard"],"title":"Multi-Scale Structure and Topological Anomaly Detection via a New Network Statistic: The Onion Decomposition","year":null,"dataSources":["3XqdvqRE7zuX4cm8m"]}