Scale-free and stable structures in complex ad hoc networks.
Scale-free and stable structures in complex ad hoc networks.
复制标题
DOI：
10.1103/physreve.69.026101
复制
发表时间：
2003-03
期刊：
影响因子：
--
通讯作者：
N. Sarshar;V. Roychowdhury
中科院分区：
文献类型：
--
作者：
N. Sarshar;V. Roychowdhury
与成熟的增长网络模型不同，其中占主导地位的动态包括插入新的节点和连接以及重新连接现有的链接，我们研究ad hoc网络，其中还必须应对快速和随机删除现有的节点（因此，相关的链接）。我们首先表明，只基于众所周知的新节点的优先附件的动态不会导致一个足够重尾度分布在ad hoc网络。特别是，幂律指数的大小随着删除率迅速增加（从3），在相等的插入和删除率的极限下变得无穷大。然后，我们引入了一个本地和普遍的补偿性重新布线动态，并表明，即使在限制的相等的插入和删除率真正的无标度结构出现，其中的度分布服从幂律与可调指数，可以任意接近2。本文中报告的动态可用于设计高度动态对等网络的协议，也可用于解释在现有流行服务中观察到的幂律指数。
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 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 only on the well-known preferential attachments of new nodes do not lead to a sufficiently heavy-tailed degree distribution in ad hoc networks. In particular, the magnitude of the power-law exponent increases rapidly (from 3) with the deletion rate, becoming infinity in the limit of equal insertion and deletion rates. We then introduce a local and universal 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. The dynamics reported 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.