logo EDITE Sujets de doctorat

Combiner prédiction de liens et détection d'événements pour décrire la dynamique des flots de liens

Sujet proposé par
Directeur de thèse:
Doctorant: Thibaud ARNOUX
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

Un flot de liens est une séquence de triplets (t,u,v) indiquant qu'une interaction entre u et v a eu lieu à l'instant t. Les flots de liens représentent les interactions au cours du temps, comme par exemple des échanges de messages, des appels téléphoniques ou des contacts entre individus, ou encore du trafic réseau ou des transactions financières [1]. Dans de tels flots, la dynamique habituelle des interactions, comme par exemple les usages quotidiens du réseau, est souvent mélangée à des dynamiques plus spécifiques telles que des polémiques, des pannes, des attaques ou des tentatives de fraudes.

La thèse porte sur l'étude de la structure et de la dynamique de ces flots de liens. Cette question est capitale car il s'agit d'une puissante manière de décrire, d'analyser et de comprendre les phénomènes sous-jacents, avec un impact important dans des domaines cruciaux comme la sécurité, la diffusion d'information, ou la conception de protocoles réseaux.

Enjeux

Deux approches majeures et complémentaires sont actuellement explorées par la communauté scientifique : la prédiction de liens [2,3] et la détection d'événements [4]. La prédiction de liens vise à déduire les interactions futures à partir des caractéristiques des interactions passées. Par exemple si un individu envoie une message à un autre, il est probable que cela se reproduise à l'avenir. Si un individu échange avec deux autres, un contact ultérieur entre ceux-ci est probable. A l'inverse, la détection d'événements a pour but d'identifier des moments spécifiques auxquels la dynamique du système change significativement, au moins pour un groupe donné.

Un tel changement peut être par exemple indiquer une controverse importante dans une liste de diffusion, ou une attaque sur un réseau. Ces deux approches pour analyser les flots de liens sont actuellement explorées de façon essentiellement indépendante, étant donnée l'apparente divergence d'objectif. Cependant, combiner ces deux approches semble extrêmement prometteur : les événements peuvent en effet être vus comme des liens ne pouvant être prédits, et la dynamique globale est la composition de comportements normaux et prédictibles avec des événements inhabituels.

L'objectif de cette thèse est d'améliorer et combiner les méthodes de prédictions de liens et de détections d'événements afin d'obtenir une compréhension unifiée de la dynamique des flots de liens.

Remarques additionnelles

Références

[1] Identifying roles in an IP network with temporal and structural density. Jordan Viard et Matthieu Latapy. Actes de NetSciCom 2014 (Workshop d'Infocom 2014).

[2] RankMerging: Learning to rank in large-scale social networks. Lionel Tabourier, Anne-Sophie Libert et Renaud Lambiotte. Actes de DyNakII (Workshop ECML-PKDD 2014).

[3] Microscopic evolution of social networks. Jure Leskovec, Lars Backstrom, Ravi Kumar et Andrew Tomkins. Actes de KDD 2008.

[4] NetSpot : Spotting significant anomalous regions on dynamic networks. Misael Mongiovi, Petko Bogdanov, Razvan Ranca, Evangelos Papalexakis, Christos Faloutsos et Ambuj K. Singh. Actes d'ICDM 2013.