Statistical models for cores decomposition of an undirected random graph
Authors:
Preprint
Abstract
The $k$-core decomposition is a widely studied summary statistic that describes a graph's global connectivity structure. In this paper, we move beyond using $k$-core decomposition as a tool to summarize a graph and propose using $k$-core decomposition as a tool to model random graphs. We propose using the shell distribution vector, a way of summarizing the decomposition, as a sufficient statistic for a family of exponential random graph models. We study the properties and behavior of the model family, implement a Markov chain Monte Carlo algorithm for simulating graphs from the model, implement a direct sampler from the set of graphs with a given shell distribution, and explore the sampling distributions of some of the commonly used complementary statistics as good candidates for heuristic model fitting. These algorithms provide first fundamental steps necessary for solving the following problems: parameter estimation in this ERGM, extending the model to its Bayesian relative, and developing a rigorous methodology for testing goodness of fit of the model and model selection. The methods are applied to a synthetic network as well as the well-known Sampson monks dataset.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Searching for superspreaders of information in real-world social mediaScientific Reports, 2014
- Identifying and ranking influential spreaders in complex networks by neighborhood corenessPhysica A: Statistical Mechanics and its Applications, 2014
- Estimating and understanding exponential random graph modelsThe Annals of Statistics, 2013
- D-cores: measuring collaboration of directed graphs based on degeneracyKnowledge and Information Systems, 2012
- Instability, Sensitivity, and Degeneracy of Discrete Exponential FamiliesJournal of the American Statistical Association, 2011
- Random graphs with a given degree sequenceThe Annals of Applied Probability, 2011
- Bayesian inference for exponential random graph modelsSocial Networks, 2011
- On the geometry of discrete exponential families with application to exponential random graph modelsElectronic Journal of Statistics, 2009
- An introduction to exponential random graph (p*) models for social networksSocial Networks, 2007
- Peeling the yeast protein networkProteomics, 2005