Organization of growing random networks - art. no. 066123

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 A(k). Wh en A(k) grows more slowly than linearly with k, the number of nodes with k links. N-k(t), decays faster than a power law in k, while for A(k) growing faster than linearly in k, a single node emerges which connects to nearly a ll other nodes. When A(k) is asymptotically linear, N-k(t) similar to tk(-n u), With nu dependent on details of the attachment probability, but in the range 2 < <nu><<infinity>. The combined age and degree distribution of node s shows that old nodes typically have a large degree. There is also a signi ficant correlation in the degrees of neighboring nodes, so that nodes of si milar 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 ex hibits a robust s(-2) power-law tail, where s is the component size. The ou t component has a typical size of order In t, and it provides basic insight s into the genealogy of the network.