Graph theory provides a language for studying the structure of relations, and\nit is often used to study interactions over time too. However, it poorly\ncaptures the both temporal and structural nature of interactions, that calls\nfor a dedicated formalism. In this paper, we generalize graph concepts in order\nto cope with both aspects in a consistent way. We start with elementary\nconcepts like density, clusters, or paths, and derive from them more advanced\nconcepts like cliques, degrees, clustering coefficients, or connected\ncomponents. We obtain a language to directly deal with interactions over time,\nsimilar to the language provided by graphs to deal with relations. This\nformalism is self-consistent: usual relations between different concepts are\npreserved. It is also consistent with graph theory: graph concepts are special\ncases of the ones we introduce. This makes it easy to generalize higher-level\nobjects such as quotient graphs, line graphs, k-cores, and centralities. This\npaper also considers discrete versus continuous time assumptions, instantaneous\nlinks, and extensions to more complex cases.\n