Anomaly detection in link streams

01/03/2022 – 02/03/2022 all-day

Offre en lien avec l’Action/le Réseau : – — –/– — –

Laboratoire/Entreprise : LIP6 – Sorbonne Université
Durée : 6 months
Contact :
Date limite de publication : 2022-03-01

Contexte :
Link streams are sequences of interactions over time. They model a large number of datasets that have both a temporal and a structural component: phone calls, social interactions, internet traffic or financial transactions. The wealth of information contained in link streams bears great potential for progress in high-impact areas. For instance, frauds or thefts in monetary transactions may leave signatures expressed as substreams that heavily interact in a short span of time. Another example are network attacks which may be characterized as repetitive bursts of links that deviate from normal activity. Our goal in this internship is to develop algorithms that allow us to efficiently detect such anomalies in link streams.

Sujet :
The goal of this internship is to develop algorithms that can detect anomalies by ranking the importance of interactions in link streams. Recent works based on this idea have been used to detect microcluster anomalies: suddenly arriving groups of suspiciously similar links. However, such works rank interactions solely based on their time properties (how often two individuals interact) and overlook the structural properties of interactions. We therefore aim to develop ranking algorithms that take into account both the time and structural properties of link streams.

Numerous recent works have extended graph theory concepts to link streams, providing a solid foundation to analyze their structural properties. It is thus a timely challenge to leverage these concepts in the context of anomaly detection algorithms. We are particularly interested in exploring the recent definitions of temporal random walks, which have achieved great success in various applications. We are also open to explore other centrality metrics, such as betweenness, which raise important algorithmic challenges but have great interpretability.

Profil du candidat :
This internship is directed at M2 students with various background (complex networks, algorithmic, graph theory) with a strong interest in graph algorithmics and/or graph theory and its applications.

Formation et compétences requises :
Students in M2 with knowledge of the following: graph theory, algorithmique, statistics, statistical physics, and coding in Python and a compiled language like C/C++/Go/Rust.

Adresse d’emploi :
Le stagiaire fera partie de l’équipe Complex Networks du LIP6 – Sorbonne Université, situé à:
4 place Jussieu
75252 PARIS CEDEX 05, France

Document attaché : 202202011233_Internship_Proposal.pdf