Although graphs are ubiquitous in statistical modelling, the definition of stochastic processes indexed on both nodes and edges is a relatively new research field. In this paper, we review some recent progress in this direction, defining (semi) metrics and covariance functions between any pair of points on temporally-evolving generalised networks. This setting complicates such definitions as the evolving topology does not allows to separate space and time: as a consequence, classical methods used in static domains fail. Last, we present the concept of time-evolving periodic graph and define covariance functions on it, which may prove to be useful in modelling phenomena whose time exhibits a circular structure.