Link Streams as a Generalization of Graphs and Time Series

Esteban Bautista, Matthieu Latapy In « Temporal Network Theory », Holme, P. and Saramäki, J. (eds), Springer, 2023 DOI: 10.1007/978-3-031-30399-9_22œ A link stream is a set of possibly weighted triplets (t, u, v) modeling that u and v interacted at time t. Link streams offer an effective model for datasets containing both temporal and relational information, making their proper analysis crucial in many applications. They …

Computing Betweenness Centrality in Link Stream

Frédéric Simard, Clémence Magnien, Matthieu Latapy Journal of Graph Algorithms and Applications 27:3, 2023 DOI: 10.7155/jgaa.00620 Betweenness centrality is one of the most important concepts in graph analysis. It was recently extended to link streams, a graph generalization where links arrive over time. However, its computation raises non-trivial issues, due in particular to the fact that time …

A Frequency-Structure Approach for Link Stream Analysis

Esteban Bautista, Matthieu Latapy Fifth IEEE International Conference on Cognitive Machine Intelligence (CogMI), 2023 A link stream is a set of triplets (t,u,v) indicating that u and v interacted at time t. Link streams model numerous datasets and their proper study is crucial in many applications. In practice, raw link streams are often aggregated or transformed into time series or graphs where decisions …

A local updating algorithm for Personalized PageRank via Chebyshev Polynomials

Esteban Bautista, Matthieu Latapy In Social Network Analysis and Mining, 2022, vol. 12, no 1, p. 1-11. The personalized PageRank algorithm is one of the most versatile tools for the analysis of networks. In spite of its ubiquity, maintaining personalized PageRank vectors when the underlying network constantly evolves is still a challenging task. To address this …

A logical approach for temporal and multiplex networks analysis

Esteban Bautista, Matthieu Latapy In 10th International Conference on Complex Networks and their Applications, Madrid (Spain), December 2021 (Poster) Many systems generate data as a set of triplets (a,b,c): they may represent that user acalled b at time c or that customer a purchased product b in store c. These datasets aretraditionally studied as networks with an …

Strongly Connected Components in StreamGraphs: Computation and Experimentations

Léo Rannou, Clémence Magnien, and Matthieu Latapy In Proceedings of the 9th International Conference on Complex Networks and their Applications, 2020 Stream graphs model highly dynamic networks in which nodes and/or links arrive and/or leave over time. Strongly connected components in stream graphs were defined recently, but no algorithm was provided to compute them. We …

Do you trade with your friends or become friends with your trading partners? A case study in the G1 cryptocurrency

Nicolas Gensollen, Matthieu Latapy In Applied Network Science, 5 (25), 2020 We study the interplay between social ties and financial transactions made through a recent cryptocurrency called G1. It has the particularity of combining the usual transaction record with a reliable network of identified users. This gives the opportunity to observe exactly who sent money …

Predicting interactions between individuals with structural and dynamical information

Thibaud Arnoux, Lionel Tabourier, Matthieu Latapy In Journal of Interdisciplinary Methodologies and Issues in Sciences, 2019 Capturing both structural and temporal features of interactions is crucial in many real-world situations like studies of contact between individuals. Using the link stream formalism to model data, we address here the activity prediction problem: we predict the number …

Weighted, Bipartite, or Directed Stream Graphs for the Modeling of Temporal Networks

Matthieu Latapy, Clémence Magnien, Tiphaine Viard In Temporal Network Theory, Holme P., Saramäki J. (eds), Computational Social Sciences, Springer, 2019 We recently introduced a formalism for the modeling of temporal networks, that we call stream graphs. It emphasizes the streaming nature of data and allows rigorous definitions of many important concepts generalizing classical graphs. This …

A general graph-based framework for top-N recommendation using content, temporal and trust information

Armel Jacques Nzekon Nzeko’o, Maurice Tchuente and Matthieu Latapy Journal of Interdisciplinary Methodologies and Issues in Sciences, 2019 Recommending appropriate items to users is crucial in many e-commerce platforms that containimplicit data as users’ browsing, purchasing and streaming history. One common approach con-sists in selecting the N most relevant items to each user, for a …

Spreading dynamics in a cattle trade network: Size, speed, typical profile and consequences on epidemic control strategies

Aurore Payen, Lionel Tabourier and Matthieu Latapy PLOS ONE, 2019 Infections can spread among livestock notably because infected animals can be brought to uncontaminated holdings, therefore exposing a new group of susceptible animals to the dis- ease. As a consequence, the structure and dynamics of animal trade networks is a major focus of interest to …

Degree-based Outlier Detection within IP Traffic Modelled as a Link Stream (extended version)

Audrey Wilmet, Tiphaine Viard, Matthieu Latapy and Robin Lamarche-Perrin Computer Networks, 2019 This paper aims at precisely detecting and identifying anomalous events in IP traffic. To this end, we adopt the link stream formalism which properly captures temporal and structural features of the data. Within this framework, we focus on finding anomalous behaviours with respect …

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 …

Pattern Matching in Link Streams: Timed-Automata with Finite Memory

Clément Bertrand, Frédéric Peschanski, Hanna Klaudel and Matthieu Latapy Scientific Annals of Computer Science, 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 applications but it raises several challenges. In particular, there is …

Degree-based Outliers Detection within IP Traffic Modelled as a Link Stream

Audrey Wilmet, Tiphaine Viard, Matthieu Latapy and Robin Lamarche-Perrin TMA Conference 2018, Vienna Precise detection and identification of anomalous events in IP traffic are crucial in many applications. This paper intends to address this task by adopting the link stream formalism which properly captures temporal and structural features of the data. Within this framework we …

Enumerating maximal cliques in link streams with durations

Tiphaine Viard, Clémence Magnien, and Matthieu Latapy Information Processing Letters 133 (2018), p. 44-48 Link streams model interactions over time, and a clique in a link stream is defined as a set of nodes and a time interval such that all pairs of nodes in this set interact permanently during this time interval. This notion …

Discovering Patterns of Interest in IP Traffic Using Cliques in Bipartite Link Streams

Tiphaine Viard, Raphaël Fournier-S’niehotta, Clémence Magnien and Matthieu Latapy International Conference on Complex Networks (CompleNet), 2018. Studying IP traffic is crucial for many applications. We focus here on the detection of (structurally and temporally) dense sequences of interactions, that may indicate botnets or coordinated network scans. More precisely, we model a MAWI capture of IP …

Stream Graphs and Link Streams for the Modeling of Interactions over Time

Matthieu Latapy, Tiphaine Viard and Clémence Magnien Social Networks Analysis and Mining, 8: 61, 2018 Graph theory provides a language for studying the structure of relations, and it is often used to study interactions over time too. However, it poorly captures the both temporal and structural nature of interactions, that calls for a dedicated formalism. …