The Diameter of Random Sparse Graphs

95 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Sampling biases in IP topology measurements (2003, methodology): “As a result we use an approximation to |Γh| derived from simulation and consistent with the bounds in [16], [17].”
Connected Components in Random Graphs with Given Expected Degree Sequences (2002, background): “and results that we derive in dealing with random graphs with given expected degree distribution are useful not only for modeling and analyzing realistic graphs but also leading to improvements for some problems on classical random graphs as well [14,29].”
Critical random graphs: Diameter and mixing time (2007, unknown): “ar X iv :m at h/ 07 01 31 6v 4 [ m at h. PR ] 2 7 A ug 2 00 8 The Annals of Probability 2008, Vol. 36, No. 4, 1267–1286 DOI: 10.1214/07-AOP358 c© Institute of Mathematical Statistics, 2008 CRITICAL RANDOM GRAPHS: DIAMETER AND MIXING TIME1 By Asaf Nachmias and Yuval Peres”
The continuum limit of critical random graphs (2009, background): “Chung and Lu [14] focused on the early supercritical phase, when np > 1 and np ≤ c log n.”
The average distances in random graphs with given expected degrees (2002, result): “surely connected. Using a result in [ 7 ], the diameter of this subgraph is at most log n”