Limiting distributions of triangle counts in linear preferential attachment models
Partha S. Dey, Grigory Terlov · 2026
Read Limiting distributions of triangle counts in linear preferential attachment models by Partha S. Dey, Grigory Terlov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28776.txt.
Introduction
Partha S. Dey and Grigory Terlov derive spread guesses for triangle counts in the linear rich-get-richer attachment model. The final distribution shifts phase from Gaussian to another odd shape, which they map in full. The long-run pattern is governed by the mix between the hidden random setting and the mean-field link effect. Their work also yields a smooth phase shift in the mean number of triads as the growth knob varies.
Catalog record
| CREATOR | Partha S. Dey, Grigory Terlov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108560 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.28776
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Limiting distributions of triangle counts in linear preferential attachment models Partha S. Dey, Grigory Terlov Abstract . We derive distributional approximations for the number of triangles in the linear preferential attachment model PAM n ( m , δ ) \mathrm{PAM}_{n}(m,\delta) , where m ⩾ 2 m\geqslant 2 and δ > − m \delta>-m , with explicit rates of convergence. The limiting distribution undergoes a phase transition from Gaussian to another nontrivial distribution, which we characterize explicitly. The asymptotic behavior is governed by the interplay between the hidden random environment and the mean-field interaction effect. In particular, our analysis also yields a continuous phase transition in the expected number of triangles as δ \delta varies. #1# 1. Introduction and main results In the study of random graphs and complex networks, the number of triangles plays a central role in quantifying local clustering and higher-order connectivity patterns. It provides insight into the structural properties and is closely tied to community formation and transitivity in real-world systems. For instance, the standard measure of clustering in a network, the clustering coefficient, is defined as the ratio of the number of triangles to the number of wedges (i.e., paths of length 2). Preferential attachment models (PAM), introduced by Barabási and Albert in 1999 [ 2 ] , are among the most studied classes of evolving random graphs. Their appeal lies in a simple “rich-get-richer” growth mechanism, where new vertices are more likely to attach to vertices of large degree. This generates scale-free degree sequences that typically exhibit power-law tails, consistent with observations across a range of networks, including citation graphs, the World Wide Web, and various social networks. At the same time, PAMs remain sufficiently tractable from the perspective of rigorous analysis, especially when the attachment function is linear. In this paper, we study a variant of the linear preferential attachment model \mathrm{PAM}_{n}(m,\delta) , where n\in\mathds{N} denotes the number of vertices. We refer the reader to [ 17 , Chapter 5] for a systematic overview of the most common variants. Since different variants of the model typically yield comparable large-scale (mean) behavior, the choice of the variant primarily affects which technical tools are available. On the other hand, it is not a priori clear that the same is true for distributional approximations. The variant considered in the present work is constructed recursively as follows: Initial data: m\in\mathds{N} and \delta>-m . \mathbf{n=2} : \mathrm{PAM}_{2}(m,\delta) consists of two vertices \{1,2\} with m edges between them. \mathbf{n=k} : Given \mathrm{PAM}_{k-1}(m,\delta) , the k -th vertex is added with m edges \{e_{k,\ell}\}_{\ell\in[m]} . The edges connect sequentially to vertices of \mathrm{PAM}_{k-1}(m,\delta) with probabilities proportional to an affine function of the current degree, which is updated after each new connection; in other words, for \ell\in[m-1] and v\in[k-1] , \pr(e_{k,\ell+1}\text{ connects to }v)=\frac{\deg^{(\ell)}_{k-1}(v)+\delta}{2m(k-2)+\ell+(k-1)\delta}, where \deg_{k-1}^{(\ell)}(v) denotes the degree of vertex v\in\mathrm{PAM}_{k-1}(m,\delta) after \ell edges from the k -th vertex have been connected to the graph. The advantage of this variant is that it admits an exchangeable representation via a hidden environment given by a family of independent Beta-distributed random variables, see Section 2.1 . For PAM {}_{n}(m,\delta) , the expected number of triangles is well understood [ 5 , 8 , 10 ] and is summarized below in Theorem 1.1 . The original results are stronger than what we state, as they also provide the constants in terms of m and \delta . We observe that some of the authors technically considered different variations of the model, but analogous results can be easily recovered for the model above; in fact, we will present a short proof of this theorem in Section 3 . Theorem 1.1 ( [ 5 , 8 , 10 ] ) . Let m\geqslant 2 be a fixed integer and \delta>-m be a fixed real number. Let T_{n} be the number of triangles in \mathrm{PAM}_{n}(m,\delta) . Then \displaystyle\E T_{n}\cong\begin{cases}\log n&\text{ if }\delta>0\\ (\log n)^{3}&\text{ if }\delta=0\\ n^{|\delta|/(2m+\delta)}\log n&\text{ if }\delta\in(-m,0).\end{cases} Here and throughout the paper, \cong denotes equality up to multiplying by some fixed constant that may depend on parameters of the model. In general, we use the big- O and small- o notation as in the usual definition, often replacing big- O with \lesssim for simplicity. 1.1. Main results Our first main result explains the nature of the phase transition in the mean behavior from Theorem 1.1 , by interpolating between different parameter regimes. To be precise, we consider a more general model constructed with the same steps as \mathrm{PAM}_{n} , but where the parameter \delta also depends on the current size of the system. Formal definition is given in Section 7 . Theorem 1.2 . Let m\geqslant 2 , c\in\mathbb{R} , \alpha>0 be fixed and \delta_{k}:=2mc\,(\log k)^{-\alpha} for k\geqslant 2. Let T_{n} be the number of triangles in \mathrm{PAM}_{n}(m,(\delta_{k})_{k\in[n]}) . Then \displaystyle\E T_{n}\cong\begin{cases}(\log n)^{1+2\alpha}&\text{ when }\alpha\in(0,1),c>0,\\ (\log n)^{3}&\text{ when }\alpha>1\text{ or }\alpha=1,c>-1,\\ (\log n)^{3}\log\log n&\text{ when }\alpha=1,c=-1,\\ (\log n)^{2-c}&\text{ when }\alpha=1,c<-1\\ (\log n)^{1+\alpha}e^{-\frac{c}{1-\alpha}(\log n)^{1-\alpha}}&\text{ when }\alpha\in(0,1),c<0.\end{cases} In particular, fixing \alpha=1 , the phase transition for \E T_{n} occurs at c=-1 . We believe that with techniques similar to ours, one can also show fluctuation phase transitions in the model. For example, in terms of fluctuations, fixing \alpha=1 , the transition should occur at c=1/2 , see open question 8.6 . Our second main result establishes distributional limits for the number of triangles in PAM (m,\delta) and gives explicit bounds on the rates of convergence. This addresses a question raised in [ 10 , page 10] . Similarly to the behavior of the mean given by Theorem 1.1 , there are three different regimes depending on the sign of \delta . In the case when \delta>0 , the limiting distribution is normal, and the analysis required for the proof is completely different from that in the remaining cases. To measure the rate of convergence, we will use the L^{1} -Wasserstein distance \textrm{d}_{\mathcal{W}} . For two random variables X and Y , it is defined by \textrm{d}_{\mathcal{W}}(X,Y):=\sup_{h:\,\mathrm{Lip}(h)\leqslant 1}\left|\E h(X)-\E h(Y)\right|. Let \psi_{1}\equiv 1 and \{\psi_{i}\}_{i\geqslant 2} be independent \mathrm{Beta}(m+\delta,(2m+\delta)(i-1)-m) random variables. Define the nonnegative sequence of real numbers (b_{i})_{i\geqslant 1} by (1) \displaystyle b_{i}:=\begin{cases}1&i=1\\ \left\|\psi_{i}\right\|_{2}^{2}\cdot\prod_{t=2}^{i}\left\|1-\psi_{t}\right\|_{2}^{-2}&i\geqslant 2.\end{cases} Observe that (\psi_{i},b_{i})_{i\geqslant 2} depend on the parameters m,\delta and define (2) \displaystyle s_{n}=\begin{cases}\sqrt{\log n},&\text{if }\delta>0,\\[4.30554pt] \frac{1}{4}(\log n)^{2},&\text{if }\delta=0,\\[4.30554pt] \left({m}/{|\delta|}-1\right)n^{|\delta|/(2m+\delta)}\log n,&\text{if }\delta\in(-m,0).\end{cases} For \delta\leqslant 0 , we interpret s_{n} as the expected number of triangles that contain the starting vertex 1 . Theorem 1.3 . Let m\geqslant 2 and \delta>-m be fixed. Let T_{n} be the number of triangles in \mathrm{PAM}_{n}(m,\delta) . We have \var(T_{n})\cong s_{n}^{2}. Moreover, there exists a constant \gamma=\gamma(m,\delta)\in(0,\infty) such that the following holds. (1) When \delta>0 , we have \displaystyle\textrm{d}_{\mathcal{W}}\left(\frac{T_{n}-\E T_{n}}{\gamma{s_{n}}},Z\right)\lesssim\frac{1}{\sqrt{\log n}}, where Z\sim\N(0,1) . (2) When \delta=0 , we have \displaystyle\textrm{d}_{\mathcal{W}}\left(\frac{T_{n}-\E T_{n}}{\gamma{s_{n}}},\sum_{i=1}^{\infty}b_{i}\left(\frac{\psi_{i}^{2}}{\left\|\psi_{i}\right\|_{2}^{2}}\prod_{j=i+1}^{\infty}\frac{(1-\psi_{j})^{2}}{\left\|1-\psi_{j}\right\|_{2}^{2}}-1\right)\right)\lesssim\frac{1}{\sqrt{\log n}}. (3) When \delta\in(-m,0) , we have \displaystyle\textrm{d}_{\mathcal{W}}\left(\frac{T_{n}}{\gamma s_{n}},\sum_{i=1}^{\infty}b_{i}\cdot\frac{\psi_{i}^{2}}{\left\|\psi_{i}\right\|_{2}^{2}}\prod_{j=i+1}^{\infty}\frac{(1-\psi_{j})^{2}}{\left\|1-\psi_{j}\right\|_{2}^{2}}\right)\lesssim\frac{1}{\sqrt{\log n}}. We present our interpretation of the limiting distribution in parts 2 and 3 alongside simulations in Subsection 8.1 . Remark 1.4 . The value of the constant \gamma is given by (3) \gamma=\begin{cases}\frac{m}{\delta}\sqrt{\frac{(m-1)(m+\delta)(m+\delta+1)}{2m+\delta}}&\text{ if }\delta>0,\\ \qquad m^{2}(m-1)&\text{ if }\delta\leqslant 0.\end{cases} Remark 1.5 (Optimality) . Since for \delta>0 the rate of convergence in Theorem 1.3 is of order 1/\sqrt{\var(T_{n})} , it is reasonable to expect it to be optimal, although it still requires establishing an