A Frequency-Structure Decomposition for Link Streams

E. Bautista, M. Latapy

28th colloquium GRETSI, Nancy (France), 2022

A link stream is a set of triplets (t, u, v) modeling interactions over time and their effective analysis is key for numerous applications. They are traditionally studied via signal processing and graph theory approaches, which allow to study their dynamical and structural properties. However, current techniques do not allow to accurately reveal the frequency-structure patterns contained in them. To overcome this limitation, this work introduces a novel decomposition for link streams. Our decomposition analyses the time dimension via traditional signal dictionaries, like Fourier or wavelets, and the structural dimension via a new decomposition for graphs that we tailored to analyze sequences of graphs. We show that our decomposition allows to naturally design filters that can recover specific structures with specific frequencies.