Optimal Routing in a Small-World Network
摘要
实质的研究被奉献给在自然以及人的社会产生的 small-worldphenomenon 的建模。更早的工作集中于各种各样的小世界的模型的静态的性质。检验路由方面， Kleinberg 基于一个 d 维的 toroidal 格子建议一个模型，远程的连接根据泛音分发在随机选择。由使用仅仅本地的信息，贪婪路由选择算法在期望的 O (lg~2 n ) 执行的 Kleinberg 表演数跳跃。我们扩大 Kleinberg “由允许每节点 x 有二更多的随机的小世界的模型连接到一致地并且随机选择在以内的节点的 s (lgn ) 从 x 的 ~(2/d ) 曼哈顿距离。基于这个扩展模型，我们然后建议能在期望的 O (lg n ) 发送在任何二个节点之间的消息的一个忘却的算法数字跳跃。Ourrouting 算法保留仅仅 O ((lg n )~( β + 1 )) 每个节点的信息的位 1 < β < 2，因此是可伸缩的 w.r.t 网络尺寸。到我们的知识，当仍然保留时，我们的结果是第一完成最佳路由选择复杂性一在小世界的网络在每个节点上存储的信息的 poly 对数的位数。
引用本文（GB/T 7714）
曾坚阳, 许文经. Optimal Routing in a Small-World Network[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2006.
引文网络
本站仅收录题录与摘要供学习参考，全文版权归属出版方；如有侵权请联系我们删除。