Source-linked AI summary
Exchangeable Random Networks
F. Bassetti, M. Cosentino Lagomarsino, S. Mandrá
TL;DR
The paper addresses the need for random graph models that are both practical null models and mathematically tractable. It develops exchangeable ensembles, derives degree-distribution laws, and studies structural observables and adjacency-matrix kernels. The framework can produce Poisson in-degree and power-law-tailed out-degree behavior in directed networks.
Problem
Random graph models need to support useful empirical-network null modeling while providing tractable results for relevant graph properties.
Source: §1 · pp. 1–2Method
Results
The ensembles yield Poisson limiting in-degree, mixed-Poisson limiting out-degree, and power-law-tailed out-degree distributions.
Source: §1 · p. 3Takeaways & Limitations
Exchangeable ensembles provide statistical null models and a flexible framework for theoretical investigations of complex networks.
Source: §1 · p. 2For subgraph counts, higher moments such as the variance are analytically possible in principle but are not straightforward to compute.
Source: §4.1 · p. 17
Abstract
from arXiv · showhide
We introduce and study a class of exchangeable random graph ensembles. They can be used as statistical null models for empirical networks, and as a tool for theoretical investigations. We provide general theorems that carachterize the degree distribution of the ensemble graphs, together with some features that are important for applications, such as subgraph distributions and kernel of the adjacency matrix. These results are used to compare to other models of simple and complex networks. A particular case of directed networks with power-law out--degree is studied in more detail, as an example of the flexibility of the model in applications.
1 Introduction
The paper introduces exchangeable random graph ensembles designed to be flexible for practical null-model use while remaining mathematically tractable. It derives degree-distribution results and studies subgraphs, connectivity, adjacency-matrix kernels, variants, and a directed power-law application.
Motivation and contribution
- Exchangeable degree correlations define a general random-graph ensemble suitable for statistical null models and theoretical exploration.The model targets flexible practical use, analytical tractability, and a unifying mathematical structure.Source: §1 · p. 2
- The ensemble supports analytical computation of finite-size and asymptotic observables while remaining fast and versatile computationally.Examples include commonly used large-network observables and prescribed degree-distribution properties rather than conservation of an observed graph’s degree sequence.Source: §1 · p. 2
Variants and application
- The paper presents directed variants and a detailed two-parameter ensemble, including a directed-network case with power-law out-degree.These variants illustrate the model’s flexibility for applications.Source: §1 · pp. 2–3
Degree distributions
- Its degree-distribution theory yields Poisson limiting in-degree, mixed-Poisson limiting out-degree, and power-law-tailed out-degree distributions.The power-law behavior arises through suitable mixtures of Poisson distributions.Source: §1 · p. 3
Graph structure
- The analysis also shows that the probability of graph disconnection tends to 1 as graph size diverges and studies subgraph counts.The paper gives results on mean numbers of subgraphs, roots, and leaves.Source: §1 · p. 3
Adjacency-matrix kernel
- A separate analysis addresses the dimension of the adjacency-matrix kernel as a Boolean optimization problem arising in statistical physics and theoretical computer science.This extends the ensemble’s application range beyond degree and subgraph observables.Source: §1 · p. 3
2 The Model
The model uses exchangeability to construct directed and undirected graph ensembles with separately controllable degree behavior. It includes partially, completely, and hierarchically exchangeable variants, with distribution choices determining ensemble characteristics.
2 The Model
- Rectangular m_n × n matrices accommodate settings where all nodes receive edges but only a fraction can send them, including power-law exponents at or below 2.The paper identifies this choice as necessary for such networks with diverging average degree.Source: §2 · p. 3
- Exchangeability preserves permutation symmetry while allowing dependence among edges, enabling distinct in- and out-degree distributions.The framework gives up total edge independence to retain maximal symmetry through exchangeability.Source: §2 · p. 3, §2.1 · p. 4
2.1 Partially Exchangeable Random Graphs
- Partially exchangeable graphs independently generate rows by sampling a bias and then Bernoulli entries, with π_n determining ensemble behavior.The transposed construction can interchange the roles of in- and out-degrees.Source: §2.1 · p. 4
- Choices of π_n include heavy-tailed degree ensembles and a directed Erdős–Rényi graph obtained from π_n(dθ) = δ_λ/n(dθ).The paper frames characterizing π_n choices that produce qualitatively different ensembles as a general problem.Source: §2.1 · p. 4
2.2 Completely exchangeable graphs
- Completely exchangeable graphs use one shared bias to generate every matrix entry, making all entries exchangeable.This variant differs from row-wise construction by drawing the bias once before tossing all matrix-entry coins.Source: §2.2 · p. 5
2.3 Hierarchical models
- Hierarchical models add a hierarchy of probability distributions for generating coin biases through a distribution λ_n and kernel π_n(·|α).The conditional kernel is defined on [0, 1] × R+ while λ_n is a probability measure on R+.Source: §2.3 · p. 5
3 Connectivities
This section characterizes connectivity-related extremes and degree limits in partially exchangeable graphs. It examines how the mixing law and heavy-tailed out-degree conditions shape limiting degree distributions and hub size.
3.1 In and out connectivity
- The model’s mean degrees are m_nµ_n for in-degree and nµ_n for out-degree, with nµ_n generally varying with n but approaching µ under condition (3).The degree variables differ structurally: out-degrees are independent sums of exchangeable Boolean variables, whereas in-degrees are dependent.Source: §3.1 · p. 6
- Proposition 3.1 shows that, under convergence of T_n=n˜θ_n, out-degree limits are Poisson mixtures while in-degree limits are simple Poisson.Convergence of T_n is necessary and sufficient for the Poisson-mixture limit of (S_n,j).Source: §3.1 · pp. 6–7
- Different mixing distributions produce distinct limits: exponential mixing gives a geometric out-degree law, while gamma mixing gives a negative-binomial law.The exponential example is explicitly an exponential mixture of Poisson distributions; the gamma generalization yields a negative-binomial distribution with parameter r.Source: §3.1 · p. 8
- Poisson mixing with exponential weights is insufficient for power laws, but suitable mixing distributions can generate heavy-tailed out-degree limits.The section gives examples involving generalized and Lerch-transcendent mixtures that produce heavy tails, demonstrating flexibility through the coin-bias distribution.Source: §3.1 · pp. 8–10
- The analysis reduces heavy-tail questions for out-degree distributions to identifying conditions on the mixing distribution F, whose properties transfer to the resulting Poisson mixture.The section notes that the model’s graph features depend on the chosen coin-bias distribution and recalls general structural properties of Poisson mixtures.Source: §3.1 · pp. 10–11
- The preceding connectivity discussion notes that degree-distribution properties inherit structural features of F, including monotonicity, log-convexity, and infinite divisibility.The text then turns to observables beyond degree distributions.Source: §3.1 · p. 11
3.2 The hub size
- The hub size is the maximum out-degree among the nodes, and its power-law regime admits an analytically tractable rescaled limit law.The analysis determines the normalizing sequence and limit function explicitly in some situations.Source: §3.2 · p. 12
- Under heavy-tailed out-degree assumptions, Proposition 3.3 characterizes the hub’s limiting behavior through explicit quantities g, b_n, and L when the required asymptotic expansion holds.The expansion has the form P{S_n,1 ≤ xb_n} = 1 − g(x)/m_n + o(1/m_n) for x ≤ L.Source: §3.2 · p. 12
- Fréchet-domain attraction yields an extreme-value limit e^(-c_ηx^-η) for suitably normalized maxima, but this condition alone does not ensure the hub has the correct order.A stronger requirement is therefore introduced to control the remainder term r_n.Source: §3.2 · p. 14
4 Some non-local features of the graphs
This section derives non-local graph statistics, including expected subgraph counts, roots and leaves, and connected-component behavior. Exchangeability enables analytic calculations, while connectedness depends on model parameters and can exhibit a giant component.
4.1 Subgraphs
- Exchangeability makes the mean number of subgraphs of a given shape analytically computable.The framework applies this approach to cycles, feedback loops, and feedforward loops, while variance calculations become cumbersome.Source: §4.1 · pp. 16–17
- Square matrices are the main setting because rectangular matrices require additional constraints on which nodes can send outgoing edges.The rectangular case is therefore more complicated in evaluating subgraph counts.Source: §4.1 · p. 16
4.2 Roots and leaves
- The expected numbers of roots and leaves are given explicitly through the model’s edge and degree probabilities.These quantities are defined by vertices with outgoing but no incoming edges, or incoming but no outgoing edges, excluding loops and isolated points.Source: §4.2 · p. 18
4.3 Connected components
- A giant component is important for using the ensemble as a null or positive model because many empirical networks contain a very large component.The paper notes that lacking this property can limit applications to real-world systems.Source: §4.3 · p. 18
- For the power-law example, simulations indicate a giant component for all parameter values, but the probability of a single connected component vanishes as n grows for β > 2 with square matrices.The existence of a giant component depends on the choice of π_n, and a general detailed analysis is left for future work.Source: §4.3 · p. 19
5 Threshold properties in the kernel of An
The paper studies threshold behavior in the kernel of the adjacency matrix through hypercycles and solutions of a random linear system over GF2. Exact mean-solution formulas yield threshold results, including exponential growth above the threshold and sub-exponential behavior at criticality.
5 Threshold properties in the kernel of An
- The central problem is whether the random linear system exhibits an abrupt threshold change as m_n and n diverge with n/m_n → γ ≤ 1.The kernel dimension is connected to the total number of hypercycles in the associated graph.Source: §5 · pp. 19–20
- An exact expression for the mean number of solutions provides a route to proving a threshold property for S(X_n).The same expression is presented as a first step toward a fuller characterization of the solution space.Source: §5 · p. 20
- When I_γ > (1/γ − 1) log(2), the mean number of hypercycles diverges exponentially in n.The asymptotic expression is E S(X_n) = (1 + o(1))(exp{n(I_γ − (1/γ − 1) log(2))}P_n^{-1}), with P_n at most polynomial.Source: §5 · p. 21
- At I_γ = (1/γ − 1) log(2), the mean number of hypercycles is sub-exponential rather than exponentially divergent.The paper states that for some b ≥ 0, E S(X_n)/n^b tends to zero as n grows.Source: §5 · p. 21
- Under the stated hypotheses, the threshold property is established, while a more exhaustive solution-space characterization is deferred.The proofs for this section are deferred to the Appendix.Source: §5 · pp. 20–21
6 Other Models
The paper briefly extends its calculations to completely exchangeable and hierarchical graph variants. The hierarchical construction can generate directed graphs with distinct power-law exponents for in- and out-degree distributions.
6.1 Completely exchangeable graphs
- Most previously discussed quantities, including subgraph, root, and leaf counts, remain analytically computable for completely exchangeable graphs.The paper states that these calculations proceed along the same lines as for the main model.Source: §6.1 · p. 22
- A proposition gives an asymptotic result for the completely exchangeable model when T_n converges in distribution.Source: §6.1 · p. 22
6.2 Hierarchical models
- The hierarchical variant can produce directed graphs with power-law-tailed in- and out-degree distributions having different exponents.The construction uses triangular matrices generated by the same algorithm.Source: §6.1 · p. 22, §6.2 · p. 22
- For γ > β > 2, the example yields Q*{S_n,1 = k} = c_1 k^-β(1 + o(1)) and Q*{Z_n,1 = k} = c_2 k^-γ(1 + o(1)).The limiting distribution for Z_n,1 is also identified through p_u,γ(k), with u = A(β − 1)/(β − 2).Source: §6.2 · pp. 22–23
7 A simple two parameters model
The two-parameter model is developed as a flexible null ensemble for directed networks, especially transcription-network-like graphs with Poissonian indegree and power-law outdegree. The section derives asymptotics for connectivity, motifs, roots and leaves, hubs, and GF2 linear systems.
7 A simple two parameters model
- The model can generate directed graphs with Poissonian indegree and approximately power-law outdegree, matching features motivating alternative null models for transcription networks.The paper uses this model to calculate the observables developed earlier.Source: §7 · p. 23
7.1 In and out connectivity
- The outdegree is asymptotically power-law distributed, while the indegree can be asymptotically Poisson distributed under suitable scaling of m_n.Different scalings of μ_n must be distinguished.Source: §7.1 · p. 24
- For β ≤ 2, obtaining an outdegree power-law with divergent mean heavily constrains the number of regulator nodes.The regulator nodes correspond to the rows of the adjacency matrix.Source: §7.1 · p. 24
7.2.2 Triangles
- The feedforward loop always dominates the feedback loop in the model, with stronger dominance for rectangular adjacency matrices.The ratio’s scaling is analyzed across parameter regimes, including a coefficient λ > 1.Source: §7.2.2 · p. 26
7.3 Roots and leaves
- The model gives asymptotic scaling for roots and leaves and can impose a specified scaling for the roots-to-leaves ratio of the null ensemble.In particular, E[L(G_n)] ∼ n is reported.Source: §7.3 · p. 27
7.4 The hub
- For β > 2, the paper states an explicit limit theorem for hub size under b_n = n^(1/(β−1)); separate scalings are given for β = 2 and 1 < β < 2.Source: §7.4 · p. 27
7.5 Random linear system in GF2
- For 1 < β < 2, there is a constant γ_c(β) associated with the threshold behavior of the random linear system in GF2.Source: §7.5 · p. 29
A Appendix
The appendix develops proofs using algebraic manipulations, convergence arguments, tail estimates, Tauberian theory, and adjacency-matrix linear systems.
A Appendix
- The proof of Lemma 3.2 rewrites expressions, sums over ai, and uses an expression independent of j when writing EN(Xn).Source: A Appendix · p. 31
- The appendix also studies adjacency matrices by counting solutions of linear systems over GF2.The matrices are introduced as m_n × n adjacency matrices, with columns and entries specified explicitly.Source: A Appendix · pp. 30–31
- The appendix applies large-deviation estimates and invokes external theorems to reduce Proposition 5.2 to finite-K bounds.The cited ingredients include a classical large-deviation estimate and Theorems 7.1 and 10.2 in.Source: A Appendix · pp. 30, 32
- Weak convergence, bounded continuity, and tightness are used to establish convergence and control tail probabilities.The argument uses weak convergence of T_M and a uniform tightness bound.Source: A Appendix · pp. 32–33
- Additional arguments establish a critical γ threshold and verify finiteness conditions for integrals and series involving γ and p_m.The proof identifies γ_c through the behavior of d x Θ_γ(x) and analyzes a Gamma-function series.Source: A Appendix · pp. 30, 33
- Karamata’s Tauberian theorem connects asymptotics of H(s) near zero with asymptotics of A(x) at infinity.For σ > 0 and slowly varying L, the stated equivalence uses the factor Γ(1 + σ).Source: A Appendix · p. 33