{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:46:57Z","timestamp":1760244417723,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institute of Health","doi-asserted-by":"publisher","award":["R01 AI-147441","R37 AI-51164"],"award-info":[{"award-number":["R01 AI-147441","R37 AI-51164"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/a16010016","type":"journal-article","created":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T02:55:07Z","timestamp":1672109707000},"page":"16","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A General Computational Approach for Counting Labeled Graphs"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0358-2435","authenticated-orcid":false,"given":"Ravi","family":"Goyal","sequence":"first","affiliation":[{"name":"Division of Infectious Diseases and Global Public Health, University of California San Diego, La Jolla, CA 92093, USA"}]},{"given":"Victor","family":"De Gruttola","sequence":"additional","affiliation":[{"name":"Department of Biostatistics, Harvard T.H. Chan School of Public Health, Boston, MA 02115, USA"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,27]]},"reference":[{"key":"ref_1","unstructured":"Harary, F., and Palmer, E.M. (2014). Graphical Enumeration, Elsevier."},{"key":"ref_2","first-page":"1","article-title":"Bridging the gap between graphs and networks","volume":"3","author":"Battiston","year":"2020","journal-title":"Commun. Phys."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1735","DOI":"10.1093\/cid\/ciab037","article-title":"Evaluation of SARS-CoV-2 transmission mitigation strategies on a university campus using an agent-based network model","volume":"73","author":"Goyal","year":"2021","journal-title":"Clin. Infect. Dis."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.ijid.2021.10.008","article-title":"Examining sars-cov-2 interventions in residential colleges using an empirical network","volume":"113","author":"Hambridge","year":"2021","journal-title":"Int. J. Infect. Dis."},{"key":"ref_5","unstructured":"Lucatero, C.R. (2019). Combinatorial Enumeration of Graphs. Probability, Combinatorics and Control, IntechOpen."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1112\/jlms\/s1-34.4.417","article-title":"The enumeration of locally restricted graphs (I)","volume":"1","author":"Read","year":"1959","journal-title":"J. Lond. Math. Soc."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/0097-3165(78)90059-6","article-title":"The asymptotic number of labeled graphs with given degree sequences","volume":"24","author":"Bender","year":"1978","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","article-title":"A probabilistic proof of an asymptotic formula for the number of labelled regular graphs","volume":"1","year":"1980","journal-title":"Eur. J. Combin."},{"key":"ref_9","unstructured":"Liebenau, A., and Wormald, N. (2017). Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph. arXiv."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of Scaling in Random Networks","volume":"286","author":"Barabasi","year":"1999","journal-title":"Science"},{"key":"ref_11","first-page":"260","article-title":"A survey of discrete methods in (algebraic) statistics for networks","volume":"685","author":"Petrovic","year":"2017","journal-title":"Algebr. Geom. Methods Discret. Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1214\/12-AOS1044","article-title":"Consistency under sampling of exponential random graph models","volume":"41","author":"Shalizi","year":"2013","journal-title":"Ann. Stat."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1017\/nws.2014.2","article-title":"Sampling networks from their posterior predictive distribution","volume":"2","author":"Goyal","year":"2014","journal-title":"Netw. Sci."},{"key":"ref_14","first-page":"496","article-title":"On realizability of a set of integers as degrees of the vertices of a linear graph","volume":"10","author":"Hakimi","year":"1962","journal-title":"J. SIAM"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"477","DOI":"10.21136\/CPM.1955.108220","article-title":"A remark on the existence of Finite graphs","volume":"80","author":"Havel","year":"1955","journal-title":"\u010casopis Pest. Mat."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"208701","DOI":"10.1103\/PhysRevLett.89.208701","article-title":"Assortative mixing in networks","volume":"89","author":"Newman","year":"2002","journal-title":"Phys. Rev. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1002\/sim.7393","article-title":"Inference on network statistics by restricting to the network space: Applications to sexual history data","volume":"37","author":"Goyal","year":"2018","journal-title":"Stat. Med."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Sensarma, D., and Sen Sarma, S. (2019). Role of graphic integer sequence in the determination of graph integrity. Mathematics, 7.","DOI":"10.3390\/math7030261"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1177\/17407745221111818","article-title":"Network methods and design of randomized trials: Application to investigation of COVID-19 vaccination boosters","volume":"19","author":"DeGruttola","year":"2022","journal-title":"Clin. Trials"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/16\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:52:16Z","timestamp":1760147536000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/1\/16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,27]]},"references-count":19,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["a16010016"],"URL":"https:\/\/doi.org\/10.3390\/a16010016","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,12,27]]}}}