Growing random networks under constraints Amit R. Puniyani and Rajan M. Lukose HP Laboratories Palo Alto, CA 94304

Abstract We study the evolution of a random graph under the constraint that the diameter remain constant as the graph grows. We show that if the graph maintains the form of its link distribution it must be scale-free with exponent between 2 and 3. These uniqueness results may help explain the scale-free nature of graphs, of varying sizes, representing the evolved metabolic pathways in 43 organisms.

** Last modified: 7/17/2001** Full paper: PDF (7/17 version)