A critical point for random graphs with a given degree sequence

From MaRDI portal

Publication:4697807

Jump to:navigation, search

DOI10.1002/rsa.3240060204zbMath0823.05050OpenAlexW2044881936WikidataQ56564362 ScholiaQ56564362MaRDI QIDQ4697807

Bruce A. Reed, Michael S. O. Molloy

Publication date: 23 October 1995

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240060204

zbMATH Keywords

random graphs chromatic number threshold degree sequence giant component

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Related Items

Mixing times of random walks on dynamic configuration models, Exactly scale-free scale-free networks, Optimal attack strategy of complex networks based on tabu search, Investigating the relationship between \(k\)-core and \(s\)-core network decompositions, Cost effective campaigning in social networks, Improving pairwise approximations for network models with susceptible-infected-susceptible dynamics, A generalized voter model on complex networks, The tail does not determine the size of the giant, Minimum vertex cover in generalized random graphs with power law degree distribution, Disease invasion risk in a growing population, Interval estimates for epidemic thresholds in two-sex network models, Robustness of power-law networks: its assessment and optimization, Underestimated cost of targeted attacks on complex networks, Epidemics in a population with social structures, Generating simple random graphs with prescribed degree distribution, Number of cliques in random scale-free network ensembles, \(k\)-core architecture and \(k\)-core percolation on complex networks, Anomalous electrical and frictionless flow conductance in complex networks, Synchronization in weighted scale-free networks with degree-degree correlation, Faster mixing and small bottlenecks, Firm-to-firm labor flows and the aggregate matching function: a network-based test using employer-employee matched records, On bounding exact models of epidemic spread on networks, A sequential algorithm for generating random graphs, Time-varying human mobility patterns with metapopulation epidemic dynamics, Percolation on interdependent networks with a fraction of antagonistic interactions, Distance in random graphs with infinite mean degrees, Approximating optimal controls for networks when there are combinations of population-level and targeted measures available: chlamydia infection as a case-study, Qualitative analysis on differential, fractional differential, and dynamic equations and related topics, Integrating fluctuations into distribution of resources in transportation networks, Unravelling the size distribution of social groups with information theory in complex networks, Parameterisation of Keeling's network generation algorithm, When is a scale-free graph ultra-small?, Structural transition in random mappings, Real-time growth rate for general stochastic SIR epidemics on unclustered networks, Large graph limit for an SIR process in random network with heterogeneous connectivity, Jamming in complex networks with degree correlation, Catastrophic event phenomena in communication networks: a survey, Generation of arbitrary two-point correlated directed networks with given modularity, Principles of statistical mechanics of uncorrelated random networks, Optimal link removal for epidemic mitigation: A two-way partitioning approach, Diffusion and cascading behavior in random networks, A network with tunable clustering, degree correlation and degree distribution, and an epidemic thereon, The configuration model for partially directed graphs, Beyond clustering: mean-field dynamics on networks with arbitrary subgraph composition, Cores of random \(r\)-partite hypergraphs, Geographical embedding of scale-free networks, Respondent-driven sampling on directed networks, Random graphs with a given degree sequence, Overlapping modularity at the critical point of \(k\)-clique percolation, Trapping of continuous-time quantum walks on Erdős-Rényi graphs, Moment closure of infectious diseases model on heterogeneous metapopulation network, The component sizes of a critical random graph with given degree sequence, A weighted configuration model and inhomogeneous epidemics, Asymptotic normality of the \(k\)-core in random graphs, A testing based extraction algorithm for identifying significant communities in networks, SIR dynamics in random networks with heterogeneous connectivity, On the largest component of a random graph with a subpower-law degree sequence in a subcritical phase, The largest component in a subcritical random graph with a power law degree distribution, Rejection sampling of bipartite graphs with given degree sequence, Central limit theorems in the configuration model, Edge percolation on a random regular graph of low degree, On the termination of some biclique operators on multipartite graphs, A stochastic SIR network epidemic model with preventive dropping of edges, Model for disease dynamics of a waterborne pathogen on a random network, How to determine if a random graph with a fixed degree sequence has a giant component, Mean-field models for non-Markovian epidemics on networks, The Kuramoto model in complex networks, Hypercube percolation, Statistical physics of vaccination, Networks, epidemics and vaccination through contact tracing, General results on preferential attachment and clustering coefficient, Universality for the distance in finite variance random graphs, Sparse maximum-entropy random graphs with a given power-law degree distribution, From ecology to finance (and back?): a review on entropy-based null models for the analysis of bipartite networks, Percolation in invariant Poisson graphs with i.i.d. degrees, A note on the derivation of epidemic final sizes, Critical points for random Boolean networks, Epidemics and vaccination on weighted graphs, Analysis of a stochastic SIR epidemic on a random network incorporating household structure, Transport between multiple users in complex networks, Random walks between leaves of random networks, SIR dynamics in random networks with communities, Algebraic bounds for heterogeneous site percolation on directed and undirected graphs, Epidemic modeling in metapopulation systems with heterogeneous coupling pattern: theory and simulations, Modelling the spread of diseases in clustered networks, On algebraic connectivity of directed scale-free networks, On the maximum betweenness improvement problem, Sufficient conditions of endemic threshold on metapopulation networks, Predicting missing links via local information, Bootstrapping on undirected binary networks via statistical mechanics, Large deviations of empirical neighborhood distribution in sparse random graphs, A scale-free graph model based on bipartite graphs, Constrained Markovian dynamics of random graphs, The evolution of the min-min random graph process, Counting triangles in power-law uniform random graphs, On a random graph evolving by degrees, An edge-based model of SEIR epidemics on static random networks, Limit theorems for a random graph epidemic model, Metric structure of random networks, Directed cycles and related structures in random graphs. I: Static properties, Moments of Uniform Random Multigraphs with Fixed Degree Sequences, Ordering in voter models on networks: exact reduction to a single-coordinate diffusion, SIR epidemics on random graphs with a fixed degree sequence, THE ROLE OF GEOGRAPHY AND TRAFFIC IN THE STRUCTURE OF COMPLEX NETWORKS, Analytical results for the distribution of cover times of random walks on random regular graphs, The mean and variance of the distribution of shortest path lengths of random regular graphs, Random Simplicial Complexes: Models and Phenomena, A functional central limit theorem for SI processes on configuration model graphs, Analytical results for the distribution of first-passage times of random walks on random regular graphs, THE FRIENDSHIP PARADOX FOR WEIGHTED AND DIRECTED NETWORKS, Some Introductory Notes on Random Graphs, Structural Characterization of Networks Using the Cat Cortex as an Example, Unnamed Item, Estimating the size of populations at high risk for HIV using respondent‐driven sampling data, Critical value asymptotics for the contact process on random graphs, Glauber dynamics for Ising models on random regular graphs: cut-off and metastability, DYNAMICS OF ROUTING MECHANISMS ON TRAFFIC NETWORKS, EFFECTS OF DEGREE CORRELATION ON THE SYNCHRONIZATION OF NETWORKS OF OSCILLATORS, Persuasion in Networks: Public Signals and Cores, OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS, SYNCHRONIZABILITY AND SYNCHRONIZATION DYNAMICS OF WEIGHED AND UNWEIGHED SCALE FREE NETWORKS WITH DEGREE MIXING, Generating Maximally Disassortative Graphs with Given Degree Distribution, Bounding the Size and Probability of Epidemics on Networks, The Construction and Properties of Assortative Configuration Graphs, Unnamed Item, Critical Window for Connectivity in the Configuration Model, Random graphs with given vertex degrees and switchings, The degree-wise effect of a second step for a random walk on a graph, Exactly solvable random graph ensemble with extensively many short cycles, Asymptotic normality in random graphs with given vertex degrees, Toward formal models of biologically inspired, highly parallel machine cognition, Two faces of greedy leaf removal procedure on graphs, Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication, Unnamed Item, Constructing and sampling directed graphs with given degree sequences, Scaling Limits of Random Trees and Random Graphs, Diffusion in Random Networks: Impact of Degree Distribution, Random degree–degree correlated networks, Binary decision making with very heterogeneous influence, Discontinuous transition of a multistage independent cascade model on networks, DISCRETE-TIME EPIDEMIC DYNAMICS WITH AWARENESS IN RANDOM NETWORKS, Prisoner’s dilemma on directed networks, The scaling of the minimum sum of edge lengths in uniformly random trees, Effect of link oriented self-healing on resilience of networks, Failure-recovery model with competition between failures in complex networks: a dynamical approach, The distribution of first hitting times of random walks on directed Erdős–Rényi networks, Large fluctuations in anti-coordination games on scale-free graphs, Exact sampling of graphs with prescribed degree correlations, Configuring Random Graph Models with Fixed Degree Sequences, Controlling epidemic outbreak based on local dynamic infectiousness on complex networks, Component structure of the vacant set induced by a random walk on a random graph, The transsortative structure of networks, Network comparison and the within-ensemble graph distance, Asymptotics of trees with a prescribed degree sequence and applications, SWITCHER-RANDOM-WALKS: A COGNITIVE-INSPIRED MECHANISM FOR NETWORK EXPLORATION, Unnamed Item, Random graphs with forbidden vertex degrees, Resolvent of large random graphs, Giant Component in Random Multipartite Graphs with Given Degree Sequences, A system of grabbing particles related to Galton-Watson trees, Graphs with specified degree distributions, simple epidemics, and local vaccination strategies, Nonuniversality of weighted random graphs with infinite variance degree, Extreme value theory, Poisson-Dirichlet distributions, and first passage percolation on random networks, Stochastic kronecker graphs, Synchronization of Network-Coupled Oscillators with Uncertain Dynamics, Infinite and Giant Components in the Layers Percolation Model, Random Graphs with a Fixed Maximum Degree, A new approach to the giant component problem, The average distances in random graphs with given expected degrees, Physicist’s approach to public transportation networks: between data processing and statistical physics, Epistemic Communities: Description and Hierarchic Categorization, Transport optimization on complex networks, Extreme fluctuations in noisy task-completion landscapes on scale-free networks, Optimal resource diffusion for suppressing disease spreading in multiplex networks, Spectral bounds in random graphs applied to spreading phenomena and percolation, Compound Poisson approximation of subgraph counts in stochastic block models with multiple edges, The effects of spatial constraints on the evolution of weighted complex networks, Loops of any size and Hamilton cycles in random scale-free networks, Inhomogeneous percolation models for spreading phenomena in random graphs, An ensemble of random graphs with identical degree distribution, Conservation laws for voter-like models on random directed networks, Unbiased sampling of network ensembles, Birds of a feather or opposites attract - effects in network modelling, Cooperative Assembly Systems, The solution space geometry of random linear equations, Graph Embedding through Random Walk for Shortest Paths Problems, Degree-Degree Dependencies in Random Graphs with Heavy-Tailed Degrees, A New Random Graph Model with Self-Optimizing Nodes: Connectivity and Diameter, Why Do Simple Algorithms for Triangle Enumeration Work in the Real World?, Karp–Sipser on Random Graphs with a Fixed Degree Sequence, Component structure of the configuration model: Barely supercritical case, Directed random graphs with given degree distributions, COMPLEX NETWORKS: TOPOLOGY, DYNAMICS AND SYNCHRONIZATION, The Structure of an Outbreak on a College Campus, The combination of targeted vaccination and ring vaccination, The Why, How, and When of Representations for Complex Systems, Law of large numbers for the SIR epidemic on a random graph with given degrees, Contact Vaccination Study Using Edge Based Compartmental Model (EBCM) and Stochastic Simulation: An Application to Oral Poliovirus Vaccine (OPV), Evolution of random graph processes with degree constraints, Percolation on Random Graphs with a Fixed Degree Sequence, Erosion of synchronization: coupling heterogeneity and network structure, Systemic risk in multiplex networks with asymmetric coupling and threshold feedback, Null models and community detection in multi-layer networks, Scalable percolation search on complex networks, Local heuristics and the emergence of spanning subgraphs in complex networks, Rare event asymptotics for exploration processes for random graphs, Depth first exploration of a configuration model, Functional relation between fluctuation and node degree in coupled stochastic dynamical systems, Effects of city-size heterogeneity on epidemic spreading in a metapopulation: a reaction-diffusion approach, Human mobility and time spent at destination: impact on spatial epidemic spreading, The scaling window for a random graph with a given degree sequence, A simple and efficient algorithm for modeling modular complex networks, Are crossing dependencies really scarce?, Observability transition in multiplex networks, Chase-escape on the configuration model, Random Oxford graphs, Average hopcount of the shortest path in tree-like components with finite size, Analysis of SHIR rumor propagation in random heterogeneous networks with dynamic friendships, Bipartite structure of all complex networks, A novel measure of edge and vertex centrality for assessing robustness in complex networks, Efficient network disruption under imperfect information: the sharpening effect of network reconstruction with no prior knowledge, The structure of typical clusters in large sparse random configurations, Generating Fibonacci-model as evolution of networks with vertex-velocity and time-memory, Dynamic vaccination game in a heterogeneous mixing population, Shells structure in uncorrelated scale-free networks, Effects of heterogeneous self-protection awareness on resource-epidemic coevolution dynamics, Interplay between epidemic spread and information propagation on metapopulation networks, Heterogeneous network epidemics: real-time growth, variance and extinction of infection, Critical percolation on scale-free random graphs: new universality class for the configuration model, Complex networks: structure and dynamics, How Clustering Affects Epidemics in Random Networks, Basic reproduction number for the SIR epidemic in degree correlated networks, Transmission dynamics of oral polio vaccine viruses and vaccine-derived polioviruses on networks, Universality for critical heavy-tailed network models: metric structure of maximal components, Relationship between fragility and resilience in complex networks, SIR epidemics and vaccination on random graphs with clustering, Mathematical analysis of epidemic models with treatment in heterogeneous networks, Thresholds for virus spread on networks, Self-awareness-based resource allocation strategy for containment of epidemic spreading, A central limit theorem for diffusion in sparse random graphs, Ensemble nonequivalence in random graphs with modular structure, Searchability of central nodes in networks, Culture and inattentional blindness: a global workspace perspective, Contact processes on scale-free networks, First passage percolation on random graphs with finite mean degrees, Limit distributions of the number of loops in a random configuration graph, Epidemics on a weighted network with tunable degree-degree correlation, Epidemics on random intersection graphs, Heavy-tailed configuration models at criticality, Survival and extinction of epidemics on random graphs with general degree, Percolation on complex networks: theory and application, A Random Graph Model for Power Law Graphs, Transport properties of random walks on scale-free/regular-lattice hybrid networks, Central limit theorems for SIR epidemics and percolation on configuration model random graphs, Systemic risk in banking networks: advantages of ``tiered banking systems, Dynamics of stochastic epidemics on heterogeneous networks, Synchronization in random networks with given expected degree sequences, A non-Markovian SIR network model with fixed infectious period and preventive rewiring, Edge-based SEIR dynamics with or without infectious force in latent period on random networks, The dynamics of sexual contact networks: effects on disease spread and control, Phase transition of random non-uniform hypergraphs, Contagions in random networks with overlapping communities, Network extreme eigenvalue: From mutimodal to scale-free networks, Infectious diseases spreading on a metapopulation network coupled with its second-neighbor network, Metastability of the contact process on fast evolving scale-free networks, A low-dimensional network model for an SIS epidemic: analysis of the super compact pairwise model, Applications of the variance of final outbreak size for disease spreading in networks, Theory of chemical evolution of molecule compositions in the universe, in the Miller-Urey experiment and the mass distribution of interstellar and intergalactic molecules, Geometry of the minimal spanning tree of a random 3-regular graph, Dynamics of an edge-based SEIR model for sexually transmitted diseases, On giant components and treewidth in the layers model, Bipartite and directed scale-free complex networks arising from zeta functions, Temporal Evolution of Social Innovation: What Matters?, A propagation model with defensive measures for PLC-PC worms in industrial networks, Information propagation in stochastic networks, Structural sparsity of complex networks: bounded expansion in random models and real-world graphs, Limits of sparse configuration models and beyond: graphexes and multigraphexes, Critical behavior in inhomogeneous random graphs, Rumor spreading of an SIHR model in heterogeneous networks based on probability generating function, Global lower mass-bound for critical configuration models in the heavy-tailed regime, Susceptible-infected epidemics on evolving graphs, Phases of small worlds: a mean field formulation, A general critical condition for the emergence of a giant component in random graphs with given degrees, Phase transitions on Markovian bipartite graphs-an application of the zero-range process, The Bohman-Frieze process near criticality, Sandwiching dense random regular graphs between binomial random graphs, Modeling and analysis of new products diffusion on heterogeneous networks, Critical window for the vacant set left by random walk on random regular graphs, Limit laws for self-loops and multiple edges in the configuration model, Degree distribution dynamics for disease spreading with individual awareness, On the mean distance in scale free graphs, The stable graph: the metric space scaling limit of a critical random graph with i.i.d. power-law degrees, An old approach to the giant component problem, Distance evolutions in growing preferential attachment graphs, DISTRIBUTION DYNAMICS FOR SIS MODEL ON RANDOM NETWORKS, Accuracy criterion for mean field approximations of Markov processes on hypergraphs, Quantum contact process on scale-free networks, Degree distribution of shortest path trees and bias of network sampling algorithms, Jigsaw percolation: what social networks can collaboratively solve a puzzle?, Distinguishing power-law uniform random graphs from inhomogeneous random graphs through small subgraphs, An Experimental Study of Algorithms for Online Bipartite Matching, A probabilistic approach to the leader problem in random graphs, Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon, On the modularity of 3‐regular random graphs and random graphs with given degree sequences, Statistical Network Analysis: A Review with Applications to the Coronavirus Disease 2019 Pandemic, Phase transition in random intersection graphs with communities, Epidemics on networks with preventive rewiring, Growth strategy determines the memory and structural properties of brain networks, Causal Structural Learning via Local Graphs, Unstable diffusion in social networks, Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication, Necessary and sufficient conditions for exact closures of epidemic equations on configuration model networks, Dynamics of diffusion on monoplex and multiplex networks: a message-passing approach, Epidemic dynamics of influenza-like diseases spreading in complex networks, Rumor transmission in online social networks under Nash equilibrium of a psychological decision game, Stable graphs: distributions and line-breaking construction, Largest component of subcritical random graphs with given degree sequence, Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model, Some Bounds for the Vertex Degree Function Index of Connected Graphs with Given Minimum and Maximum Degrees, Percolation of arbitrary uncorrelated nested subgraphs, Edge-based compartmental modeling for the spread of cholera on random networks: a case study in Somalia, The winner takes it all but one, Unnamed Item, First-Order Model-Checking in Random Graphs and Complex Networks, Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size, Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk, The Stripping Process Can be Slow: Part II, Lower bounds for random 3-SAT via differential equations, Almost all graphs with average degree 4 are 3-colorable, On a conditionally Poissonian graph process, Generating stationary random graphs on ℤ with prescribed independent, identically distributed degrees, Using the bootstrap for statistical inference on random graphs, The effects of evolutionary adaptations on spreading processes in complex networks, Degree-ordered-percolation on uncorrelated networks, Analytical results for the distribution of first hitting times of random walks on random regular graphs, Analytical results for the distribution of first return times of random walks on random regular graphs, Stochastic resetting in a networked multiparticle system with correlated transitions

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:4697807&oldid=18927370"