A class of algorithms which are based on the classical (prospective / retrospective) hotspotting techniques where a grid is replaced by edges on a network/graph.
We follow (1), which itself uses (2) for the KDE method.
The resulting "hotspot" is actually a "risk" estimate for each point on the network, where a higher risk corresponds to the belief that future events are more likely. As usual, we generate an actual "hotspot(s)" by chosing a "coverage level", say 10%, and then selecting the 10% of the network which is most risky, where we use the natural length of edges in the network to decide what "10%" means.
We might naturally want to compare such a prediction with a grid-based prediction. To do this, (1) suggests (although they don't quite use these words) generating a network prediction from a grid prediction. We do this by giving edge network point the "risk" of the grid cell it occurs in. Once this is done, we can then compare network predictions directly. (For example, to generate 10% coverage, we work from most risky to least risky grid cell, adding all the network which intersects with that cell, until we have selected 10% of the network by length.)
We follow (2); the summary in (1) is very clear. Let $s'$ be an event on the network. We seek to derive a formula for the (space-like) kernel induced at a point $s$. As a base, we start with a one-dimensional kernel function $f:\mathbb R\rightarrow [0,\infty)$. We assume that $f$ is symmetric, $f(-t) = f(t)$, and it should be normalised, $\int_{\mathbb R} f(t) \ dt = 1$. (Source (2) gives further conditions, but these are details, and will be satisfied by our kernels.) We always suppose our kernels have a finite "support", a value $t_\max$ such that $f(t)=0$ for any $|t|>t_\max$.
We consider all paths in the network from $s'$ to $s$, ignoring any "cyclic" paths. This is not entirely specified in (1), so we use this algorithm:
(1) considers a "prospective" hotspotting technique, which takes account of time. We consider forming a prediction at time $t$. Consider events which occur at time $t_i$ for $i=1,\cdots,n$, and which occur at a place $s_i$ on the network. We combine a time and space kernel.
Thus the final network "risk" estimate is at time $t$ and network location $s$, $$ \lambda(s,t) = \sum_{t_i<t} \frac{1}{h_T} \exp\Big( -\frac{t-t_i}{h_T} \Big) \Big( \sum_i \sum_{p:s_i\rightarrow s, l(p) \leq h_S} \frac{h_S - l(p)}{h_S^2(n_1-1)\cdots(n_{m(p)}-1)}\Big) $$
We are interested in an estimate of the risk at a fixed time $t$. Source (1) suggests sampling $\lambda(s) = \lambda(s,t)$ at various points $s$ across the network; (1) suggests every 30 metres. We make some comments on how to improve this, and towards efficient computation:
To find all paths between a point in the middle of an edge between vertices $u_1, u_2$ and a point in the middle of an edge between vertices $u_3, u_4$, we can proceed as follows:
Finally, once we have summed all the "risks" for each edge, we should normalise and divide by the length of the edge.
The above procedure is very slow if the "spatial bandwidth" of the kernel becomes large (and in practical situations, it is large). We have implemented a caching scheme which:
An alternative scheme, as explored more in the Geometry reduction notebook, is to approximate the sum over all paths by:
We again follow (1). Given a grid prediction, we can intersect the grid with the network, and assign the risk of each grid cell to every network part which intersects that cell.
For networks, it is hard(er) to produce toy examples. So instead of giving examples here, we give examples using real data from Chicago.
In [ ]: