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 Barabási and Albert
[3], as a simple model of the growth of real-world graphs such
as the world-wide web. Computer experiments presented by
Barabási, 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 log
n. We show that while this holds for
m=1, for
m
2 the diameter is
asymptotically log
n/log
log
n.
Mathematics Subject
Classification (2000): 05C80
* Research supported in part by NSF grant no.
DSM9971788