CS Paper Radar

Local Convergence of Triadic Closures of Sparse Random Graphs

Himasish Talukdar

cs.DM math.PRmath-phmath.CO ·submitted 2026-10-29 07:33 UTC · v1
theory

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 $\left( H_n \right)_{n \in \mathbb{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.

Comment
46 pages, 4 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Exponential random graph models with soft clique constraints

cs.AI math.COmath.PR ·2026-08-31 ·Yasmin Tousinejad, Vera Koponen
theory similarity 0.61
Abstract · 58 pages, 1 figure

Let $r\geq3$ be fixed, and let $\mathbf{G}_n$ be the set of all simple graphs with vertex set $[n]=\{1,\ldots,n\}$. We consider an exponential random graph model which gives higher probability to $G \in \mathbf{G}_n$ than to $H \in \mathbf{G}_n$ if $G$ has fewer $r$-cliques than $H$. But all graphs in $\mathbf{G}_n$ have positive probability. The degree to which graphs with fewer $r$-cliques are given higher probability is determined by a positive weight $w$. We prove that, asymptotically almost surely as $n \to \infty$, a random graph from $\mathbf{G}_n$ has a vertex partition into $r-1$ parts of roughly equal size, the density of edges between the parts is close to $1/2$, and for every $\varepsilon > 0$ the density of edges within any part is less than $\varepsilon$. The asymptotic structural properties are independent of the weight $w$ as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight.

0.42

Correlation Clustering with Random Partial Information

cs.DS cs.LG ·2026-08-17 ·Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari
theory similarity 0.60
Abstract · 17 pages, 5 figures, 6 tables

Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.

0.26

Near linear mixing of random-cluster Glauber dynamics on random regular graphs

cs.DS math.PRmath-ph ·2026-11-04 ·Zhangsong Li
similarity 0.59
Abstract · 37 pages

We study the random-cluster model on locally treelike graphs at low temperatures. This is a model of dependent percolation parametrized by an edge probability $p \in (0,1)$ and a clustering weight $q \in [1,\infty)$, generalizing independent Bernoulli percolation ($q=1$) and closely related to the classical ferromagnetic Ising and Potts spin systems at integer $q$. For $q>2$, at parameter $p$ below the tree uniqueness threshold $p_{\mathsf u}(q,d)$, it is expected that sampling is easy and local Markov chains mix rapidly on all graphs with degree bounded by $d$. On typical graphs, the same is predicted at $p>p_{\mathsf s}(q,d)$, where $p_{\mathsf s}(q,d)$ is a second uniqueness transition point on the $d$-regular wired tree. Our result confirms this prediction for random regular graphs, showing that the random-cluster Glauber dynamics mix in time $O(n^{1+o(1)})$ on a random $d$-regular graph for all fixed $q>2$ and $p>p_{\mathsf s}$. For comparison, the best prior sampling results for these models that held for all $p>p_{\mathsf s}$ required $q\gtrsim \log d$ \cite{BGPZ26}. The key difficulty is that simply utilizing the contraction of cavity messages on $d$-regular trees does not suffice to cover the entire regime $q>2$. To address this issue, motivated by \cite{LS26}, we develop a careful bootstrap argument to show the shrinkage of disagreement under grand coupling. The core ideas of the proof were generated using GPT-6 and the Pharos system; the proof was then refined and simplified by the author.

0.10

Rotating Walks, Derandomized Squares, and Permutation Conjugated Walks

cs.DM math.COmath.PR ·2026-11-10 ·Vedat Levi Alev, Shravas Rao
theory similarity 0.58
Abstract

Using the recent strong convergence results of Bordenave and Collins (Annals of Mathematics) and Chen et al. (Annals of Mathematics), we study the average case behavior of rotating random walks of Cohen and Maor (STOC 2023) and the derandomized square construction of Rozenman and Vadhan (RANDOM 2005). Concretely, we prove a conjecture of Cohen et al. (ITCS 2025) regarding the average case behavior of derandomized squaring for random graphs and show that the existential bounds of Cohen and Maor for their rotating random walk construction hold with high-probability for random graphs. Using the results of O'Donnell and Wu (FOCS 2020), we can in polynomial time construct a family of graphs and rotations which almost saturate the bounds of Cohen and Maor, and meet the bounds conjectured by Cohen et al. for all vertex-transitive auxiliary graphs of fixed degree in the derandomized square. Finally, we study independent random permutation conjugates of deterministic regular graph adjacency matrices. We prove quantitative weak convergence to freely independent tree adjacency operators when the degrees are fixed and the girths tend to infinity. Separately, a covering argument gives deterministic spectral lower bounds for polynomials with non-negative coefficients, recovering the lower bound of Cohen et al. for rotating walks.

0.19

Parameterized Complexity of Connected Network Microaggregation: The Role of Cluster Size

cs.DS ·2026-08-28 ·Ajinkya Gaikwad, Dušan Knop, Tomáš Valla
theory similarity 0.58
Abstract

Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admitting a center within bounded distance. We study the parameterized complexity of the \emph{unweighted Connected Network Microaggregation} problem, focusing on structural parameters and natural clustering parameters such as the distance bound $d$ and cluster size gap $u-\ell$. We show that, unlike the weighted variant, the unweighted connected problem is fixed-parameter tractable when parameterized by neighborhood diversity, and hence by vertex cover. In contrast, it remains $\mathrm{W[1]}$-hard for more general structural parameters, including vertex deletion to paths, stars, and cliques. These hardness results hold even for every $d\ge 2$ and any fixed gap $u-\ell$, showing that these clustering parameters do not overcome the structural hardness. We further show that adding the cluster size bound $u$ restores tractability for structural parameters such as treewidth and cluster vertex deletion. Moreover, $u$ is essential: the problem remains $\mathrm{W[1]}$-hard when these structural parameters are considered alone. For kernelization, we prove that the problem has no polynomial kernel parameterized by vertex cover unless $\mathrm{coNP}\subseteq\mathrm{NP/poly}$, even when the distance constraint is vacuous. Adding $u$ yields a polynomial kernel for vertex cover, while kernelization remains unlikely for more general structural parameters even when combined with $u$. Finally, we show that the problem is NP-hard on graphs of bounded clique-width.

0.24

Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs

cs.DM math.PRmath.CO ·2026-09-11 ·Dávid Ferenczi, Alexander Grigoriev
theory similarity 0.57
Abstract · 18 pages, 1 figure

Finding large lattice subgraphs in sparse Erdős--Rényi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densities substantially larger than the grid-emergence scale. In this paper we exploit the specific geometry of the square grid. We introduce the Quarantined Local Search, a three-phase local algorithm that separates the construction of an initial boundary from the later corner-closure process and controls adaptive negative exposure through bounded pair-test histories. We prove that, for every fixed $δ\in (0,1)$, there exists $C_δ>0$ such that the algorithm embeds a $k\times k$ square grid with $k^2\le (1-δ)n$ in $G(n,p)$ with high probability whenever $p\ge C_δ\sqrt{\ln k/n}$. Thus, for $k^2=Θ(n)$, a density of order $\sqrt{\log n/n}$ is sufficient, a factor of order $\sqrt{\log n}$ above the corresponding $n^{-1/2}$ emergence scale.

0.15

Maximum edge overlap between independent random regular graphs

cs.DM math.COmath.PR ·2026-10-30 ·Andrea D'Ascenzo, Riccardo Michielan
theoryhot direction similarity 0.57
Abstract

Optimising the vertex correspondence can substantially increase the number of edges shared by two independent realisations of the same random graph. We quantify this phenomenon for uniformly random $d$-regular graphs and derive corresponding results for their edge-based graph edit distance. For every fixed $d\geq 3$, we show that the maximum overlap is $n+Θ_{\mathbb P}(n/\log n)$, where the leading term $n$ arises from Hamiltonicity, while the surplus captures the optimal order of the excess beyond it. We establish explicit upper and lower bounds on the surplus. The upper bound is obtained by counting common cores of minimum degree at least two, while the lower bound is established using spanning factors consisting of cycles of the same logarithmic length. For the special case $d=2$, we show that the maximum overlap is $n-(1+o_{\mathbb P}(1))\log n$. The additional overlap achievable is also studied by rotating aligned Hamilton cycles, using a contiguity argument. As a by-product, we determine the asymptotic maximum overlap between unions of independent random perfect matchings under cyclic shifts.

0.35

On the self-intersection time of non-backtracking random walks

cs.DS math.PRmath.CO ·2026-08-10 ·Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen, Mark Jerrum, Gabor Pete +2 more
theory similarity 0.57
Abstract

We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed $Δ\geq 3$ we show that the expected self-intersection time is $O(\sqrt{n} \log n)$ on $n$-vertex graphs with minimum degree at least $3$ and maximum degree at most $Δ$. For regular graphs with a uniform spectral gap, we improve this to $O(\sqrt{n})$. We also show an $Ω(\sqrt{n})$ lower bound on a class of regular expanders. Our upper bound on the expected self-intersection time implies an improved mixing time bound on Glauber dynamics for the Ising model on $Δ$-regular graphs at the tree uniqueness threshold.

0.40