On the spread of random graphs
From MaRDI portal
Publication:5495672
Abstract: The spread of a connected graph G was introduced by Alon, Boppana and Spencer (1998) and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on V(G) of the variance of f(X) when X is uniformly distributed on V(G). We investigate the spread for certain models of sparse random graph; in particular for random regular graphs G(n,d), for ErdH{o}s-R'enyi random graphs G_{n,p} in the supercritical range p>1/n, and for a 'small world' model. For supercritical G_{n,p}, we show that if p=c/n with c>1 fixed then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge-lengths. We also give lower bounds on the spread for the barely supercritical case when p=(1+o(1))/n. Further, we show that for d large, with high probability the spread of G(n,d) becomes arbitrarily close to that of the complete graph K_n.
Recommendations
Cites work
- A simple solution to the k‐core problem
- An asymptotic isoperimetric inequality
- Balls and bins: A study in negative dependence
- Collective dynamics of `small-world' networks
- Component behavior near the critical point of the random graph process
- Cycles in a random graph near the critical point
- Diameters in supercritical random graphs via first passage percolation
- Matchings in random regular bipartite digraphs
- Negative association of random variables, with applications
- Random graph dynamics
- Renormalization group analysis of the small-world network model
- Size and connectivity of the \(k\)-core of a random graph
- The diameter of sparse random graphs
- The sub-Gaussian constant and concentration inequalities
Cited in
(10)- Spectral bounds in random graphs applied to spreading phenomena and percolation
- Mathematical analysis of topological and random \(m\)-order spread models
- A central limit theorem for diffusion in sparse random graphs
- On Dissemination Thresholds in Regular and Irregular Graph Classes
- scientific article; zbMATH DE number 2217106 (Why is no real title available?)
- Combinatorial Aspects of Move-Up Crews for Spreading Processes on Networks
- Spreading of messages in random graphs
- On a 2-parameter class of scale free random graphs
- Almost-spanning universality in random graphs (extended abstract)
- Revolutionaries and Spies on Random Graphs
This page was built for publication: On the spread of random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495672)
