Algebraic structures for dynamic networks

作者：Kontoleon Nectarios^*; Falzon Lucia; Pattison Philippa

来源：Journal of Mathematical Psychology, 2013, 57(6): 310-319.

DOI：10.1016/j.jmp.2013.11.002

• Dynamic networks
• Time-ordered paths
• Endomorphism algebra
• Generalised Gauss-Seidel algorithm
• Reachability in dynamic networks
• Betweenness in dynamic networks

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

• 出版日期2013-12