Source-linked AI summary
Random graphs with clustering
M. E. J. Newman
TL;DR
The paper addresses the difficulty of building plausible, analytically tractable random-graph models with clustering. It generalizes the configuration model by separately specifying single edges and triangles, then derives exact results for connectivity, giant components, and percolation.
Problem
Analytic modeling of clustered networks has remained difficult, limiting development of a comprehensive theory despite progress for degree distributions and correlations.
Method
The model generalizes the configuration model by specifying each vertex’s numbers of single edges and triangles, then uniformly matching edge stubs and triangle corners.
Results
The generalized model permits exact formulas for component sizes, giant-component formation and size, and percolation properties in clustered networks.
Takeaways & Limitations
The model provides an unbiased ensemble of clustered networks and a basis for studying effects of clustering on epidemics, resilience, and network dynamics.
Abstract
from arXiv · showhide
We offer a solution to a long-standing problem in the physics of networks, the creation of a plausible, solvable model of a network that displays clustering or transitivity -- the propensity for two neighbors of a network node also to be neighbors of one another. We show how standard random graph models can be generalized to incorporate clustering and give exact solutions for various properties of the resulting networks, including sizes of network components, size of the giant component if there is one, position of the phase transition at which the giant component forms, and position of the phase transition for percolation on the network.