A General Computational Approach for Counting Labeled Graphs
Open Access
- 27 December 2022
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 16 (1) , 16
Abstract
This paper presents a general recursive formula to estimate the number of labeled graphs as well as details to evaluate the formula for the following graph properties: number of edges (graph density), degree sequence, degree distribution, classification mixing, and degree mixing, i.e., the formula estimates the number of labeled graphs that have given values for graph properties. The proposed approach can be extended to additional graph properties (e.g., number of triangles) as well as properties of bipartite graphs. For special settings in which formulas exist from previous research, simulation studies demonstrate the validity of the proposed approach. In addition, we demonstrate how our approach can be used to quantify the level of variability in values of a graph property in the subset of graphs that hold a specified value of a different graph property (or properties) constant.Keywords
Funding Information
- National Institutes of Health (R01 AI-147441, R37 AI-51164)
This publication has 18 references indexed in Scilit:
- Role of Graphic Integer Sequence in the Determination of Graph IntegrityMathematics, 2019
- Inference on network statistics by restricting to the network space: applications to sexual history dataStatistics in Medicine, 2017
- Sampling networks from their posterior predictive distributionNetwork Science, 2014
- Consistency under sampling of exponential random graph modelsThe Annals of Statistics, 2013
- Assortative Mixing in NetworksPhysical Review Letters, 2002
- Emergence of Scaling in Random NetworksScience, 1999
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980
- The asymptotic number of labeled graphs with given degree sequencesJournal of Combinatorial Theory, Series A, 1978
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. IJournal of the Society for Industrial and Applied Mathematics, 1962
- The Enumeration of Locally Restricted Graphs (I)Journal of the London Mathematical Society, 1959