论文标题
适应性在源识别中与路径上的时间查询的功能
The power of adaptivity in source identification with time queries on the path
论文作者
论文摘要
我们研究了根据几个查询节点在扩散的到达时间上识别随机扩散过程扩散时间在图上扩散的问题。在图$ g =（v，e）$中，一个未知的源节点$ v^* \ in v $随机均匀地绘制了均匀的绘制，而未知的边缘权重$ w（e）$ w（e）$ w（e）in e $ in e $，代表沿着边缘的传播延迟，是由平均$ 1 $ $ 1 $ and Variance $ and Variance $ and Variance $ c $ c $ c $ c $ c $ c $ f $ pressian the Edges沿岸绘制的。然后，算法试图通过查询节点$ q \ in V $来识别$ v^*$，并被告知$ w $加权$ q $和$ v^*$之间的最短路径的长度。我们考虑两个设置：非自适应，其中所有查询节点必须提前确定，并自适应，其中每个查询都可以取决于先前的结果。这两种设置都是由该问题应用于流行过程（来源称为患者零）的动机，我们会详细讨论。 当$ g $是$ n $节路径时，我们会表征查询复杂性。在非自适应设置中，需要$θ（nσ^2）$查询，对于$σ^2 \ leq 1 $，而$σ^2 \ geq 1 $的$θ（n）$。在自适应设置中，有些令人惊讶的是，仅$θ（\ log \ log_ {1/σ} n）$需要$σ^2 \ leq 1/2 $，而$θ（\ log \ log \ log \ log \ log \ log n）+o_σ（1）这是在非确定性扩散过程中对源识别和时间查询的第一项数学研究。
We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph $G=(V,E)$, an unknown source node $v^* \in V$ is drawn uniformly at random, and unknown edge weights $w(e)$ for $e\in E$, representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean $1$ and variance $σ^2$. An algorithm then attempts to identify $v^*$ by querying nodes $q \in V$ and being told the length of the shortest path between $q$ and $v^*$ in graph $G$ weighted by $w$. We consider two settings: non-adaptive, in which all query nodes must be decided in advance, and adaptive, in which each query can depend on the results of the previous ones. Both settings are motivated by an application of the problem to epidemic processes (where the source is called patient zero), which we discuss in detail. We characterize the query complexity when $G$ is an $n$-node path. In the non-adaptive setting, $Θ(nσ^2)$ queries are needed for $σ^2 \leq 1$, and $Θ(n)$ for $σ^2 \geq 1$. In the adaptive setting, somewhat surprisingly, only $Θ(\log\log_{1/σ}n)$ are needed when $σ^2 \leq 1/2$, and $Θ(\log \log n)+O_σ(1)$ when $σ^2 \geq 1/2$. This is the first mathematical study of source identification with time queries in a non-deterministic diffusion process.
