Algebraic structures for dynamic networks

• We construct an algebra for the analysis of time-ordered relational networks.
• We use the algebra to construct time-ordered paths and walks.
• We develop algorithms to calculate time-ordered reachability and betweenness.
• We show that the results with time-ordering differ markedly from the static case.

In this paper, we extend the algebraic foundations for network structures to the dynamic case. The networks of interest are those in which each pair of network nodes is connected for a finite, possibly empty, set of closed time intervals within a fixed time period. We present an algebra of interval sets and define several operations on these sets, including an addition operation and several forms of relational composition, and consider the algebraic structures to which they give rise. The first composition operation is equivalent to the construction of Moody’s (2002) time-ordered paths and yields a left dioid structure. The second composition operation, termed δδ-composition, introduces a decay variable, that may be specified by the type of transmission and/or relation; it reflects a finite time period after which the last edge in a path cannot be extended to form a longer path. We show how to construct a dioid of endomorphisms in this second case. In the case of both algebras, we demonstrate how to compute time-respecting paths and walks from relational interval arrays. In order to illustrate the computational potential of these constructions, we assess reachability and betweenness in an illustrative set of observations on a dynamic network. The approach developed here provides the foundation for further development of measures for dynamic networks that are based on time-respecting walks and paths.