Thumbnail
Access Restriction
Open

Author Bertrand, Clément ♦ Klaudel, Hanna ♦ Latapy, Matthieu ♦ Peschanski, Frédéric
Source Hyper Articles en Ligne (HAL)
Content type Text
File Format PDF
Language English
Subject Keyword link streams ♦ Timed pattern recognition ♦ finite-memory automata ♦ timed automata ♦ complex networks ♦ info ♦ Computer Science [cs] ♦ Computer Science [cs]/Social and Information Networks [cs.SI]
Abstract 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 applications 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 algorithm. 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 performances .
Educational Use Research
Learning Resource Type Proceeding
Publisher Date 2018-06-29
Volume Number 10877
Page Count 21
Starting Page 227
Ending Page 247