Strongly clustered random graphs via triadic closure: An exactly solvable model
arXiv:2311.05312 · doi:10.1103/PhysRevE.109.024306
Abstract
Triadic closure, the formation of a connection between two nodes in a network sharing a common neighbor, is considered a fundamental mechanism determining the clustered nature of many real-world topologies. In this work we define a static triadic closure (STC) model for clustered networks, whereby starting from an arbitrary fixed backbone network, each triad is closed independently with a given probability. Assuming a locally treelike backbone we derive exact expressions for the expected number of various small, loopy motifs (triangles, 4-loops, diamonds and 4-cliques) as a function of moments of the backbone degree distribution. In this way we determine how transitivity and its suitably defined generalizations for higher-order motifs depend on the heterogeneity of the original network, revealing the existence of transitions due to the interplay between topologically inequivalent triads in the network. Furthermore, under reasonable assumptions for the moments of the backbone network, we establish approximate relationships between motif densities, which we test in a large dataset of real-world networks. We find a good agreement, indicating that STC is a realistic mechanism for the generation of clustered networks, while remaining simple enough to be amenable to analytical treatment.
arXiv comment15 pages, 9 figures
References in corpus (25)
- Random graphs with arbitrary degree distributions and their applications
- Critical phenomena in complex networks
- Networks beyond pairwise interactions: structure and dynamics
- Growing Scale-Free Networks with Tunable Clustering
- Generation of uncorrelated random scale-free networks
- Random graphs with clustering
- Properties of highly clustered networks
- Emergence of a small world from local interactions: Modeling acquaintance networks
- Triadic closure as a basic generating mechanism of communities in complex networks
- Random graphs containing arbitrary distributions of subgraphs
- Percolation and Epidemic Thresholds in Clustered Networks
- Clustering in complex networks. I. General formalism
- Clustering in complex networks. II. Percolation properties
- Cumulative effects of triadic closure and homophily in social networks
- Distinct types of eigenvector localization in networks
- Solution for the properties of a clustered network
- Bond percolation on a class of clustered random networks
- Loops of any size and Hamilton cycles in random scale-free networks
- Triadic closure dynamics drives scaling-laws in social multiplex networks
- Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects
- Deciphering the global organization of clustering in real complex networks
- Disentangling homophily, community structure and triadic closure in networks
- Triadic closure in configuration models with unbounded degree fluctuations
- Extended-range percolation in complex networks
- Emergence of Clustering in an Acquaintance Model without Homophily