Temporal networks in biology and medicine: a survey on models, algorithms, and tools

Abstract

The use of static graphs for modelling and analysis of biological and biomedical data plays a key role in biomedical research. However, many real-world scenarios present dynamic behaviours resulting in both node and edges modification as well as feature evolution. Consequently, ad-hoc models for capturing these evolutions along the time have been introduced, also referred to as dynamic, temporal, time-varying graphs. Here, we focus on temporal graphs, i.e., graphs whose evolution is represented by a sequence of time-ordered snapshots. Each snapshot represents a graph active in a particular timestamp. We survey temporal graph models and related algorithms, presenting fundamentals aspects and the recent advances. We formally define temporal graphs, focusing on the problem setting and we present their main applications in biology and medicine. We also present temporal graph embedding and the application to recent problems such as epidemic modelling. Finally, we further state some promising research directions in the area. Main results of this study include a systematic review of fundamental temporal network problems and their algorithmic solutions considered in the literature, in particular those having application in computational biology and medicine. We also include the main software developed in this context.

Fig. 1

Figure depicts three temporal snapshots of a temporal network

Fig. 2

(1) A representation of the temporal graph of Fig. 1 as a labelled graph and (2) the corresponding underlying graph $G_s$

Fig. 3

An extended temporal graph, where edges are labelled by pair $(t,\lambda )$, where t is a timestamp and $\lambda$ the time required to traverse the labelled edge at time t. In bold, a temporal path from Node 1 to Node 4 that starts a t time 1 and arrives at time 5

Fig. 4

An example of temporal walk in a temporal graph from Node 1 to Node 3. The thick edges belong to the walk; notice that the timestamps in bold satisfy the time constraint

Fig. 5

An example of temporal path in a temporal graph. The thick edges belong to the path and each node on the path is traversed once; notice also in this case that the timestamps in bold satisfies the time constraint

Fig. 6

A simple example of a temporal network with two nodes v and u and five timestamps that illustrates the concept of the inter-contact time. The inter-contact time ${\tau }_{v,u}$ between nodes v and u is a list of size 2, since there exist three temporal edges connecting v and u. ${\tau }_{v,u}$ is equal to [2,1], where the first value is the difference between timestamps of second and first temporal edge connecting v and u, that is timestamps 3 and 1; the second value of the vector is the difference between timestamps 4 and 3 (the timestamps of the third and second temporal edge connecting v, u)

Fig. 7

The example give in Kempe et al. (2002) that shows that Menger’s theorem does not hold for temporal graphs. There exists only one temporal vertex disjoint path from s to t, while the removal of one of the vertices in $\{a,b,c\}$ does not disconnect s from t

Fig. 8

An example of a temporal graph with a densest subgraph induced by nodes $\{1,2,3,4,6\}$ of density $\frac{7}{5}$ in interval [1, 2]

Fig. 9

An example of a cover of a temporal graph, as defined by MinTimeLineCover and MinMaxTimeLine, where the grey areas represent the interval activities of nodes. Nodes 1 and 3 have an activity interval of length of 1, since they are active in timestamp 1 and 2, and the remaining vertices have an activity interval of length 0, since they are active in a single timestamp

Fig. 10

Classification of the main problems related to paths, walks, circuits, and trails in temporal graphs, according to their complexity. Notice that Restless path is a decision problem (and it is NP-complete), while the others are all optimization problems