Random graphs containing arbitrary distributions of subgraphs

Abstract

Traditional random graph models of networks generate networks that are locally tree-like, meaning that all local neighborhoods take the form of trees. In this respect such models are highly unrealistic, most real networks having strongly non-tree-like neighborhoods that contain short loops, cliques, or other biconnected subgraphs. In this paper we propose and analyze a new class of random graph models that incorporates general subgraphs, allowing for non-tree-like neighborhoods while still remaining solvable for many fundamental network properties. Among other things we give solutions for the size of the giant component, the position of the phase transition at which the giant component appears, and percolation properties for both site and bond percolation on networks generated by the model.

12 pages, 6 figures, 1 table

References in corpus (16)

• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• The spread of epidemic disease on networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Hierarchical structure and the prediction of missing links in networks
• Dynamical and correlation properties of the Internet
• Random graphs with clustering
• Properties of highly clustered networks
• Clustering in complex networks. I. General formalism
• Clustering in complex networks. II. Percolation properties
• Networks of strong ties
• Bond percolation on a class of clustered random networks
• Loops structure of the Internet at the Autonomous System Level
• Random acyclic networks
• Analytical results for bond percolation and k-core sizes on clustered networks

Cited by in corpus (80)

• Networks beyond pairwise interactions: structure and dynamics
• The Kuramoto model in complex networks
• Suppressing cascades of load in interdependent networks
• Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
• Percolation on complex networks: Theory and application
• Edge-Based Compartmental Modeling for Infectious Disease Spread Part I: An Overview
• Quantifying randomness in real networks
• Accuracy of Mean-Field Theory for Dynamics on Real-World Networks
• The robustness of interdependent clustered networks
• Message passing on networks with loops
• Cascades on a class of clustered random networks
• Deciphering the global organization of clustering in real complex networks
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Spectra of networks containing short loops
• Higher-order structure and epidemic dynamics in clustered networks
• Clique percolation in random graphs
• Network cloning unfolds the effect of clustering on dynamical processes
• Clustering determines the dynamics of complex contagions in multiplex networks
• Structural preferential attachment: Network organization beyond the link
• Symbolic regression of generative network models
• General and exact approach to percolation on random graphs
• Epidemic fronts in complex networks with metapopulation structure
• Bond percolation on a class of correlated and clustered random graphs
• Randomizing hypergraphs preserving degree correlation and local clustering
• Percolation on random networks with arbitrary k-core structure
• Ising model in clustered scale-free networks
• Cascades on clique-based graphs
• Random graphs with arbitrary clustering and their applications
• Propagation on networks: an exact alternative perspective
• Percolation and the effective structure of complex networks
• 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
• Subgraph covers -- An information theoretic approach to motif analysis in networks
• Epidemic control in networks with cliques
• Two-pathogen model with competition on clustered networks
• Scale effects on spatially embedded contact networks
• Percolation in random graphs with higher-order clustering
• Optimizing and controlling functions of complex networks by manipulating rich-club connections
• Atomic subgraphs and the statistical mechanics of networks
• Predicting the diversity of early epidemic spread on networks
• Dynamics of infectious disease in clustered networks with arbitrary degree distributions
• Stylized facts in social networks: Community-based static modeling
• Spectra of random networks in the weak clustering regime
• Cooperative coinfection dynamics on clustered networks
• Compact pairwise models for epidemics with multiple infectious stages on degree heterogeneous and clustered networks
• Degree correlations in graphs with clique clustering
• Exact solution of bond percolation on small arbitrary graphs
• Epidemics on contact networks: a general stochastic approach
• Effectiveness of Contact Tracing on Networks with Cliques
• An exact formula for percolation on higher-order cycles
• Sample-to-sample fluctuations in real-network ensembles
• Effects of clustering heterogeneity on the spectral density of sparse networks
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• Exact epidemic dynamics for generally clustered, complex networks
• Belief propagation on networks with cliques and chordless cycles
• Strongly clustered random graphs via triadic closure: An exactly solvable model
• The elliptic model for social fluxes
• Automatic Discovery of Families of Network Generative Processes
• Generating Scale-free Networks with Adjustable Clustering Coefficient Via Random Walks
• Generating functions for message-passing on weighted networks: directed bond percolation and SIR epidemics
• Corrected mean-field model for random sequential adsorption on random geometric graphs
• Complex Contagions and hybrid phase transitions in unclustered and clustered random networks
• Exact analytical solution of irreversible binary dynamics on networks
• Sandpile cascades on interacting tree-like networks
• Lack of Hyperbolicity in Asymptotic Erdös--Renyi Sparse Random Graphs
• On the Role of Triadic Substructures in Complex Networks
• Superexponential growth of epidemics in networks with cliques
• Hybrid evolving clique-networks and their communicability
• Consistent Approximation of Epidemic Dynamics on Degree-heterogeneous Clustered Networks
• Construction of simplicial complexes with prescribed degree-size sequences
• Bayesian learning of forest and tree graphical models
• Mapping structural diversity in networks sharing a given degree distribution and global clustering: Adaptive resolution grid search evolution with Diophantine equation-based mutations
• Epidemic spread in networks: Existing methods and current challenges
• Statistical properties of mutualistic-competitive random networks
• Motif Conservation Laws for the Configuration Model
• A network with tunable clustering, degree correlation and degree distribution, and an epidemic thereon
• On the Number of Graphs with a Given Histogram
• Cyclic random graph models predicting giant molecules in hydrocarbon pyrolysis