Models for information propagation on graphs
  We propose and unify classes of different models for information propagation
over graphs. In a first class, propagation is modeled as a wave which emanates
from a set of known nodes at an initial time, to all other unknown nodes at
later times with an ordering determined by the arrival time of the information
wave front. A second class of models is based on the notion of a travel time
along paths between nodes. The time of information propagation from an initial
known set of nodes to a node is defined as the minimum of a generalized travel
time over subsets of all admissible paths. A final class is given by imposing a
local equation of an eikonal form at each unknown node, with boundary
conditions at the known nodes. The solution value of the local equation at a
node is coupled to those of neighbouring nodes with lower values. We provide
precise formulations of the model classes and prove equivalences between them.
Motivated by the connection between first arrival time model and the eikonal
equation in the continuum setting, we derive mean field limits for graphs based
on uniform grids in Euclidean space under grid refinement. For a specific
parameter setting, we demonstrate that the solution on the grid approximates
the Euclidean distance, and illustrate the use of front propagation on graphs
to semi-supervised learning.
