Organization of growing random networks

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 ${A}_{k}.$ When ${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 all other nodes. When ${A}_{k}$ is asymptotically linear, ${N}_{k}(t)\ensuremath{\sim}{\mathrm{tk}}^{\ensuremath{-}\ensuremath{\nu}},$ with $\ensuremath{\nu}$ dependent on details of the attachment probability, but in the range $2<\ensuremath{\nu}<\ensuremath{\infty}.$ 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 ${s}^{\ensuremath{-}2}$ power-law tail, where s is the component size. The out component has a typical size of order $\mathrm{ln}t,$ and it provides basic insights into the genealogy of the network.