Abstract
We initiate the study of local topology of random graphs. The high level goal is to characterize local "motifs" in graphs. In this paper, we consider what we call the layer-$r$ subgraphs for an input graph $G = (V,E)$: Specifically, the layer-$r$ subgraph at vertex $u \in V$, denoted by $G_{u; r}$, is the induced subgraph of $G$ over vertex set $\Delta_{u}^{r}:= \left\{v \in V: d_G(u,v) = r \right\}$, where $d_G$ is shortest-path distance in $G$. Viewing a graph as a 1-dimensional simplicial complex, we then aim to study the $1$st Betti number of such subgraphs. Our main result is that the $1$st Betti number of layer-$1$ subgraphs in Erd\H{o}s--R'enyi random graphs $G(n,p)$ satisfies a central limit theorem.
Introduction
While the global topological properties of random graphs—such as connectivity, clique numbers, and global homology—have been rigorously studied since the mid-20th century, the local topology of these networks remains largely unexplored. Understanding local structural "motifs" is essential for characterizing the architecture of complex networks.
This research bridges the gap between classical random graph theory and modern Topological Data Analysis (TDA). We focus on the topological features of rooted $k$-neighborhood subgraphs, specifically the "layer-1" subgraph consisting of vertices exactly one hop away from a chosen root node. By treating these subgraphs as 1-dimensional simplicial complexes, we can quantify their complexity using the 1st Betti number, which counts the number of independent cycles (or "holes") within the local neighborhood.
Methodology
Mathematical Framework
We consider Erdős–Rényi random graphs $G(n, p)$, where $n$ is the number of vertices and $p$ is the edge probability. For a randomly selected vertex $u$, the layer-1 subgraph $G_{u;1}$ is the induced subgraph of its immediate neighbors. The primary random variable of interest is $C^{(1)}_{n,p}$, representing the 1st Betti number of this subgraph.
Proof Techniques
To establish a Central Limit Theorem (CLT) for the 1st Betti number, we utilize several probabilistic and combinatorial tools:
- Euler Characteristic Formula: We relate the 1st Betti number ($\beta_1$) to the 0th Betti number ($\beta_0$, the number of connected components) and the counts of vertices ($V$) and edges ($E$) in the subgraph: $\chi = \beta_0 - \beta_1 = V - E$.
- Stein’s Method: We apply Stein's method for normal approximation on sums of dissociated random variables. This allows us to prove that the difference between the number of edges and vertices in the layer-1 subgraph approaches a normal distribution as $n$ increases.
- Concentration Inequalities: Using Chernoff bounds, we demonstrate that when $p \gg n^{-1/2}$, the layer-1 subgraph is connected with high probability. In this regime, $\beta_0 = 1$, allowing us to isolate the behavior of $\beta_1$ through the vertex and edge counts alone.
Key Results
Central Limit Theorem for Local Topology
The primary contribution of this work is Theorem 1.1, which rigorously proves that if the edge probability $p$ satisfies $n^{-1/2} \ll p < 1$, the normalized 1st Betti number of a layer-1 subgraph converges weakly to a standard normal distribution $\mathcal{N}(0, 1)$. Furthermore, we establish that the total variation distance between the normalized Betti number and the standard normal distribution vanishes as $n \to \infty$.
Bridge to Persistent Homology
Beyond pure graph theory, these results have implications for TDA. The 1st Betti number of these layer subgraphs corresponds to the multiplicity of specific points in 1-dimensional extended persistence diagrams induced by a distance-to-root function. This provides a theoretical foundation for using Betti numbers as local descriptors in topological feature engineering.
Empirical Observations and Future Work
While our theoretical proofs are confined to layer-1 subgraphs, we conducted synthetic simulations on Erdős–Rényi graphs ($G(1000, p)$ and $G(10000, p)$) using D'Agostino-Pearson normality tests. These simulations suggest that the statistical predictability of local topology may extend further:
- Layer-$k$ Subgraphs: Empirical evidence suggests that for layer-2 and layer-3 subgraphs, there exist disjoint ranges of $p$ where a CLT might still hold, though the mathematical complexity of these higher-order layers is significantly greater.
- Graph-Wide Distributions: We conjecture that the distribution of $\beta_{1,d}$—the count of all vertices in a graph whose layer-1 subgraph has exactly $d$ cycles—also follows a normal distribution for sufficiently large $p$.
This work provides a first step toward a complete statistical characterization of the local topological motifs that define random networks.
Summary updated