Random graphs with clustering

Abstract

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.

5 pages, 2 figures

References in corpus (15)

• Assortative mixing in networks
• Hierarchical organization of modularity in metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Dynamical and correlation properties of the Internet
• Why social networks are different from other types of networks
• Growing Scale-Free Networks with Tunable Clustering
• Properties of highly clustered networks
• Highly clustered scale-free networks
• Clustering in complex networks. I. General formalism
• Tuning clustering in random networks with arbitrary degree distributions
• Networks of strong ties
• Solution for the properties of a clustered network
• Network Transitivity and Matrix Models

Cited by in corpus (171)

• Multilayer Networks
• Networks beyond pairwise interactions: structure and dynamics
• The Kuramoto model in complex networks
• Robustness and resilience of complex networks
• Suppressing cascades of load in interdependent networks
• The Statistical Physics of Real-World Networks
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• A message passing approach for general epidemic models
• Unification of theoretical approaches for epidemic spreading on complex networks
• Percolation on complex networks: Theory and application
• Coevolution spreading in complex networks
• Edge-Based Compartmental Modeling for Infectious Disease Spread Part I: An Overview
• Fundamentals of spreading processes in single and multilayer complex networks
• Analytical maximum-likelihood method to detect patterns in real networks
• Random graphs containing arbitrary distributions of subgraphs
• Binary-state dynamics on complex networks: pair approximation and beyond
• Identifying optimal targets of network attack by belief propagation
• Analysis of complex contagions in random multiplex networks
• Towards real-world complexity: an introduction to multiplex networks
• Accuracy of Mean-Field Theory for Dynamics on Real-World Networks
• Dynamics of social contagions with memory of non-redundant information
• Statistical Inference for Valued-Edge Networks: Generalized Exponential Random Graph Models
• The unreasonable effectiveness of tree-based theory for networks with clustering
• The robustness of interdependent clustered networks
• How clustering affects the bond percolation threshold in complex networks
• Message passing on networks with loops
• Cascades on a class of clustered random networks
• Higher-order clustering in networks
• Bond percolation on a class of clustered random networks
• Gibbs entropy of networks ensembles by cavity methods
• Evolution of robust network topologies: Emergence of central backbones
• Robustness of partially interdependent network formed of clustered networks
• EoN (Epidemics on Networks): a fast, flexible Python package for simulation, analytic approximation, and analysis of epidemics on networks
• Untangling the interplay between epidemic spreading and transmission network dynamic
• Propagation dynamics on networks featuring complex topologies
• Epidemics on random intersection graphs
• Deciphering the global organization of clustering in real complex networks
• Breaking of the site-bond percolation universality in networks
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Tight lower bound for percolation threshold on a quasi-regular graph
• Beyond the locally tree-like approximation for percolation on real networks
• Predicting the epidemic threshold of the susceptible-infected-recovered model
• Belief propagation for networks with loops
• Spectra of networks containing short loops
• The theory of percolation on hypergraphs
• Percolation in self-similar networks
• Higher-order structure and epidemic dynamics in clustered networks
• Explosive spreading on complex networks: the role of synergy
• Security Analysis Methods on Ethereum Smart Contract Vulnerabilities: A Survey
• Co-circulation of infectious diseases on networks
• Message-passing theory for cooperative epidemics
• Network cloning unfolds the effect of clustering on dynamical processes
• How does bond percolation happen in coloured networks?
• Explosion in weighted Hyperbolic Random Graphs and Geometric Inhomogeneous Random Graphs
• Modelling Epidemics on Networks
• Clustering determines the dynamics of complex contagions in multiplex networks
• A model of spreading of sudden events on social networks
• An Empirical Study of the Relation Between Community Structure and Transitivity
• Limited path entanglement percolation in quantum complex networks
• Clustering Phase Transitions and Hysteresis: Pitfalls in Constructing Network Ensembles
• Homophily as a Process Generating Social Networks: Insights from Social Distance Attachment Model
• Social Clustering in Epidemic Spread on Coevolving Networks
• General and exact approach to percolation on random graphs
• Bond percolation on a class of correlated and clustered random graphs
• Analytical results for bond percolation and k-core sizes on clustered networks
• Randomizing hypergraphs preserving degree correlation and local clustering
• Percolation on random networks with arbitrary k-core structure
• Ising model in clustered scale-free networks
• Suppressing epidemics on networks by exploiting observer nodes
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• Cascades on clique-based graphs
• The nature of hypergraph $k$-core percolation problems
• Combinatorial approach to Modularity
• Generating Simple Directed Social Network Graphs for Information Spreading
• A multi-type branching process method for modelling complex contagion on clustered networks
• Effects of local and global network connectivity on synergistic epidemics
• Clustering in random line graphs
• Endemic infections are always possible on regular networks
• Random graphs with arbitrary clustering and their applications
• Coupled dynamics of node and link states in complex networks: A model for language competition
• Networks with arbitrary edge multiplicities
• Beyond clustering: Mean-field dynamics on networks with arbitrary subgraph composition
• Power-law relations in random networks with communities
• Tweaking Synchronisation by Link Addition
• Are the different layers of a social network conveying the same information?
• Statistical Thermodynamics of Clustered Populations
• Two-pathogen model with competition on clustered networks
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Percolation in random graphs with higher-order clustering
• Synchronization in Scale Free networks with degree correlation
• Scale effects on spatially embedded contact networks
• Structure of percolating clusters in random clustered networks
• Highly Clustered Complex Networks in the Configuration Model: Random Regular Small-World Network
• Motifs in Triadic Random Graphs based on Steiner Triple Systems
• Jamming in complex networks with degree correlation
• Critical behavior and correlations on scale-free small-world networks. Application to network design
• Exotic phase transitions of k-cores in clustered networks
• Spectral estimation of the percolation transition in clustered networks
• Heterogeneous message passing for heterogeneous networks
• Predicting the diversity of early epidemic spread on networks
• Spectra of random networks in the weak clustering regime
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Dynamics of infectious disease in clustered networks with arbitrary degree distributions
• Atomic subgraphs and the statistical mechanics of networks
• Tunneling conductivity in anisotropic nanofibre composites: a percolation-based model
• Locally Differentially Private Analysis of Graph Statistics
• Imaginary replica analysis of loopy regular random graphs
• The Role of Masks in Mitigating Viral Spread on Networks
• Cooperative coinfection dynamics on clustered networks
• Self-avoiding walks and connective constants in clustered scale-free networks
• Compact pairwise models for epidemics with multiple infectious stages on degree heterogeneous and clustered networks
• Subgraphs and motifs in a dynamic airline network
• Exactly Solvable Random Graph Ensemble with Extensively Many Short Cycles
• Degree correlations in graphs with clique clustering
• An exact formula for percolation on higher-order cycles
• Mask-GVAE: Blind Denoising Graphs via Partition
• Sparse graphs: metrics and random models
• Effectiveness of Contact Tracing on Networks with Cliques
• Topological conditions drive stability in meta-ecosystems
• Mechanisms for tuning clustering and degree-correlations in directed networks
• Exact epidemic dynamics for generally clustered, complex networks
• Cliques and a new measure of clustering: with application to U.S. domestic airlines
• Effects of clustering heterogeneity on the spectral density of sparse networks
• Symbiotic and antagonistic disease dynamics on networks using bond percolatio
• Belief propagation on networks with cliques and chordless cycles
• Weighted projected networks: mapping hypergraphs to networks
• Strongly clustered random graphs via triadic closure: An exactly solvable model
• Conditions for viral influence spreading through multiplex correlated social networks
• Epidemic dynamics on metapopulation networks with node2vec mobility
• Structural Analysis of Viral Spreading Processes in Social and Communication Networks Using Egonets
• Observability transitions in clustered networks
• Assortativity in random line graphs
• Single-Seed Cascades on Clustered Networks
• The distribution of the number of node neighbors in random hypergraphs
• New methods to generate massive synthetic networks
• The scaling of human interactions with city size
• Properties of Latent Variable Network Models
• The Atlas for the Aspiring Network Scientist
• Copula-based analysis of the generalized friendship paradox in clustered networks
• Corrected mean-field model for random sequential adsorption on random geometric graphs
• Generating functions for message-passing on weighted networks: directed bond percolation and SIR epidemics
• Moment-Based Spectral Analysis of Large-Scale Networks Using Local Structural Information
• Numerical assessment of the percolation threshold using complement networks
• Complex Contagions and hybrid phase transitions in unclustered and clustered random networks
• Sandpile cascades on interacting tree-like networks
• An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
• Analytic Solution to Clustering Coefficients on Weighted Networks
• Exact deterministic representation of Markovian SIR epidemics on networks with and without loops
• Relaxation dynamics of maximally clustered networks
• Critical phenomena on heterogeneous small-world networks
• Percolation in clustered networks
• 2.5K-Graphs: from Sampling to Generation
• On the Role of Triadic Substructures in Complex Networks
• Algorithms for Generating Large-scale Clustered Random Graphs
• Communication-Efficient Triangle Counting under Local Differential Privacy
• Random Overlapping Communities: Approximating Motif Densities of Large Graphs
• Free-energy density functional for Strauss's model of transitive networks
• On the Number of Graphs with a Given Histogram
• Unimodality of the Expectation of Betti Numbers for Bernoulli Random Quota Complexes
• Rigidity percolation in random 3D rod systems
• Mean-field theory of vector spin models on networks with arbitrary degree distributions
• Epidemic spread in networks: Existing methods and current challenges
• Cyclic random graph models predicting giant molecules in hydrocarbon pyrolysis
• How universal is the mean-field universality class for percolation in complex networks?
• Motif Conservation Laws for the Configuration Model
• Searching for network modules
• A network with tunable clustering, degree correlation and degree distribution, and an epidemic thereon
• Fast generation of simple directed social network graphs with reciprocal edges and high clustering
• Consistent Approximation of Epidemic Dynamics on Degree-heterogeneous Clustered Networks
• Epidemic prediction and control in clustered populations
• An Independent Process Approximation to Sparse Random Graphs with a Prescribed Number of Edges and Triangles