Scale-Free and Stable Structures in Complex {\em Ad hoc} networks

Abstract

Unlike the well-studied models of growing networks, where the dominant dynamics consist of insertions of new nodes and connections, and rewiring of existing links, we study {\em ad hoc} networks, where one also has to contend with rapid and random deletions of existing nodes (and, hence, the associated links). We first show that dynamics based {\em only} on the well-known preferential attachments of new nodes {\em do not} lead to a sufficiently heavy-tailed degree distribution in {\em ad hoc} networks. In particular, the magnitude of the power-law exponent increases rapidly (from 3) with the deletion rate, becoming $\infty$ in the limit of equal insertion and deletion rates. \iffalse ; thus, forcing the degree distribution to be essentially an exponential one.\fi We then introduce a {\em local} and {\em universal} {\em compensatory rewiring} dynamic, and show that even in the limit of equal insertion and deletion rates true scale-free structures emerge, where the degree distributions obey a power-law with a tunable exponent, which can be made arbitrarily close to -2. These results provide the first-known evidence of emergence of scale-free degree distributions purely due to dynamics, i.e., in networks of almost constant average size. The dynamics discovered in this paper can be used to craft protocols for designing highly dynamic Peer-to-Peer networks, and also to account for the power-law exponents observed in existing popular services.

References in corpus (5)

• Statistical mechanics of complex networks
• Topology of evolving networks: local events and universality
• Degree Distributions of Growing Networks
• Scaling properties of scale-free evolving networks: Continuous approach
• Scaling Behaviour of Developing and Decaying Networks

Cited by in corpus (21)

• Exact solutions for models of evolving networks with addition and deletion of nodes
• Experience versus Talent Shapes the Structure of the Web
• Fractional Dynamics of Network Growth Constrained by aging Node Interactions
• Effect of node deleting on network structure
• Scalable Percolation Search in Power Law Networks
• Growing distributed networks with arbitrary degree distributions
• Topological phase transition in a network model with preferential attachment and node removal
• Multiple Scale-Free Structures in Complex Ad-Hoc Networks
• Random Birth-and-Death Networks
• Preferential survival in models of complex ad hoc networks
• Scaling of critical connectivity of mobile ad hoc communication networks
• Randomly Evolving Idiotypic Networks: Structural Properties and Architecture
• Higher-order distributions and nongrowing complex networks without multiple connections
• Preservation of network Degree Distributions from non-uniform failures
• A Statistical Mechanical Load Balancer for the Web
• Stochastic resetting in a networked multiparticle system with correlated transitions
• A Maximum Entropy Method for the Prediction of Size Distributions
• Ad-hoc Limited Scale-Free Models for Unstructured Peer-to-Peer Networks
• Decay of Scale-Free Property in Birth-and-Death Network
• Controlling Communication Field of Complex Networks by Transformation Method
• The Degree Distribution of Random Birth-and-Death Network with Network Size Decline