Direction de recherche : Matthieu LATAPY

Co-encadrement : MAGNIEN Clémence

Groupes et Communautés dans les flots de liens: des données aux algorithmes

Les interactions sont partout : il peut s'agir de contacts entre individus, d'emails, d'appels téléphoniques, etc. Toutes ces interactions sont définies par deux entités interagissant sur un intervalle de temps: par exemple, deux individus se rencontrant entre 12h et 14h.
Nous modélisons ces interactions par des flots de liens qui sont des ensembles de quadruplets (b, e, u, v), où chaque quadruplet représente un lien entre les noeuds u et v existant durant l'intervalle [b,e].

• Dans un graphe, une communauté est un sous-ensemble plus densément connecté qu’une référence.
• Dans le formalisme de flot de liens, les notions même de densité et de référence sont à définir.

Nous étudions donc comment étendre la notion de communauté aux flots de liens. Pour ce faire, nous nous appuyons sur des données réel où une structure communautaire est connue. Puis, nous développons une méthode permettant de trouver automatiquement des sous-flots qui sont jugés pertinents. Ces sous-flots, c’est-à-dire des sous-ensembles de liens, sont trouvés grâce à une méthode de détection de communautés appliquée sur une projection du flot sur un graphe statique. Un sous-flot est jugé pertinent s’il est plus dense que les sous-flots qui lui sont proches temporellement et topologiquement. Ainsi nous approfondissons les notions de voisinage et référence dans les flots de liens.
Nous appliquons cette méthode sur plusieurs jeux de données d’interactions réelles et obtenons des groupes pertinents qui n’auraient pas pu être détectés par les méthodes existantes. Enfin, nous abordons la génération de flots de liens avec une structure communautaire donnée et à la manière d'évaluer une telle partition.

Publications 2014-2018

• 2018
  • M. Danisch, N. Gaumont, J.‑L. GUILLAUME : “A Modular Overlapping Community Detection Algorithm: Investigating the ``From Local to Global’’ Approach”, 16^th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Paris, France, pp. 167-170 (2018)
• 2016
  • N. Gaumont : “Groupes et Communautés dans les flots de liens: des données aux algorithmes”, thèse, soutenance 11/10/2016, direction de recherche Latapy, Matthieu, co-encadrement : Magnien, Clémence (2016)
  • N. Gaumont : “Trouver des séquences de contacts pertinentes dans un flot de liens”, ALGOTEL 2016 - 18^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, ALGOTEL 2016 - 18^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Bayonne, France (2016)
  • N. Gaumont, T. Viard, R. Fournier‑S'niehotta, Q. Wang, M. Latapy : “Analysis of the Temporal and Structural Features of Threads in a Mailing-List”, Complex Networks VIIProceedings of the 7^th Workshop on Complex Networks CompleNet 2016, vol. 644, Studies in Computational Intelligence, Dijon, France, pp. 107-118, (Springer) (2016)
  • N. Gaumont, C. Magnien, M. Latapy : “Finding remarkably dense sequences of contacts in link streams”, Social Network Analysis and Mining, vol. 6 (1), pp. 87, (Springer) (2016)
• 2015
  • N. Gaumont, F. Queyroi, C. Magnien, M. Latapy : “Expected Nodes: A Quality Function for the Detection of Link Communities”, Complex Networks VI, vol. 597, Studies in Computational Intelligence, New-York, United States, pp. 57-64 (2015)
• 2014
  • N. Gaumont, F. Queyroi : “Partitionnement des Liens d’un Graphe : Critères et Mesures”, ALGOTEL 2014 -- 16^es Rencontres, Le Bois-Plage-en-Ré, France, pp. 1-4 (2014)