• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Information Spreading in Stationary Markovian Evolving Graphs
【24h】

Information Spreading in Stationary Markovian Evolving Graphs

机译：平稳马尔可夫演化图中的信息传播

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

摘要

Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule. They are extremely general and they can well describe important dynamic-network scenarios. We study the speed of information spreading in the stationary phase by analyzing the completion time of the flooding mechanism. We prove a general theorem that establishes an upper bound on flooding time in any stationary Markovian evolving graph in terms of its node-expansion properties. We apply our theorem in two natural and relevant cases of such dynamic graphs. Geometric Markovian evolving graphs where the Markovian behaviour is yielded by n mobile radio stations, with fixed transmission radius, that perform independent random walks over a square region of the plane. Edge-Markovian evolving graphs where the probability of existence of any edge at time t depends on the existence (or not) of the same edge at time t-1. In both cases, the obtained upper bounds hold with high probability and they are nearly tight. In fact, they turn out to be tight for a large range of the values of the input parameters. As for geometric Markovian evolving graphs, our result represents the first analytical upper bound for flooding time on a class of concrete mobile networks.
机译：马尔可夫演化图是动态图模型，其中固定节点集之间的链接会根据任意马尔可夫规则随时间变化。它们非常笼统，可以很好地描述重要的动态网络方案。通过分析淹没机制的完成时间，我们研究了信息在固定阶段的传播速度。我们证明了一个通用定理，该定理根据其节点扩展性质在任何平稳的马尔可夫演化图中确定了泛洪时间的上限。我们将定理应用于此类动态图的两种自然和相关情况。几何马尔可夫演化图，其中马尔可夫行为由n个具有固定传输半径的移动无线电台产生，它们在平面的正方形区域上执行独立的随机游动。 Edge-Markovian演化图，其中在时间t处存在任何边缘的概率取决于在时间t-1处相同边缘的存在（或不存在）。在这两种情况下，获得的上限都具有很高的概率，并且几乎是紧密的。实际上，对于很大范围的输入参数值，它们都非常严格。对于几何马尔可夫演化图，我们的结果代表了一类具体的移动网络上洪水时间的第一个分析上限。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号