Triadic closure preserves local patterns and boosts clustering in random graphs

Local Convergence of Triadic Closures of Sparse Random Graphs

Discrete Mathematics

Summary

Clustering shows how friends of friends often become friends too, which happens a lot in social networks. The authors study a process called triadic closure, where pairs of nodes with a shared neighbor get connected with some chance, based on their connections. They prove that if a sequence of graphs behaves a certain way locally, then their triadic closures behave similarly, keeping the local structure intact. They also show that even if the original graphs have low clustering, their triadic closures can have positive clustering. The theory applies to popular random graph models like Erdős-Rényi and preferential attachment.

What this means in practice

Authors

Himasish Talukdar

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.