...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Low-Mean Hitting Time for Random Walks on Heterogeneous Networks
【24h】

Low-Mean Hitting Time for Random Walks on Heterogeneous Networks

机译：异构网络上随机游动的低平均击中时间

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Mean hitting time for random walks on a network, defined as the average of hitting times over all possible pairs of nodes, has found a large variety of applications in many areas. In this paper, we first prove that among all N-node networks, the complete graph has the minimum mean hitting time N - 1, which scales linearly with network size. We then study a random walk mobility model with location heterogeneity, modeled by scale-free networks, which are ubiquitous in realistic systems such as P2P networks. For this purpose, we consider random walks on two sparse scale-free small-world networks. By using the connection between random walks and electrical networks, we derive explicit formulas about mean hitting time for both networks, the dominant scaling of which exhibits the same behavior as that of complete graphs. This paper demonstrates that heterogeneous sparse networks can have low-mean hitting time with a behavior similar to that of dense complete graphs, which is instrumental in designing networks, where search is fast between any pair of nodes.
机译：网络上随机游动的平均命中时间（定义为所有可能的节点对上的命中时间的平均值）已经在许多领域中得到了广泛的应用。在本文中，我们首先证明在所有N节点网络中，完整图具有最小平均命中时间N-1，该时间与网络大小呈线性比例关系。然后，我们研究了具有位置异质性的随机步行移动性模型，该模型由无标度网络建模，而无标度网络在诸如P2P网络等现实系统中无处不在。为此，我们考虑在两个稀疏的无标度小世界网络上随机行走。通过使用随机游走与电网之间的联系，我们得出了关于两个网络的平均命中时间的显式公式，其主要标度表现出与完整图相同的行为。本文证明了异构稀疏网络可以具有低均值命中时间，其行为类似于密集完整图的行为，这对于设计网络非常重要，因为在网络设计中，任何一对节点之间的搜索都是快速的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号