  Many real-world networks evolve over time, that is, new contacts appear and
old contacts may disappear. They can be modeled as temporal graphs where
interactions between vertices (which represent people in the case of social
networks) are represented by time-stamped edges. One of the most fundamental
problems in (social) network analysis is community detection, and one of the
most basic primitives to model a community is a clique. Addressing the problem
of finding communities in temporal networks, Viard et al. [TCS 2016] introduced
$\Delta$-cliques as a natural temporal version of cliques. Himmel et al. [SNAM
2017] showed how to adapt the well-known Bron-Kerbosch algorithm to enumerate
$\Delta$-cliques. We continue this work and improve and extend the algorithm of
Himmel et al. to enumerate temporal $k$-plexes (notably, cliques are the
special case $k=1$).
  We define a $\Delta$-$k$-plex as a set of vertices and a time interval, where
during this time interval each vertex has in each consecutive $\Delta + 1$ time
steps at least one edge to all but at most $k-1$ vertices in the chosen set of
vertices. We develop a recursive algorithm for enumerating all maximal
$\Delta$-$k$-plexs and perform experiments on real-world social networks that
demonstrate the practical feasibility of our approach. In particular, for the
special case of $\Delta$-1-plexes (that is, $\Delta$-cliques), we observe that
our algorithm is on average significantly faster than the previous algorithms
by Himmel et al. [SNAM 2017] and Viard et al. [IPL 2018] for enumerating
$\Delta$-cliques.
