# Statistical models for cores decomposition of an undirected random graph

@article{Karwa2014StatisticalMF, title={Statistical models for cores decomposition of an undirected random graph}, author={Vishesh Karwa and Michael J. Pelsmajer and Sonja Petrovic and Despina Stasi and Dane Wilburne}, journal={ArXiv}, year={2014}, volume={abs/1410.7357} }

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… Expand

#### Figures, Tables, and Topics from this paper

#### 16 Citations

Random Graphs with Prescribed K-Core Sequences: A New Null Model for Network Analysis

- Computer Science, Mathematics
- WWW
- 2021

This work establishes a new family of network null models that operate on the k-core decomposition, and provides the first efficient sampling algorithm to solve the following basic combinatorial problem: given a graph G, produce a random graph sampled nearly uniformly from among all graphs with the same sequence of core numbers as G. Expand

Random graphs with node and block effects: models, goodness-of-fit tests, and applications to biological networks

- Mathematics
- 2021

Many popular models from the networks literature can be viewed through a common lens. We describe it here and call the class of models log-linear ERGMs. It includes degree-based models, stochastic… Expand

A scalable graph generation algorithm to sample over a given shell distribution

- Computer Science
- 2020 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)
- 2020

This paper presents a scalable shared and distributed memory graph generator that, given a shell decomposition, generates a random graph that conforms to it. Expand

Modular decomposition of graphs and hierarchical modeling

- Mathematics, Computer Science
- ArXiv
- 2018

This work considers Gallai's graph Modular Decomposition theory for network analytics and proposes a model for random graphs based on this decomposition, establishing a well defined context for hierarchical modeling and providing a solid theoretical framework for probabilistic and statistical methods. Expand

DERGMs: Degeneracy-restricted exponential random graph models

- Mathematics, Computer Science
- ArXiv
- 2016

A new exponential family of models for random graphs that build on the standard ERGM framework is proposed, and a new parameter based on the graph-theoretic notion of degeneracy, a measure of sparsity whose value is low in real-worlds networks is introduced. Expand

Estimating Shell-Index in a Graph with Local Information

- Computer Science, Physics
- ArXiv
- 2018

This work proposes a method to estimate the shell-index of a node using its local information and proposes hill-climbing based approach to hit the top-ranked nodes in a small number of steps. Expand

A survey of discrete methods in (algebraic) statistics for networks

- Computer Science, Mathematics
- ArXiv
- 2015

An overview of open problems in this area of discrete mathematics from the point of view of a particular family of statistical models for networks called exponential random graph models, which are related to well-known concepts in commutative algebra and graph-theoretic concepts in computer science. Expand

Leveraging Structural Hierarchy for Scalable Network Comparison

- Computer Science
- DEXA
- 2016

It is established that probability distributions of coreness and intra/inter-shell edges are capable of characterizing different genres of networks and capturing finer structural differences between networks of the same genre. Expand

What are higher-order networks?

- Computer Science, Mathematics
- ArXiv
- 2021

The goals are to clarify (i) what higher-order networks are, (ii) why these are interesting objects of study, and (iii) how they can be used in applications. Expand

Cores, shell indices and the degeneracy of a graph limit

- Mathematics
- 2018

The $k$-core of a graph is the maximal subgraph in which every node has degree at least~$k$, the shell index of a node is the largest $k$ such that the $k$-core contains the node, and the degeneracy… Expand

#### References

SHOWING 1-10 OF 58 REFERENCES

New Specifications for Exponential Random Graph Models

- Mathematics
- 2006

The most promising class of statistical models for expressing structural properties of social networks observed at one moment in time is the class of exponential random graph models (ERGMs), also… Expand

Exploring biological network structure using exponential random graph models

- Mathematics, Computer Science
- Bioinform.
- 2007

The exponential random graph models are described and demonstrated to have utility in modeling the architecture of biological networks as a function of the prominence of local features and it is argued that the flexibility, in terms of the number of available local feature choices, and scalability, in Terms of the network sizes, make this approach ideal for statistical modeling of Biological networks. Expand

Markov Chain Monte Carlo Estimation of Exponential Random Graph Models

- Computer Science
- J. Soc. Struct.
- 2002

This paper is about estimating the parameters of the exponential random graph model using frequentist Markov chain Monte Carlo (MCMC) methods, based on the Robbins-Monro algorithm for approximating a solution to the likelihood equation. Expand

An introduction to exponential random graph (p*) models for social networks

- Mathematics, Computer Science
- Soc. Networks
- 2007

The homogeneous Markov random graph models of Frank and Strauss are not appropriate for many observed networks, whereas the new model specifications of Snijders et al. are more suitable for social networks. Expand

On the geometry of discrete exponential families with application to exponential random graph models

- Mathematics
- 2008

There has been an explosion of interest in statistical models for analyzing network data, and considerable interest in the class of exponential random graph (ERG) models, especially in connection… Expand

Inference in Curved Exponential Family Models for Networks

- Mathematics
- 2006

Network data arise in a wide variety of applications. Although descriptive statistics for networks abound in the literature, the science of fitting statistical models to complex network data is still… Expand

K-shell decomposition for dynamic complex networks

- Computer Science
- 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks
- 2010

This paper proposes two methods for ranking nodes, according to generalized k-shell indexes, and compares their ability to identify the most influential spreaders by emulating the diffusion of epidemics using both synthetic as well as real-world contact traces. Expand

A model of Internet topology using k-shell decomposition

- Computer Science, Physics
- Proceedings of the National Academy of Sciences
- 2007

This analysis uses information on the connectivity of the network shells to separate, in a unique (no parameters) way, the Internet into three subcomponents: a nucleus that is a small, very well connected globally distributed subgraph; a fractal subcomponent that is able to connect the bulk of the Internet without congesting the nucleus, with self-similar properties and critical exponents predicted from percolation theory. Expand

CONSISTENCY UNDER SAMPLING OF EXPONENTIAL RANDOM GRAPH MODELS.

- Mathematics, Medicine
- Annals of statistics
- 2013

It is shown that this apparently trivial condition is in fact violated by many popular and scientifically appealing models, and that satisfying it drastically limits ERGM's expressive power. Expand

K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases

- Mathematics, Computer Science
- Networks Heterog. Media
- 2008

It is found that the k-core analysis provides an interesting characterization of the fluctuations and incompleteness of maps as well as information helping to discriminate the original underlying structure. Expand