Ideal Free Distributions in Growing Networks
(Presented at the American Control Conference in Seattle, WA)
There is growing interest in understanding the emergence of a class of real-world networks called “scale-free networks” (e.g., computer networks such as the World Wide Web, some protein-protein interaction networks, and networks created by the formation of sexual partnerships). In this context, the number of edges (connections) that is most commonly found in a network (graph) indicates the scale of its connectivity distribution (e.g., the peak in a Poisson or bell-shaped distribution). Broadly speaking, the most notable feature of a scale-free network is its heavy-tailed (power-law), rather than a Poisson or bell-shaped, connectivity distribution. In particular, power-law distributions indicate that the probability P (k) that a node connects to k other nodes is proportional to k−β for some positive constant β , implying that the number of edges (the degree) of the nodes of the network comprises different orders of magnitude (i.e., with a few nodes having a high degree, many having only a low one, and without a peak in the distribution). We presents a class of network optimization processes that account for the emergence of scale-free network structures. We introduce a mathematical framework that captures the connectivity and growth dynamics of a network with an arbitrary initial topology. We show how selection via differential node fitness affects the proportion of connections a node makes to other nodes, and how a heavy-tailed connectivity behavior manifests itself from consecutive achievements of IFDs. Finally, we present simulation results that show how this class of networks may emerge even when consecutive IFDs are not perfectly reached.
[gview file=”IFDs-in-growing-networks.pdf”]