On the spread of random graphs
From MaRDI portal
Publication:5495672
DOI10.1017/S0963548314000248zbMATH Open1301.60010arXiv0902.1156MaRDI QIDQ5495672FDOQ5495672
Authors: Louigi Addario-Berry, Svante Janson, Colin McDiarmid 
Publication date: 6 August 2014
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0902.1156
Recommendations
Cites Work
- Collective dynamics of `small-world' networks
- Negative association of random variables, with applications
- Random graph dynamics
- Component behavior near the critical point of the random graph process
- Cycles in a random graph near the critical point
- Renormalization group analysis of the small-world network model
- A simple solution to the k‐core problem
- The sub-Gaussian constant and concentration inequalities
- Balls and bins: A study in negative dependence
- Diameters in supercritical random graphs via first passage percolation
- The diameter of sparse random graphs
- Size and connectivity of the \(k\)-core of a random graph
- An asymptotic isoperimetric inequality
- Matchings in random regular bipartite digraphs
Cited In (10)
- Combinatorial Aspects of Move-Up Crews for Spreading Processes on Networks
- Spectral bounds in random graphs applied to spreading phenomena and percolation
- Title not available (Why is that?)
- Revolutionaries and Spies on Random Graphs
- On Dissemination Thresholds in Regular and Irregular Graph Classes
- Almost-spanning universality in random graphs (extended abstract)
- On a 2-parameter class of scale free random graphs
- Mathematical analysis of topological and random \(m\)-order spread models
- A central limit theorem for diffusion in sparse random graphs
- Spreading of messages in 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)
