Algebraic structures for dynamic networks

Abstract

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 dec..