Pattern Matching in Link Streams: a Token-based Approach


Clément Bertrand, Hanna Klaudel, Matthieu Latapy et Frédéric Peschanski

Petri Nets, 2018


Link streams model the dynamics of interactions in complex
distributed systems as sequences of links (interactions) occurring at a
given time. Detecting patterns in such sequences is crucial for many ap-
plications but it raises several challenges. In particular, there is no generic
approach for the specification and detection of link stream patterns in
a way similar to regular expressions and automata for text patterns. To
address this, we propose a novel automata framework integrating both
timed constraints and finite memory together with a recognition algo-
rithm. The algorithm uses structures similar to tokens in high-level Petri
nets and includes non-determinism and concurrency. We illustrate the
use of our framework in real-world cases and evaluate its practical per-

This entry was posted in Papers