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

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

2003-03-03

arxiv.org/abs/cond-mat/0303041v2

Phys. Rev. E 69, 026101 (2004)

Physics

Condensed Matter

Disordered Systems and Neural Networks

Scientific paper

10.1103/PhysRevE.69.026101

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.

Affiliated with

Also associated with

No associations

Rating

Scale-Free and Stable Structures in Complex {\em Ad hoc} networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scale-Free and Stable Structures in Complex {\em Ad hoc} networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scale-Free and Stable Structures in Complex {\em Ad hoc} networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-493622