论文标题
对动态网络中异步传播的严格分析
Tight Analysis of Asynchronous Rumor Spreading in Dynamic Networks
论文作者
论文摘要
异步的谣言算法传播了一条信息，即所谓的谣言，在网络中。从单个知情节点开始，每个节点都与$ 1 $的指数时间时钟相关联，并调用随机邻居，以便可能交换谣言。扩散时间是网络所有节点以很高的可能性告知的第一次。我们考虑在任何动态发展的网络中传播算法的时间，$ \ Mathcal {g} = \ {g^{（t）} _ {t = 0}^{\ infty} $，这是在分离的时间步骤$ t = 0,1，11 \ ldots $ $ t = 0，y ldots $。我们观察到，除了动态网络的扩展曲线外，节点随时间的分布效果传播时间。我们在图形电导和勤奋方面为扩散时间建立上限。对于给定连接的简单图$ g =（v，e）$，切割的努力集$ e（s，\ overline {s}）$定义为$ρ（s）= \ min _ {\ {\ {\ {u，v \} \ in E（s，s，s，s，s，\ edline {s}} \ max { \ bar {d}/d_v \} $其中$ d_u $是$ u $的度，$ \ \ bar {d} $是切割的一侧的平均节点的平均度，较小的体积（即$ {\ sathtt {vol}}}}} {（s s）} {（s s）} = \ sum_ sum_ _} $ g $的勤奋也定义为$ρ（g）= \ min_ {\ emptyset \ neq s \ subset v}ρ（s）$。我们表明，算法中$ \ MATHCAL {g} $的传播时间由$ t $界定，其中$ t $是$ \ sum_ {t = 0}^tφ（g^{（t）}）\cdotρ（g^{（t）} $ c \ log n $ n $ c \ den uconcanie $ c.^{（t）） $ g^{（t）} $和$ c $是指定常数。我们还将绝对勤奋定义为$ \Overlineρ（g）= \ min _ {\ {\ { $ \ sum_ {t = 0}^t \lceilφ（g^{（t）}）\ rceil \ cdot \ cdot \overlineρ（g^{（t）}）\ ge 2n $。我们提出动态网络，其中给定的上限几乎紧密。
The asynchronous rumor algorithm spreading propagates a piece of information, the so-called rumor, in a network. Starting with a single informed node, each node is associated with an exponential time clock with rate $1$ and calls a random neighbor in order to possibly exchange the rumor. Spread time is the first time when all nodes of a network are informed with high probability. We consider spread time of the algorithm in any dynamic evolving network, $\mathcal{G}=\{G^{(t)}\}_{t=0}^{\infty}$, which is a sequence of graphs exposed at discrete time step $t=0,1\ldots$. We observe that besides the expansion profile of a dynamic network, the degree distribution of nodes over time effect the spread time. We establish upper bounds for the spread time in terms of graph conductance and diligence. For a given connected simple graph $G=(V,E)$, the diligence of cut set $E(S, \overline{S})$ is defined as $ρ(S)=\min_{\{u,v\}\in E(S,\overline{S})}\max\{\bar{d}/d_u, \bar{d}/d_v\}$ where $d_u$ is the degree of $u$ and $\bar{d}$ is the average degree of nodes in the one side of the cut with smaller volume (i.e., ${\mathtt{vol}}{(S)}=\sum_{u\in S}d_u$). The diligence of $G$ is also defined as $ρ(G)=\min_{ \emptyset\neq S\subset V}ρ(S)$. We show that the spread time of the algorithm in $\mathcal{G}$ is bounded by $T$, where $T$ is the first time that $\sum_{t=0}^TΦ(G^{(t)})\cdotρ(G^{(t)})$ exceeds $C\log n$, where $Φ(G^{(t)})$ denotes the conductance of $G^{(t)}$ and $C$ is a specified constant. We also define the absolute diligence as $\overlineρ(G)=\min_{\{u,v\}\in E}\max\{1/d_u,1/d_v\}$ and establish upper bound $T$ for the spread time in terms of absolute diligence, which is the first time when $\sum_{t=0}^T\lceilΦ(G^{(t)})\rceil\cdot \overlineρ(G^{(t)})\ge 2n$. We present dynamic networks where the given upper bounds are almost tight.
