  A link stream is a set of triplets $(t, u, v)$ indicating that $u$ and $v$
interacted at time $t$. Link streams model numerous datasets and their proper
study is crucial in many applications. In practice, raw link streams are often
aggregated or transformed into time series or graphs where decisions are made.
Yet, it remains unclear how the dynamical and structural information of a raw
link stream carries into the transformed object. This work shows that it is
possible to shed light into this question by studying link streams via
algebraically linear graph and signal operators, for which we introduce a novel
linear matrix framework for the analysis of link streams. We show that, due to
their linearity, most methods in signal processing can be easily adopted by our
framework to analyze the time/frequency information of link streams. However,
the availability of linear graph methods to analyze relational/structural
information is limited. We address this limitation by developing (i) a new
basis for graphs that allow us to decompose them into structures at different
resolution levels; and (ii) filters for graphs that allow us to change their
structural information in a controlled manner. By plugging-in these
developments and their time-domain counterpart into our framework, we are able
to (i) obtain a new basis for link streams that allow us to represent them in a
frequency-structure domain; and (ii) show that many interesting transformations
to link streams, like the aggregation of interactions or their embedding into a
euclidean space, can be seen as simple filters in our frequency-structure
domain.
