  Generative network models play an important role in algorithm development,
scaling studies, network analysis, and realistic system benchmarks for graph
data sets. A complex network model gaining considerable popularity builds
random hyperbolic graphs, generated by distributing points within a disk in the
hyperbolic plane and then adding edges between points with a probability
depending on their hyperbolic distance.
  We present a dynamic extension to model gradual network change, while
preserving at each step the point position probabilities. To process the
dynamic changes efficiently, we formalize the concept of a probabilistic
neighborhood: Let $P$ be a set of $n$ points in Euclidean or hyperbolic space,
$q$ a query point, $\operatorname{dist}$ a distance metric, and $f :
\mathbb{R}^+ \rightarrow [0,1]$ a monotonically decreasing function. Then, the
probabilistic neighborhood $N(q, f)$ of $q$ with respect to $f$ is a random
subset of $P$ and each point $p \in P$ belongs to $N(q,f)$ with probability
$f(\operatorname{dist}(p,q))$. We present a fast, sublinear-time query
algorithm to sample probabilistic neighborhoods from planar point sets. For
certain distributions of planar $P$, we prove that our algorithm answers a
query in $O((|N(q,f)| + \sqrt{n})\log n)$ time with high probability. This
enables us to process a node movement in random hyperbolic graphs in sublinear
time, resulting in a speedup of about one order of magnitude in practice
compared to the fastest previous approach. Apart from that, our query algorithm
is also applicable to Euclidean geometry, making it of independent interest for
other sampling or probabilistic spreading scenarios.
