Local Convergence of Triadic Closures of Sparse Random Graphs
Abstract
Triadic closure is a natural mechanism for modeling the clustering phenomenon observed in many real-world networks. Given a possibly random undirected graph H, we consider pairs of non-adjacent vertices that have a common neighbor. Conditional on H, each such pair is joined by an edge independently and simultaneously, with a probability depending on the degrees of its endpoints and on the number of their common neighbors. The resulting graph is called a triadic closure of H. We study the effect of this operation on local convergence. More precisely, we prove that if a sequence of potentially random finite undirected graphs of ( Hn )n ∈ ℕ converges locally in probability to a rooted graph H*, then the corresponding sequence of triadic closures converges locally in probability to the same triadic closure of H*. As a consequence, we obtain a general limit theorem for the clustering coefficients of triadic closures. In particular, we show that the triadic closures can have a strictly positive limiting clustering coefficients even when the limiting clustering coefficients of the parent graph sequence is zero. Finally, we apply our results to several classical sparse random graph models including Erdős-Rényi, configuration, preferential attachment models and compute the limiting clustering coefficients of their triadic closures.
Related
BibTeX
@misc{talukdar2026local,
title = {{Local Convergence of Triadic Closures of Sparse Random Graphs}},
author = {Himasish Talukdar},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39535},
eprint = {2610.39535},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39535},
}
RIS
TY - UNPB
TI - Local Convergence of Triadic Closures of Sparse Random Graphs
AU - Himasish Talukdar
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39535
UR - https://arxiv.org/abs/2610.39535
AB - Triadic closure is a natural mechanism for modeling the clustering phenomenon observed in many real-world networks. Given a possibly random undirected graph H, we consider pairs of non-adjacent vertices that have a common neighbor. Conditional on H, each such pair is joined by an edge independently and simultaneously, with a probability depending on the degrees of its endpoints and on the number of their common neighbors. The resulting graph is called a triadic closure of H. We study the effect of this operation on local convergence. More precisely, we prove that if a sequence of potentially random finite undirected graphs of ( H_n )_n ∈ ℕ converges locally in probability to a rooted graph H^*, then the corresponding sequence of triadic closures converges locally in probability to the same triadic closure of H^*. As a consequence, we obtain a general limit theorem for the clustering coefficients of triadic closures. In particular, we show that the triadic closures can have a strictly positive limiting clustering coefficients even when the limiting clustering coefficients of the parent graph sequence is zero. Finally, we apply our results to several classical sparse random graph models including Erdős-Rényi, configuration, preferential attachment models and compute the limiting clustering coefficients of their triadic closures.
ER -