The diameter of a scale-free random graph

We consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number m of earlier vertices, where each earlier vertex is chosen with probability proportional to its degree. This process was introduced by Barabaasi and Albert [3], as a simple model of the growth of real-world graphs such as the world-wide web. Computer experiments presented by Barabaasi, Albert and Jeong [1,5] and heuristic arguments given by Newman, Strogatz and Watts [23] suggest that after n steps the resulting graph should have diameter approximately logn. We show that while this holds for m=1, for mgreater than or equal to2 the diameter is asymptotically log n/log log n.