| Affiliation: | (1) Delft University of Technology, Electrical Engineering, Mathematics and Computer Science, P.O. Box 5031, 2600 GA Delft, The Netherlands;(2) Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands;(3) EURANDOM, P.O. Box 513, 5600 MB Eindhoven, The Netherlands |
| Abstract: | We study random graphs with an i.i.d. degree sequence of which the tail of the distribution function  is regularly varying with exponent ![$$tauin [1,2]$$](/content/e7713134368617u1/10687_2006_Article_7963_TeX2GIFIEq2.gif) . In particular, the degrees have infinite mean. Such random graphs can serve as models for complex networks where degree power laws are observed. The minimal number of edges between two arbitrary nodes, also called the graph distance or the hopcount, is investigated when the size of the graph tends to infinity. The paper is part of a sequel of three papers. The other two papers study the case where  , and  , respectively. The main result of this paper is that the graph distance for  converges in distribution to a random variable with probability mass exclusively on the points  and  . We also consider the case where we condition the degrees to be at most  for some  , where  is the size of the graph. For fixed  and  such that  , the hopcount converges to  in probability, while for  , the hopcount converges to the same limit as for the unconditioned degrees. The proofs use extreme value theory. AMS 2000 Subject Classifications Primary—60G70; Secondary—05C80 |
