# Recursive Formula for Labeled Graph Enumeration

@article{Goyal2020RecursiveFF, title={Recursive Formula for Labeled Graph Enumeration}, author={Ravi Goyal and Victor De Gruttola}, journal={ArXiv}, year={2020}, volume={abs/2001.00084} }

This manuscript presents a general recursive formula to estimate the size of fibers associated with algebraic maps from graphs to summary statistics of importance for social network analysis, such as number of edges (graph density), degree sequence, degree distribution, mixing by nodal covariates, and degree mixing. That is, the formula estimates the number of labeled graphs that have given values for network properties. The proposed approach can be extended to additional network properties (e…

#### One Citation

Investigation of patient-sharing networks using a Bayesian network model selection approach for congruence class models.

- Medicine, MathematicsStatistics in medicine
- 2021

A Bayesian approach to conduct network model selection is presented for a general class of network models referred to as the congruence class models, and evidence in support of heterogeneity in sociality but not selective mixing by provider type or degree is found.

#### References

SHOWING 1-10 OF 17 REFERENCES

Goodness of fit for log-linear network models: dynamic Markov bases using hypergraphs

- Mathematics
- 2014

Social networks and other sparse data sets pose significant challenges for statistical inference, since many standard statistical methods for testing model/data fit are not applicable in such…

Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph

- Mathematics
- 2017

In this paper we relate a fundamental parameter of a random graph, its degree sequence, to a simple model of nearly independent binomial random variables. This confirms a conjecture made in 1997. As…

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

- Computer Science, MathematicsArXiv
- 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.

CONSISTENCY UNDER SAMPLING OF EXPONENTIAL RANDOM GRAPH MODELS.

- Mathematics, MedicineAnnals 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.

Sampling networks from their posterior predictive distribution

- Medicine, Computer ScienceNetwork Science
- 2014

This work provides detail needed to sample networks for the specific network properties of degree distribution, mixing frequency, and clustering, and demonstrates the methods to generate networks using simulated data and data from the National Longitudinal Study of Adolescent Health.

The Asymptotic Number of Labeled Graphs with Given Degree Sequences

- Computer Science, MathematicsJ. Comb. Theory, Ser. A
- 1978

Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: each row sum is specified and bounded, and a specified “sparse” set of entries must be zero.

A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs

- Mathematics, Computer ScienceEur. J. Comb.
- 1980

The method determines the asymptotic distribution of the number of short cycles in graphs with a given degree sequence, and gives analogous formulae for hypergraphs.

Networks: An Introduction

- Computer Science
- 2010

This book brings together for the first time the most important breakthroughs in each of these fields and presents them in a coherent fashion, highlighting the strong interconnections between work in different areas.

Effects of random rewiring on the degree correlation of scale-free networks

- Computer Science, MedicineScientific reports
- 2015

It is found that random and directional rewiring affect the topology of a scale-free network differently, even if the degree correlation of the rewired networks is the same.

Assortative mixing in networks.

- Computer Science, PhysicsPhysical review letters
- 2002

This work proposes a model of an assortatively mixed network and finds that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.