Randomized Rumor Spreading in Dynamic Graphs
Randomized Rumor Spreading in Dynamic Graphs
复制标题
动态图中的随机谣言传播
DOI：
10.1007/978-3-662-43951-7_42
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Alexandre O. Stauffer
中科院分区：
文献类型：
--
作者：
George Giakkoupis;Thomas Sauerwald;Alexandre O. Stauffer
我们考虑了研究得很好的谣言传播模型，在该模型中，节点在每一轮中联系一个随机的邻居以推送或拉出谣言。与大多数以前关注静态拓扑的工作不同，我们研究了一个动态图模型，其中允许对手在每一轮之前重新连接顶点之间的连接，从而产生一系列图，G1，G2，…我们的第一个结果是关于这些图的电导的谣言传播时间的界。我们证明了，如果每个结点的度在协议过程中变化不大(即至多一个恒定因子)，则对于某个t，在t轮内完成扩散，使得图G1到Gt的电导和为O(Logn)。这一结果甚至适用于自适应对手，该对手在一轮中的决策可能依赖于该轮之前的知情顶点集，并且蕴含了静态图的已知紧致电导界。接下来，我们证明了对于顶点扩展的替代扩展度量，情况是不同的。自适应对手可以显著延迟谣言的传播，即使图是规则的并且具有高伸缩性，这与静态图的情况不同，在静态图的情况下，高伸缩性被认为保证了谣言的快速传播。然而，如果敌手是健忘的，即图序列是在协议开始之前确定的，那么我们证明了对于任意正则图序列，接近于静态情况的界是成立的。
We consider the well-studied rumor spreading model in which nodes contact a random neighbor in each round in order to push or pull the rumor. Unlike most previous works which focus on static topologies, we look at a dynamic graph model where an adversary is allowed to rewire the connections between vertices before each round, giving rise to a sequence of graphs, G 1,G 2,… Our first result is a bound on the rumor spreading time in terms of the conductance of those graphs. We show that if the degree of each node does not change much during the protocol (that is, by at most a constant factor), then the spread completes within t rounds for some t such that the sum of conductances of the graphs G 1 up to G t is O(logn). This result holds even against an adaptive adversary whose decisions in a round may depend on the set of informed vertices before the round, and implies the known tight bound with conductance for static graphs. Next we show that for the alternative expansion measure of vertex expansion, the situation is different. An adaptive adversary can delay the spread of rumor significantly even if graphs are regular and have high expansion, unlike in the static graph case where high expansion is known to guarantee fast rumor spreading. However, if the adversary is oblivious, i.e., the graph sequence is decided before the protocol begins, then we show that a bound close to the one for the static case holds for any sequence of regular graphs.