# A General Computational Approach for Counting Labeled Graphs
## 3 Methods
## 5 Application

In this section, we estimate the variation in degree mixing matrices consistent with degree distributions formed by the Barabasi-Albert (BA) model ([PERSON] and [PERSON], 2018). The BA model can be initiated with a small seed graph that grows by the addition of new vertices one at a time. Each new vertex forms a new edge with an existing vertex based on preferential attachment rules. Vertices and edges, once introduced, are never deleted. The BA model fixes the number of (undirected) edges connected to each new vertex. The BA model provides a mechanism to generate graphs with a fat-tailed degree distribution--specifically a power-law degree distribution--wherein the probability, \(P(k)\), that a vertex in the graph has degree \(k\), decays as a power-law \(P(k)\sim k^{-\gamma}\). Figure 1: **Comparison:** Log estimates the number of \(\delta\)-regular graphs for degrees from 1 to 10. The red bars depict estimates based on the recursive formula introduced in this paper; the blue bars are estimates based on [PERSON] et al. (2018). Each plot shows log estimates for graphs of size 1000, 5000, and 10,000. To calculate the variation in degree mixing matrices consistent with degree distributions formed by the BA model, we first estimate the number graphs consistent with a degree distribution associated with the BA. Second, we estimate the number of graphs consistent with a degree mixing matrix associated with a degree distribution from the BA model. Third, we estimate the number of distinct degree mixing matrices associated with a degree distribution generated from the BA model, which provides a metric for the variation of graphs generated by the BA model. For the first step, we generate 100 graphs using the BA model (\(n=5000\)), denoted as \(\{G_{1}^{BA},\ldots,G_{100}^{BA}\}\). Figure 2 shows density plots for the log estimates for \(|c_{\phi_{2}}(\phi_{2}(G_{i}^{BA}))|\) in the first panel. The average number of labeled graphs associated with a degree distribution generated from the BA model was estimated as \(1.26e16988\) (exponential of the mean of the first panel in Figure 2). Second, for each graph, we estimate \(|c_{\phi_{4}}(\phi_{4}(G_{i}^{BA}))|\). Figure 2 (second panel) shows density plots for the log estimates for \(|c_{\phi_{4}}(\phi_{4}(G_{i}^{BA}))|\). Figure 2 (third panel) shows a density plot for the log estimates for the number of distinct degree mixing matrices associated with a degree distribution generated from the BA model. The exponential of the mean gives an estimate of \(4.16e634\) distinct degree mixing matrices associated with a degree distribution generated from the BA model. ## 6 Discussion

This paper presents a general recursive formula to estimate the number of labeled graphs with specific values for graph properties of interest. We consider those with particular relevance for social network analysis: number of edges (graph density), degree sequence, degree distribution, classification mixing, and degree mixing. The proposed method can easily be extended to additional graph properties, including number of triangles (controlling for degree mixing), as well as to bipartite graphs; the formulas for Equation (2) are currently available. The proposed recursive formula differs from other available approaches for graph enumeration both in its overall approach and in the breadth

Figure 2: Barabási-Albert (BA) model: Density plots for the log estimates for \(|c_{\phi_{2}}(\phi_{2}(G_{i}^{BA}))|\) (first panel) [degree distribution], \(|c_{\phi_{4}}(\phi_{j}(G_{i}^{BA}))|\) (second panel) [degree mixing], and number of distinct degree mixing matrices associated with a degree distribution generated from the BA model. of graph properties that can be considered; it may be profitable to investigate the theoretical connections between the proposed method and other approaches.