Abstract
The organizational development of growing random networks is investigated. These growing networks are built by adding nodes successively, and linking each to an earlier node of degree k with an attachment probability When grows more slowly than linearly with k, the number of nodes with k links, decays faster than a power law in k, while for growing faster than linearly in k, a single node emerges which connects to nearly all other nodes. When is asymptotically linear, with dependent on details of the attachment probability, but in the range The combined age and degree distribution of nodes shows that old nodes typically have a large degree. There is also a significant correlation in the degrees of neighboring nodes, so that nodes of similar degree are more likely to be connected. The size distributions of the in and out components of the network with respect to a given node—namely, its “descendants” and “ancestors”—are also determined. The in component exhibits a robust power-law tail, where s is the component size. The out component has a typical size of order and it provides basic insights into the genealogy of the network.
- Received 7 November 2000
DOI:https://doi.org/10.1103/PhysRevE.63.066123
©2001 American Physical Society