Multiple power-law structures in heterogeneous complex networks.

Abstract

This paper develops a framework for analyzing and designing dynamic networks comprising different classes of nodes that coexist and interact in one shared environment. We consider ad hoc (i.e., nodes can leave the network unannounced, and no node has any global knowledge about the class identities of other nodes) preferentially grown networks, where different classes of nodes are characterized by different sets of local parameters used in the stochastic dynamics that all nodes in the network execute. We show that multiple scale-free structures, one within each class of nodes, and with tunable power-law exponents (as determined by the sets of parameters characterizing each class), emerge naturally in our model. Moreover, the coexistence of the scale-free structures of the different classes of nodes can be captured by succinct phase diagrams, which show a rich set of structures, including stable regions where different classes coexist in heavy-tailed (i.e., the exponent is between 2 and 3) and light-tailed (i.e., the exponent is greater than 3) states, and sharp phase transitions. The topology of the emergent networks is also shown to display a complex structure, akin to the distribution of different components of an alloyed material; e.g., nodes with a light-tailed scale-free structure get embedded to the outside of the network, and have most of their edges connected to nodes belonging to the class with a heavy-tailed distribution. Finally, we show how the dynamics formulated in this paper will serve as an essential part of ad hoc networking protocols, which can lead to the formation of robust and efficiently searchable networks [including, the well-known peer-to-peer networks] even under very dynamic conditions.