Title: Stream Graphs and Link Streams for the Modeling of Interactions over Time,
Abstract: Graph theory provides a language for studying the structure of relations, and
it is often used to study interactions over time too. However, it poorly
captures the both temporal and structural nature of interactions, that calls
for a dedicated formalism. In this paper, we generalize graph concepts in order
to cope with both aspects in a consistent way. We start with elementary
concepts like density, clusters, or paths, and derive from them more advanced
concepts like cliques, degrees, clustering coefficients, or connected
components. We obtain a language to directly deal with interactions over time,
similar to the language provided by graphs to deal with relations. This
formalism is self-consistent: usual relations between different concepts are
preserved. It is also consistent with graph theory: graph concepts are special
cases of the ones we introduce. This makes it easy to generalize higher-level
objects such as quotient graphs, line graphs, k-cores, and centralities. This
paper also considers discrete versus continuous time assumptions, instantaneous
links, and extensions to more complex cases.