Navigable Small-World networks with few random bits

被引:0
|
作者
Cordasco, Gennaro [1 ]
Gargano, Luisa [1 ]
机构
[1] Univ Salerno, Dipartimento Informat & Applicaz RM Capocelli, I-84084 Fisciano, Italy
关键词
Small-World networks; Kleinberg's model; Greedy routing; Complex networks;
D O I
10.1016/j.tcs.2009.07.050
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study Small-World graphs in the perspective of their use in the development of efficient as well as easy to implement network infrastructures. Our analysis starts from the Small-World model proposed by Kleinberg: a grid network augmented with directed long-range random links. The choices of the long-range links are independent from one node to another. In this setting greedy routing and some of its variants have been analyzed and shown to produce paths of polylogarithmic expected length. We start from asking whether all the randomness, used in Kleinberg's model for establishing the long-range contacts of the nodes, is indeed necessary to assure the existence of short paths. In order to deal with the above question, we impose (stringent) restrictions oil the choice of long-range links and we show that such restrictions do not increase the average path length of greedy routing and its variations. We are able to decrease the number of random bits, required to establish each node's long-range link, from Omega(log n) to O(log log n) on a network of size it. Diminishing the randomness in the choice of random links has several benefits; in particular, it implies all increase in the clustering of the graph, thus increasing the resilience of the network. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码:4975 / 4988
页数:14
相关论文
共 50 条
  • [1] Random Walks on Stochastic and Deterministic Small-World Networks
    Wang, Zi-Yi
    Guo, Shi-Ze
    Lu, Zhe-Ming
    Song, Guang-Hua
    Li, Hui
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2013, E96D (05): : 1215 - 1218
  • [2] Synchronizibility of random rewired small-world chaotic networks
    Liu Jie
    Lu Junan
    Proceedings of the 24th Chinese Control Conference, Vols 1 and 2, 2005, : 228 - 231
  • [3] On Detection and Structural Reconstruction of Small-World Random Networks
    Cai, Tony
    Liang, Tengyuan
    Rakhlin, Alexander
    IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING, 2017, 4 (03): : 165 - 176
  • [4] Random walks in small-world exponential treelike networks
    Zhang, Zhongzhi
    Li, Xintong
    Lin, Yuan
    Chen, Guanrong
    JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2011,
  • [5] Intersection of Random Spanning Trees in Small-World Networks
    London, Andras
    Pluhar, Andras
    COMPLEX NETWORKS AND THEIR APPLICATIONS XI, COMPLEX NETWORKS 2022, VOL 2, 2023, 1078 : 337 - 345
  • [6] Bifurcation control in small-world networks
    Cheng, Zunshui
    Cao, Jinde
    NEUROCOMPUTING, 2009, 72 (7-9) : 1712 - 1718
  • [7] The small-world effect for interferometer networks
    Krawciw, Benjamin
    Carr, Lincoln D.
    Diniz Behn, Cecilia
    JOURNAL OF PHYSICS-COMPLEXITY, 2024, 5 (02):
  • [8] Eccentricities on small-world networks
    Li, Wentao
    Qiao, Miao
    Qin, Lu
    Zhang, Ying
    Chang, Lijun
    Lin, Xuemin
    VLDB JOURNAL, 2019, 28 (05): : 765 - 792
  • [9] Eccentricities on small-world networks
    Wentao Li
    Miao Qiao
    Lu Qin
    Ying Zhang
    Lijun Chang
    Xuemin Lin
    The VLDB Journal, 2019, 28 : 765 - 792
  • [10] Epilepsy in small-world networks
    Netoff, TI
    Clewley, R
    Arno, S
    Keck, T
    White, JA
    JOURNAL OF NEUROSCIENCE, 2004, 24 (37): : 8075 - 8083