English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of identifying the source of a stochastic diffusionprocess spreading on a graph based on the arrival times of the diffusion at afew queried nodes. In a graph $G=(V,E)$, an unknown source node $v^* \in V$ isdrawn uniformly at random, and unknown edge weights $w(e)$ for $e\in E$,representing the propagation delays along the edges, are drawn independentlyfrom a Gaussian distribution of mean $1$ and variance $\sigma^2$. An algorithmthen attempts to identify $v^*$ by querying nodes $q \in V$ and being told thelength 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 bedecided in advance, and adaptive, in which each query can depend on the resultsof the previous ones. Both settings are motivated by an application of theproblem to epidemic processes (where the source is called patient zero), whichwe discuss in detail.  We characterize the query complexity when $G$ is an $n$-node path. In thenon-adaptive setting, $\Theta(n\sigma^2)$ queries are needed for $\sigma^2 \leq1$, and $\Theta(n)$ for $\sigma^2 \geq 1$. In the adaptive setting, somewhatsurprisingly, only $\Theta(\log\log_{1/\sigma}n)$ are needed when $\sigma^2\leq 1/2$, and $\Theta(\log \log n)+O_\sigma(1)$ when $\sigma^2 \geq 1/2$. Thisis the first mathematical study of source identification with time queries in anon-deterministic diffusion process.

The power of adaptivity in source identification with time queries on the path