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.